[Forwarded from the UK Crypto Mailing List] Subject: Large Primes From: Paul Leyland pleyland@microsoft.com Date: Thu, 15 Aug 2002 07:25:53 -0700 The importance of this result is that the algorithm guarantees to give a yes/no answer to the question "is N prime" and guarantees to do so in a time which is bounded by a polynomial in the size of N. The size of N is shorthand for log(N) --- it takes that number of bits or digits or what have you to specify N --- and the best result which has been proved and stated publically is that the polynomial is log(N)^12 which is a rather high power. I've heard from a source I am not yet at liberty to reveal that the 12 has since been reduced to 8. There is a bunch of known algorithms which when asked the question give an answer of "maybe" or "no", where the likelihood that "maybe" actually means "yes" is extremely high but still short of certainty. These are so-called probable-prime tests (or, better, compositeness tests) and are generally easily adequate for crypto-grade primes. There is another bunch of known algorithms which give an answer of "yes", "no" or "don't know". If the result is definite, that's the end of the matter. If an uncommital answer pops out, it's possible to re-run the algorithm with a different random choice of internal variables and to get another yes/no/unknown answer. In principle, it's possible to get an indefinite run of "don't know" answers, but the probability of this occurring is vanishingly small --- so much so that the expected time you have to wait before a "yes" or a "no" arrives is bounded by a polynomial in log(N). These are the so-called random polynomial time deterministic primality provers. A final group of algorithms invariably give a yes/no answer but take time which grows faster than any polynomial in log(N). A simple example is to try to factor N by dividing it by all integers smaller than N. This takes time which exponentially large --- it is time N, which is exp (log (N)). Some better algorithms take time which is only very slightly larger than a polynomial, but they are still superpolynomial. Some of the superpolynomial algorithms in the final class seem to run in polynomial time in practice, and if one or more celebrated hypotheses in number theory could be proved, these algorithms could also be proved to run in polynomial time. For intstance, if the most notorious hypothesis, ERH or the extended Riemann hypothesis, were proved the Miller-Rabin test could be proved to run in polynomial time. If a very plausible conjecture about the density of Sophie-German primes could be proved, the new algorithm could be proved to run in time log(N)^6 (or better ...) but at the present the best that can be proved is log(N)^12 (or 8 if my mysterious source is correct, and I believe he is). As far as practicality is concerned, it's a beautiful algorithm but very slow. There are far more efficient algorithms around for proving primality. However, it's a very new algorithm and can almost certainly be improved immensely, so it may yet turn into something which is efficient in practice. One reason for the excitement within the mathematical community is not only does this algorithm settle a long-standing problem, it also does so in a brilliantly simple manner. Everyone is now wondering what else has been similarly overlooked. Paul ---------------------------------------------------------------------------- ---------------------------------------------------------------------------- 2. Subject: Large Primes From: Paul Leyland pleyland@microsoft.com Date: Fri, 16 Aug [Owen Lewis wrote] > Many thanks for the trouble taken, Paul. Every stone provides some > foundation for others to build on or to use as a fulcrum. Or to pick up and throw at someone, which is what the principle use of the AKS algorithm seems to be at the moment. The amount of ill-informed blether about the demise of public key cryptography is truly amazing. Paul ---------------------------------------------------