Modern probabilistic prime tests
Daniel Loebenberger ( Universität Erlangen - Nürnberg )
Thursday, December, 08th, 2005, 1300, b-it 1.25
Contents
After the discovery of 'PRIMES in P' by Agrawal, Kayal and Saxena, probabilistic primetests are still in wide use due to their efficiency. The most important of them is certainly the Miller-Rabin test and of course the very simple Fermat test. Both of them work within the group of units of Z/(n). Less prominent are the Lucas test and the Frobenius test, that work within the ring Z[X]/(f(x),n), where f(x) is a polynomial of degree 2 in Z[X]/(n). Damgard and Frandsen proposed the combination of these tests, called the extended quadratic Frobenius test, which has a very small error probability.
The lecture gives an overview of the probabilistic tests mentioned above and compares the tests concerning their error probability and runtime. (Talk)