FOM: probabilistic rigor

[Stephen Fenner]

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