Skip to main content
Computer Science

Return to Question

deleted 4 characters in body
Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

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$AKS certificate.

So was it not known prior to $2004$2004 that integer factoring was 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?

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?

Source Link
user39969
user39969

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?