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