# Without primes in $P$ does integer factorization lie in $coNP$?

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.

• thank you what is the correct definition of IF? – user39969 Mar 2 '16 at 21:08
• 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$. – Yuval Filmus Mar 2 '16 at 21:08
• 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. – user39969 Mar 2 '16 at 21:13
• Given $n$, you're asking whether it's prime (or a square). – Yuval Filmus Mar 2 '16 at 21:14
• That is true but Ok how about a different definition of IF? may be that will clear my confusion. – 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.

• ok without reading blog I want to ask in short how do you show IF is in coNP without primes is in P? – user39969 Mar 2 '16 at 21:12
• 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. ​ ​ – user12859 Mar 2 '16 at 21:15
• Could you include some details in your answer, please? – David Richerby Mar 3 '16 at 5:30