On Polynomial Time Primality Testing
Abstract
Prime numbers are an important part of modern cryptography.
Most modern algorithms for encryption involve multiplying
two large primes and their security depends on the difficulty
of factoring the result. In creating large numbers that are
a product of two primes it is important to ensure that the
original numbers are, in fact, prime. Finding an efficient
way to do this has long been a difficult problem in mathematics.
There are many efficient probabilistic tests which can
demonstrate that a number is most likely prime. Recently,
however, a deterministic algorithm for primality testing
was devloped that runs efficiently enough for practical use.
Table of Contents
Complete List of References
- [AM1]
Agrawal, Manindra, Neeraj Kayal, and Nitin Saxena.
Primes is in P.
Annals of Mathematics, Vol. 160, No. 3, (Sept. 2003), 781—793.
- [RP1]
Ribenboim, Paulo.
The Little Book of Bigger Primes.
New York: Springer Verlag, 2004.
- [DM1]
du Sautoy, Marcus.
The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics.
New York: Harper Collins, 2003.
- [WD1]
Well, David.
Prime Numbers: The Most Mysterious Figures in Math.
Hoboken, NJ: John Wiley Sons, Inc, 2005.
- [DM1]
Davis, Martin D., Ron Sigal, and Elaine J. Weyuker.
Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science.
San Diego: Academic Press, Inc., 1994.
- [EW1]
Ellison, William and Fern Ellison.
Prime Numbers.
New York: Wiley-Interscience, 1985.
- [NJ1]
Neukirch, Jurgen.
Algebraic Number Theory.
New York: Springer-Verlag, 1999.
- [BP1]
Berrizbeitia, Pedro.
Sharpening "Primes is in P" for a large family of numbers.
Mathematics of Computation, Vol. 74 (2005), 2043—2059.
