deterministic primality test

[Don Davis]

from slashdot:

http://www.cse.iitk.ac.in/primality.pdf

                 PRIMES in P
       M. Agrawal, N. Kayal, N. Saxena
            Dept. of C.S. & Eng,
        Indian Inst. of Tech. Kanpur
                 Aug 6, 2002

Abstract:  We present a deterministic polynomial time
algorithm that determines whether an input number is
prime or composite.

Summary:  time complexity is O((log n)^12), but the
exponent can be reduced to 6, assuming the truth of
the hardy-littlewood conjecture about the distribution
of sophie germain primes.  the exponent might be
reducible to 3, if another, less-famous conjecture
is true.

bona fides:  FWIW, the authors acknowledge some well-
known workers.

				- don davis





-

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com