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