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

Ulm's Oberon Library:


RabinMiller - implementation of the Rabin-Miller primality testing algorithm


VAR test: Primes.Test;


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).


Frank B.J. Fischer


general abstraction for primality testing algorithm
a quick test for small primes
implementation of the Lehmann primality testing algorithm
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