1

The decision version of SEMIPRIME asks if a positive integer n can be factored into 2 primes.
The complement of SEMIPRIME asks if n cannot be factored into 2 primes.
My understanding is that the complement of SEMIPRIME is in NP because a certificate would consist of a list of k $\neq$ 2 primes whose product would be n.

To verify that the product is n would require k multiplications.
Since the input size is log(n), for the verification time to be polynomial in log(n) would require that k $= (log(n))^c$ for some constant c.

I don't understand how we would know that k $= (log(n))^c$?
Could someone clarify?

user137481
  • 2,605
  • 4
    You don't need a complete factorization, you just need three numbers whose product is $n$ (or to certify that $n$ is prime). – vadim123 Mar 28 '16 at 01:36
  • @vadim123 The argument would then be that if the 3 numbers are all prime, we have our proof. If at least one of the numbers is not prime, it can be factored into primes in which case we would have proved that n has a factorization into more than 2 primes. Is my understanding correcct? – user137481 Mar 28 '16 at 02:46
  • That is correct. – vadim123 Mar 28 '16 at 03:24
  • @vadim123 Thanks! – user137481 Mar 28 '16 at 19:00
  • If you ignore that trick and include the entire prime factorization, you can still take $c = 1 + \epsilon$: an $a$-digit number times a $b$-digit number is an $(a+b)$-digit number. – Dan Brumleve Mar 28 '16 at 21:24
  • @DanBrumleve 10 is 2-digits and 100 is 3-digits. Their product is a 4-digit number. Could you clarify what you mean? As well, what is $\epsilon$? – user137481 Mar 29 '16 at 02:24

1 Answers1

1

A natural number $n$ can always be represented with $log(n)$ bits. Each time you multiply a number by another number greater than 1, at least one more bit than either multiplicand is needed to represent the product. Therefore $log(n)$ multiplications are bound to produce a number $log(n)$ bits long or longer. So to produce $n$, $k$ < $log(n)$ always, leaving your verification process polynomial in duration.

Kyle Jones
  • 1,871