# 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