0
$\begingroup$

In integer factorization we ask 'Given $N$ is there a $a\in[2,\sqrt{N}+1]$ such that $a|N$?'.

Is the above problem in coNP because we know primes is in $P$?

That is there is no such factor $a$ of $N$ iff $N$ is prime and we have AKS certificate.

So was it not known prior to 2004 that integer factoring was in coNP?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

First of all, you're misstating integer factorization: your version is completely equivalent to primality.

Second, there were primality certificates which could stand for a polytime primality testing algorithm. These are polytime verifiable certificates of primality.

Improve this answer
$\endgroup$
8
  • $\begingroup$ thank you what is the correct definition of IF? $\endgroup$
    – user39969
    Commented Mar 2, 2016 at 21:08
  • $\begingroup$ There are several possible definitions. One option is: given $n,i,j,b$, whether the $i$th smallest prime factor of $n$ has $j$th bit equal to $b$. $\endgroup$
    – Yuval Filmus
    Commented Mar 2, 2016 at 21:08
  • $\begingroup$ interesting.. so I am very confused why is my query in quotes wrong? I see it seems to equal primality but still not compltely clear. $\endgroup$
    – user39969
    Commented Mar 2, 2016 at 21:13
  • $\begingroup$ Given $n$, you're asking whether it's prime (or a square). $\endgroup$
    – Yuval Filmus
    Commented Mar 2, 2016 at 21:14
  • $\begingroup$ That is true but Ok how about a different definition of IF? may be that will clear my confusion. $\endgroup$
    – user39969
    Commented Mar 2, 2016 at 21:15
1
$\begingroup$

Without primes in P does integer factorization lie in coNP? ​ Yes.

So was it not known prior to 2004 that integer factoring was in coNP? ​ No.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ ok without reading blog I want to ask in short how do you show IF is in coNP without primes is in P? $\endgroup$
    – user39969
    Commented Mar 2, 2016 at 21:12
  • 2
    $\begingroup$ Give [recursive certificates for the factorization of p-1] and a generator to show that the multiplicative group mod p is cyclic of order p-1. ​ ​ $\endgroup$
    – user12859
    Commented Mar 2, 2016 at 21:15
  • $\begingroup$ Could you include some details in your answer, please? $\endgroup$
    – David Richerby
    Commented Mar 3, 2016 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.