FOM: probabilistic rigor
Stephen Fenner
fenner at cs.sc.edu
Mon Oct 19 12:35:15 EDT 1998
On Sat, 17 Oct 1998 JoeShipman at aol.com wrote:
> I am not sure primality tests are quite as practically feasible as you claim.
> There is a deterministic "almost polynomial time" (exponent is loglog of the
> input size rather than constant) algorithm and a probabilistic one which fits
> your description (never makes an error and *usually* runs quickly) whose worst
> case is "almost polynomial time" but with a better constant in the exponent
> than the deterministic case, but the *usually* means "always for most inputs"
> rather than "most of the time for all inputs". There is also a test which
> runs in polynomial time with randomized input which has an exponentially small
> probability of error, and a test which runs in polynomial time and is always
> correct if the Extended Riemann Hypothesis is true. But I am not aware that
> there is a test for which it has been unconditionally proven that
> 1) it never makes an error
> 2) there is a polynomial P such that for *any* input to be tested for
> primality, the probability it does not finish within P(inputsize) steps is
> exponentially small.
>
> Such an algorithm would certainly be the next best thing to a true P-time
> algorithm; but can you give me a reference that such an algorithm actually
> exists for testing primality?
>
> -- JS
There is provably polynomial expected time algorithm to prove primality
due to Adleman and Huang, using generalizations of elliptic curves:
L. Adleman and M. Huang, "Recognizing primes in random polynomial time."
Proceedings of the 19th Annual ACM Symposium on the Theory of Computing,
1987, pp. 462-469.
There must be a later journal version, but I don't have a reference for
it. There is a brief discussion of it (and elliptic curve methods in
general) in Koblitz, _A_Course_in_Number_Theory_and_Cryptography_(2nd ed),
Springer GTM 114, 1994, pages 187-191.
This, combined with the Miller-Rabin or Solovay-Strassen tests, satisfies
the criteria you gave, but apparently the Adleman-Huang algorithm is
completely impractical.
Stephen Fenner 803-777-2596
Computer Science Department fenner at cs.sc.edu
University of South Carolina http://www.cs.sc.edu/~fenner
Columbia, SC 29208 USA
More information about the FOM
mailing list