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?


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.

| cite | improve this answer | |
  • $\begingroup$ thank you what is the correct definition of IF? $\endgroup$ – user39969 Mar 2 '16 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 Mar 2 '16 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 Mar 2 '16 at 21:13
  • $\begingroup$ Given $n$, you're asking whether it's prime (or a square). $\endgroup$ – Yuval Filmus Mar 2 '16 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 Mar 2 '16 at 21:15

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.

| cite | improve this answer | |
  • 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 Mar 2 '16 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 Mar 2 '16 at 21:15
  • $\begingroup$ Could you include some details in your answer, please? $\endgroup$ – David Richerby Mar 3 '16 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy