# The cl-factoring Reference Manual

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

# The cl-factoring Reference Manual

This is the cl-factoring Reference Manual, generated automatically by Declt version 2.3 "Robert April" on Wed Mar 14 03:15:35 2018 GMT+0.

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

## 1 Introduction

```
* CL-Factoring

This library presents a set of algorithms for computing integer factorizations.
An interface is provided that takes an integer and will return a list of prime
numbers such that, when multiplied together, will result in the original number.

There is no magic sauce here or mathematical breakthroughs; the time
complexities of each algorithm is exponential.

** Interface

The library provides the function =factor=.

Specific factoring methods can be accessed from the package
=cl-factoring-algorithms=.

** General Purpose Factoring Algorithms

1. Trial Division
2. Pollard's Rho
3. Brent's Cycle
4. Hypercubic Polynomial Quadratic Sieve

Certain algorithms may be developed by others and be licensed under more
permissive licenses.  If development is performed on these, the license will
remain as is (the LLGPL won't infect them).

```

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-factoring

Author

Zach Kost-Smith <zachkostsmith@gmail.com>

LLGPL (http://opensource.franz.com/preamble.html) except for the file "ulimyhmpqs-1.0.lisp" which is 3 Clause BSD

Description

Integer Factoring

Dependencies
• iterate
• cl-primality
Source

cl-factoring.asd (file)

Components

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-factoring.asd

Location

cl-factoring.asd

Systems

cl-factoring (system)

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

#### 3.1.2 cl-factoring/ulimyhmpqs-1.0.lisp

Parent

cl-factoring (system)

Location

ulimyhmpqs-1.0.lisp

Packages
Exported Definitions

hmpqs (function)

Internal Definitions

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

#### 3.1.3 cl-factoring/cl-factoring.lisp

Dependency

ulimyhmpqs-1.0.lisp (file)

Parent

cl-factoring (system)

Location

cl-factoring.lisp

Packages
Exported Definitions

factor (function)

Internal Definitions

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

## 4 Packages

Packages are listed by definition order.

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

### 4.1 ulimy-hmpqs

Source

ulimyhmpqs-1.0.lisp (file)

Use List

common-lisp

Exported Definitions

hmpqs (function)

Internal Definitions

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

### 4.2 cl-factoring-algorithms

Source

cl-factoring.lisp (file)

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

### 4.3 cl-factoring

Source

cl-factoring.lisp (file)

Use List
• cl-primality
• iterate
• common-lisp
Exported Definitions

factor (function)

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: factor N

Return the prime factorization of N as a sorted (smallest to largest) list. Factors that appear more than once are present mulitiple times in the output.

(reduce ’* (factor n)) = n

Package
Source

cl-factoring.lisp (file)

Function: hmpqs N &key REPORT2
Package
Source

ulimyhmpqs-1.0.lisp (file)

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

### 5.2 Internal definitions

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

#### 5.2.1 Constants

Constant: minutes-per-internal-time-unit
Package
Source

ulimyhmpqs-1.0.lisp (file)

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

#### 5.2.2 Special variables

Special Variable: *count-x*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *how-to-handle-new-relations*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *max-divide-out*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *max-stored-prime*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *nr-of-stored-primes*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *qr256*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *qs-line*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *qs-line-width*
Package
Source

ulimyhmpqs-1.0.lisp (file)

Special Variable: *stored-primes*
Package
Source

ulimyhmpqs-1.0.lisp (file)

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

#### 5.2.3 Macros

Macro: 2* I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: 2^i I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: ? &rest XXX
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: concat &rest STRNGS
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: define-relation-handling MODE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: dfloat X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: div A B
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: div2 X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: even-down I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: even-up I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: expt2 I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: fb-log10 Q
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: fb-p Q
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: h1 Y
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: ilog2 X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: ilog2h1y Y
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: init-subsieve Y YSTOP QUADRANT
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: let-qs RETURN-IDS N &rest STUFF
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: make-topoff-n-cubes DIMENSION
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: odd-down I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: odd-up I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: str\$ X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: topoff-bucket LOG-SUM
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: topoff-index LOG-SUM
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: with-all-primes P &rest BODY
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: with-all-stored-primes P &rest BODY
Package
Source

ulimyhmpqs-1.0.lisp (file)

Macro: yofh H QUADRANT
Package
Source

ulimyhmpqs-1.0.lisp (file)

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

#### 5.2.4 Functions

Function: a-generator ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: a_ideal N M
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: b-generator A A-FACTORS D
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: b-opt N
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: binoc N K
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: brents-cycle N

Find the prime factorization of N.

Package
Source

cl-factoring.lisp (file)

Function: brents-cycle-attempt ()
Package
Source

cl-factoring.lisp (file)

Function: brents-cycle-find-factor N
Package
Source

cl-factoring.lisp (file)

Function: centered-report2 X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: centered-title X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: copy-factor INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: divide-out-mod-2 X HX A-FACTORS
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: divmod A B MODULO
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: efactors N &key REPORT2
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: exptmod BASE POWER MODULO
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-1/amodp INSTANCE
Function: (setf factor-1/amodp) VALUE INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-base-size N
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-dp INSTANCE
Function: (setf factor-dp) VALUE INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-ep INSTANCE
Function: (setf factor-ep) VALUE INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-log10p INSTANCE
Function: (setf factor-log10p) VALUE INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-log2p INSTANCE
Function: (setf factor-log2p) VALUE INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-p OBJECT
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-prime INSTANCE
Function: (setf factor-prime) VALUE INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factor-sqrtnmodp INSTANCE
Function: (setf factor-sqrtnmodp) VALUE INSTANCE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: factors-of-n-report2 ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: fb-log-sum I0 I1
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: fb-picture WID
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: got-them-all ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: hard D
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: init-sieve A BETA GAMMA
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: initial-report2 ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: invmod X M
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: invmod! X M
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: jacobisymbol P Q
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: m-opt LOG10N
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: make-cubes A-LIST LOG-REST Q QMAX D
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: make-cublets A-LIST LOG-REST Q QMAX D
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: make-factor &key (PRIME PRIME) (SQRTNMODP SQRTNMODP) (LOG2P LOG2P) (LOG10P LOG10P) (1/AMODP 1/AMODP) (DP DP) (EP EP)
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: make-factor-base N FB-SIZE
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: make-primes N
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: merge-cubes A1 A2
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: minutes ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: multiple-append X NROFCOPIES XCOPIES
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: multiple-cons X NROFCOPIES XCOPIES
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: new-factor F
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: nextpprime P
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: nice-time MINS
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: pi_ N

approx #{p | p<=n & p prime}

Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: pollards-rho N

Find the prime factorization of N.

Package
Source

cl-factoring.lisp (file)

Function: pollards-rho-attempt N
Package
Source

cl-factoring.lisp (file)

Function: pollards-rho-find-factor N
Package
Source

cl-factoring.lisp (file)

Function: power-breaker X &optional MAX-FACTOR
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: pprime? P &optional TRIALS
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: prime I
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: prime? X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: put-into-its-bucket R
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: qs N &key M B DELTA-T OMIT-BELOW SLP-LOG2 ALFA REPORT2 RETURN2
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: quadratic-residue? N P
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: report2 ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: report2? ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: report2?sieving-time ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: report2?total-time ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: sieve-for-ab A B A-FACTORS
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: sqrtmodprime N P
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: square? X
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: squarep N
Package
Source

cl-factoring.lisp (file)

Function: trial-division N
Package
Source

cl-factoring.lisp (file)

Function: try-to-solve IX-LIST
Package
Source

ulimyhmpqs-1.0.lisp (file)

Function: xor-merge U V
Package
Source

ulimyhmpqs-1.0.lisp (file)

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

#### 5.2.5 Conditions

Condition: factor-attempt-failed ()
Package
Source

cl-factoring.lisp (file)

Direct superclasses

condition (condition)

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

#### 5.2.6 Structures

Structure: factor ()
Package
Source

ulimyhmpqs-1.0.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: prime
Type

fixnum

Initform

0

factor-prime (function)

Writers

(setf factor-prime) (function)

Slot: sqrtnmodp
Type

fixnum

Initform

0

factor-sqrtnmodp (function)

Writers

(setf factor-sqrtnmodp) (function)

Slot: log2p
Type

fixnum

Initform

0

factor-log2p (function)

Writers

(setf factor-log2p) (function)

Slot: log10p
Type

float

Initform

0.0

factor-log10p (function)

Writers

(setf factor-log10p) (function)

Slot: 1/amodp
Type

fixnum

Initform

0

factor-1/amodp (function)

Writers

(setf factor-1/amodp) (function)

Slot: dp
Type

fixnum

Initform

0

factor-dp (function)

Writers

(setf factor-dp) (function)

Slot: ep
Type

fixnum

Initform

0

factor-ep (function)

Writers

(setf factor-ep) (function)

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

## Appendix A Indexes

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

### A.1 Concepts

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

### A.2 Functions

Jump to: (   2   ?   A   B   C   D   E   F   G   H   I   J   L   M   N   O   P   Q   R   S   T   W   X   Y
Jump to: (   2   ?   A   B   C   D   E   F   G   H   I   J   L   M   N   O   P   Q   R   S   T   W   X   Y

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

### A.3 Variables

Jump to: *   1   C   D   E   L   M   P   S
Jump to: *   1   C   D   E   L   M   P   S

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

### A.4 Data types

Jump to: C   F   P   S   U
Jump to: C   F   P   S   U