[11366] in cryptography@c2.net mail archive
deterministic primality test
daemon@ATHENA.MIT.EDU (Don Davis)
Wed Aug 7 14:26:04 2002
Date: Wed, 7 Aug 2002 08:54:02 -0400
To: cryptography@wasabisystems.com
From: Don Davis <dtd@world.std.com>
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@wasabisystems.com
