PRIMES is in P

[Jim Whitehead]

http://crypto.cs.mcgill.ca/%7Estiglic/PRIMES_P_FAQ.html

Q1.  What is the purpose of this FAQ?

This FAQ is intended to answer some of the most common questions related to
a recent, very beautiful result in complexity theory that can be found in
[1]. That paper proves that the problem of deciding whether or not an
integer is a prime can be solved in time polynomial in the number of bits
necessary to represent the integer at hand (that is, roughly the logarithm
of the integer itself).  This FAQ also clarifies some misconceptions
surrounding the result.

.....

[1]  Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P .
http://www.cse.iitk.ac.in/news/primality.html

.....

Q11. Could this result break cryptographic algorithms?

No. As mentioned above, fast randomized algorithms for primality testing
were already known, and in fact they are necessary just to make most known
public key cryptosystems feasible!

Some people confuse the factorization problem with the problem of
distinguishing prime numbers from composite numbers.  The factorization
problem is: given an integer n, try to find the prime numbers which when
multiplied together give n.  The fundamental theorem of arithmetic states
that every integer n can indeed be factored into prime numbers, and in a
unique way, so the problem makes sense for any integer.  If one could
efficiently factor large integers, then certain cryptographic algorithms
would be broken (such as the famous RSA encryption and signature schemes).
The fact that PRIME has been found to be in P cannot be used to break any
cryptographic algorithms.

Q12. Does this result have any impact in cryptography at all?

Not in any obvious ways. Certain algorithms need to generate prime numbers
in order to construct cryptographic keys, but algorithms to accomplish this
which can be executed very efficiently already existed before the result in
[1].  The most commonly used ones have a probability of error, but this
error can be made to be arbitrarily small (see question 9) and thus they
give us practically the same assurance as the algorithm proposed in P.
These algorithms that are commonly used in practice are actually faster than
the ones proposed in [1].  The result in [1] is a very important one in
complexity theory, but probably have no (practical) impact in cryptography.

- Jim