Common Lisp Package: CL-PRIMALITY

README:

FUNCTION

Public

GEN-PRIME

Generate a prime that is N-BITS long (less than 2^N-BITS). Just try random numbers of the right length until we find one that is prime (we use MILLER-RABIN for the test by default bit it can be specified via PRIMEP-FN).

MILLER-RABIN

Miller-Rabin probabilistic primality test: Checks if N is prime with the chance of a false positive less than CHANCE-OF-ERROR. This algorithm never gives false negatives.

PRIMEP (N)

Determine if N is prime.

Private

*-MOD (N M MD)

Multiply N by M, modulo MD.

EXPT-MOD (B E MD &OPTIONAL (TOT 1))

Raise B to the power of E, modulo MD (leave TOT as 1).

MILLER-RABIN-PASS

Performs one 'pass' of the Miller-Rabin primality algorithm.

TRIAL-DIVISION (N)

Test for primality by effectively attempting to divide N by every integer between 2 and (/ N 2). This should not actually be used.