Given that an integer is prime, can you convince me in a reasonable amount of time of that fact? Stated otherwise: Is there a “short” formal argument that proves the fact that a given prime is indeed prime? Here “short” means that the argument can be written in pages, for some polynomial independent of .

Notice that there is always a short proof of the fact that a given composite number is composite, namely a non-trivial factorization.

Formally this last statement means that the problem of the deciding if a given integer is *composite *is in NP.

The excercise is to prove that the problem of deciding if a given integer is *prime *is in NP.

*Remarks:* The *formal argument *mentioned in the explanation is usually called *certificate. *Notice that the size of the certificate must be polynomial in the logarithm of because is representable by bits and thus the size of the input is and not .

### Like this:

Like Loading...

Hint: Lucas primality test.

Prove that if we have an integer such that:

is coprime with

for all divisor of

then is prime.

Then observe that exponentiation can be done fastly using the squaring method.

LikeLiked by 1 person

@gciruelos you have the right idea! But there are some things to justify.

For example, one does not have to check that is coprime with since this follows from the other two conditions. You are right about the exponentiation being polynomial so the second condition is clearly polynomial (it is not a bad idea to mod out after each exponentiation).

It is not so obvious that the third condition is polynomial. As matter of fact it is not, at least stated that way, but it can be fixed. The problem is that might have a lot of divisors. But one does not need to check the condition for every divisor, it suffices to check it for *maximal* divisors. Maximal with respect to the order given by divisibility, one considers maximal divisors of different from itself. It is easy to check that there are polynomial-many of them.

But there’s a little more: one has to prove the fact that one is actually making the check with each maximal divisor. For this one needs the prime decomposition of , which is polynomial in size, and *by induction*, it is polynomial to prove that the numbers in the factorization are actually prime!

LikeLike