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

# Ulm's Oberon Library:

Primes

## NAME

Primes - general abstraction for primality testing algorithms
## SYNOPSIS

CONST composite = 0; prime = 1; indefinite = 2;
TYPE Test = POINTER TO TestRec;
TYPE TestRec = RECORD (Disciplines.ObjectRec) END;
TYPE PerformTestProc = PROCEDURE(test: Test;
value: IntOperations.Operand;
VAR p: REAL): INTEGER;
TYPE Interface = POINTER TO InterfaceRec;
TYPE InterfaceRec =
RECORD
(Objects.ObjectRec)
performTest: PerformTestProc;
END;

PROCEDURE Init(test: Test; if: Interface);
PROCEDURE PerformTest(test: Test; value: IntOperations.Operand;
VAR p: REAL): INTEGER;

## DESCRIPTION

`Primes`
defines a general abstraction for primality testing algorithms. For
probabilistic algorithms additionally the probability of the tested value being
prime is given (see `Lehmann` or `RabinMiller`) instead of an
absolute predication.
The interface procedure should meet the specification following:

`performTest`: **PROCEDURE**(`test`: `Test`; `value`: `IntOperations`.`Operand`; **VAR** `p`: **REAL**) : **INTEGER**;-
test given
`value` and return `composite` if `value` is definitely
not prime, return `prime` if `value` is surely prime and return
`indefinite` if `value` may be prime. In this case, `p` in (0..1)
should indicate the probability of `value` being prime if `test` is a
probabilistic primality testing algorithm and the tests should be independent.
Otherwise `p` is to be set to 0.

`Init`
is called by modules which implement a primality test algorithm to connect
the interface `if` to the prime test `test`.

`PerformTest`
tests the given `value` and returns `composite` if `value` is
definitely not prime, returns `prime` if `value` is surely prime and
returns `indefinite` if `value` may be prime. If a probabilistic
primality testing algorithm is used, then `p` in (0..1) indicates the
probability of `value` being prime. Then reiterations of the test improve
the result, because the tests are independent. If the test returns
`indefinite` and `p` is 0, then really no prediction can be made and it
is recommended to use another testing algorithm.

## DIAGNOSTICS

`Primes` asserts that the test and the variable to be tested are given.
## AUTHOR

Frank B.J. Fischer
## SEE ALSO

`IntOperations`-
generic interface for arithmetic integer operations
`QuickPrimeTest`-
quick test for small primes
`RabinMiller`-
implementation of the Rabin-Miller primality test algorithm
`Lehmann`-
implementation of the Lehmann primality test algorithm

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