Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Winter 2005/2006 

Modern probabilistic prime tests

Daniel Loebenberger ( Universität Erlangen - Nürnberg )

Thursday, December, 08th, 2005, 1300, b-it 1.25


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)

Imprint, webmaster & more