The cl-primality Reference Manual

This is the cl-primality Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed May 15 04:23:02 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 cl-primality

Primality testing

Author

Zach Kost-Smith <>

License

LLGPL (http://opensource.franz.com/preamble.html)

Dependency

iterate (system).

Source

cl-primality.asd.

Child Component

cl-primality.lisp (file).


3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 cl-primality/cl-primality.asd

Source

cl-primality.asd.

Parent Component

cl-primality (system).

ASDF Systems

cl-primality.


3.1.2 cl-primality/cl-primality.lisp

Source

cl-primality.asd.

Parent Component

cl-primality (system).

Packages
Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 cl-primality

Source

cl-primality.lisp.

Use List
  • common-lisp.
  • iterate.
Public Interface
Internals

4.2 cl-primality-algorithms

Source

cl-primality.lisp.


5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Ordinary functions

Function: expt-mod (b e md &optional tot)

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

Package

cl-primality.

Source

cl-primality.lisp.

Function: gen-prime (n-bits &optional primep-fn)

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 but it can be specified via PRIMEP-FN).

Package

cl-primality.

Source

cl-primality.lisp.

Function: primep (n)

Determine if N is prime.

Package

cl-primality.

Source

cl-primality.lisp.


5.2 Internals


5.2.1 Ordinary functions

Function: *-mod (n m md)

Multiply N by M, modulo MD.

Package

cl-primality.

Source

cl-primality.lisp.

Function: expt-mod-ref (b e md)

A reference implementation, do not use except for testing purposes.

Package

cl-primality.

Source

cl-primality.lisp.

Function: miller-rabin (n &optional chance-of-error)

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.

Package

cl-primality.

Source

cl-primality.lisp.

Function: miller-rabin-pass (n a)

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

Package

cl-primality.

Source

cl-primality.lisp.

Function: 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.

Package

cl-primality.

Source

cl-primality.lisp.


Appendix A Indexes


A.1 Concepts


A.3 Variables