Oberon || Library || Module Index || Search Engine || Definition || Module


Ulm's Oberon Library:
RabinMiller


NAME

RabinMiller - implementation of the Rabin-Miller primality testing algorithm

SYNOPSIS

VAR test: Primes.Test;

DESCRIPTION

RabinMiller offers the implementation of the primality testing algorithm developed by M. O. Rabin, based in part on the ideas of G. L. Miller. Look at Journal of Number Theory, v. 12, n. 1, Feb 1980, pp. 128-138: M. O. Rabin, \fIProbabilistic Algorithm for Testing Primality\fP as a reference. The test wrongly declares a none-prime a prime in 1/4 of the cases. The tests are independent and consequently n tests wrongly declare a none-prime a prime in 1/$4 sup n$ of the cases. The Rabin-Miller testing algorithm converges faster than the algorithm implemented in Lehmann

During its initialization, RabinMiller creates an interface of the type defined in Primes and connects it to test.

RabinMiller must have the possibility to create random numbers of the type specified by the given value to be tested. Consequently, a module importing RabinMiller must also import a service provider for the generation of random numbers of the specified type (see, for example, RandCard1024s).

AUTHOR

Frank B.J. Fischer

SEE ALSO

Primes
general abstraction for primality testing algorithm
QuickPrimeTest
a quick test for small primes
Lehmann
implementation of the Lehmann primality testing algorithm
PrimeGen
implementation of a prime number generator

Edited by: borchert, last change: 1997/04/03, revision: 1.1, converted to HTML: 1997/04/28

Oberon || Library || Module Index || Search Engine || Definition || Module