Simple and hard problems I

Given that an integer p 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 O(P(\mathrm{log} \,n)) pages, for some polynomial P independent of n.

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 n because n is representable by \mathrm{log}\, n bits and thus the size of the input is \mathrm{log}\, n and not n.

Simple and hard problems I

2 thoughts on “Simple and hard problems I

  1. gciruelos says:

    Hint: Lucas primality test.

    Prove that if we have an integer a such that:

      a is coprime with n
      a^{n-1} \equiv 1 (\mod n)
      a^{\frac{n-1}{q}} \not\equiv 1 (\mod n) for all q divisor of n-1

    then n is prime.

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

    Liked by 1 person

  2. @gciruelos you have the right idea! But there are some things to justify.
    For example, one does not have to check that a is coprime with n 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 n-1 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 n-1 different from n-1 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 n-1, which is polynomial in size, and *by induction*, it is polynomial to prove that the numbers in the factorization are actually prime!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s