The cl-primality Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The cl-primality Reference Manual

This is the cl-primality Reference Manual, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:19:36 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction


* CL-Primality

Tools for testing if a number is prime or composite.  Also for generating prime
numbers.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 cl-primality

Author

Zach Kost-Smith <zachkostsmith@gmail.com>

License

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

Description

Primality testing

Dependency

iterate

Source

cl-primality.asd (file)

Component

cl-primality.lisp (file)


Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 cl-primality.asd

Location

cl-primality.asd

Systems

cl-primality (system)


Previous: , Up: Lisp files   [Contents][Index]

3.1.2 cl-primality/cl-primality.lisp

Parent

cl-primality (system)

Location

cl-primality.lisp

Packages
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

4.1 cl-primality-algorithms

Source

cl-primality.lisp (file)


Previous: , Up: Packages   [Contents][Index]

4.2 cl-primality

Source

cl-primality.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 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 (file)

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 (file)

Function: primep N

Determine if N is prime.

Package

cl-primality

Source

cl-primality.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: *-mod N M MD

Multiply N by M, modulo MD.

Package

cl-primality

Source

cl-primality.lisp (file)

Function: expt-mod-ref B E MD

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

Package

cl-primality

Source

cl-primality.lisp (file)

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

Package

cl-primality

Source

cl-primality.lisp (file)

Function: miller-rabin-pass ()

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

Package

cl-primality

Source

cl-primality.lisp (file)

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 (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   C   F   L  
Index Entry  Section

C
cl-primality.asd: The cl-primality<dot>asd file
cl-primality/cl-primality.lisp: The cl-primality/cl-primality<dot>lisp file

F
File, Lisp, cl-primality.asd: The cl-primality<dot>asd file
File, Lisp, cl-primality/cl-primality.lisp: The cl-primality/cl-primality<dot>lisp file

L
Lisp File, cl-primality.asd: The cl-primality<dot>asd file
Lisp File, cl-primality/cl-primality.lisp: The cl-primality/cl-primality<dot>lisp file

Jump to:   C   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   *  
E   F   G   M   P   T  
Index Entry  Section

*
*-mod: Internal functions

E
expt-mod: Exported functions
expt-mod-ref: Internal functions

F
Function, *-mod: Internal functions
Function, expt-mod: Exported functions
Function, expt-mod-ref: Internal functions
Function, gen-prime: Exported functions
Function, miller-rabin: Internal functions
Function, miller-rabin-pass: Internal functions
Function, primep: Exported functions
Function, trial-division: Internal functions

G
gen-prime: Exported functions

M
miller-rabin: Internal functions
miller-rabin-pass: Internal functions

P
primep: Exported functions

T
trial-division: Internal functions

Jump to:   *  
E   F   G   M   P   T  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables


Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   P   S  
Index Entry  Section

C
cl-primality: The cl-primality system
cl-primality: The cl-primality package
cl-primality-algorithms: The cl-primality-algorithms package

P
Package, cl-primality: The cl-primality package
Package, cl-primality-algorithms: The cl-primality-algorithms package

S
System, cl-primality: The cl-primality system

Jump to:   C   P   S