Special Purpose Factoring Devices

   A journey from Bicycle to Quantum Computers

Computational Number Theory Project
Math 583e, University of Washington
Spring 2009

Factoring Integers

The Factoring Problem

Given an integer , find a factorization  such that .

Solution

An algorithm for factoring integers on general purpose machines or special purpose hardware for factoring.

 

Though the factoring problem is easy to state, the solution is not easy. Here, by easy we mean computationally efficient. Abiding by  the general complexity theory convention, a solution will be called easy or computationally efficient if the running time of the solution algorithm is of a polynomial order in terms of the input size . We will eventually modify the notion of efficiency in terms of time-space cost, that is efficiency in terms of time complexity as well as space complexity. Let us take a look at the current solutions to the factoring problem and a comparison among a few of those.

 

Factoring Algorithms

Reference: Wikipedia [Most of the links point to Wikipedia articles]

Special-Purpose Algorithms

A special-purpose factoring algorithm's running time depends on the properties of its unknown factors: size, special form, etc. Exactly what the running time depends on varies between algorithms.

General-Purpose Algorithms

A general-purpose factoring algorithm's running time depends solely on the size of the integer to be factored. These are mostly based on congruence-of-squares method.

 

Quick Comparison Chart

Factoring Algorithm Time Complexity Remarks
Trial division Most trivial but slowest method
Fermat's factorization method Improved by McKee to
Pollard's rho algorithm This is heuristics with probability of factorization 1/2 
Hart's One line factoring algorithm Literally single line in PARI (Hart) and Python (Boothby)
Shanks' square forms factorization Best exponential factorization algorithm
Lenstra elliptic curve factorization Best algorithm to find small factors ( denotes the smallest factor here)
Dixon's algorithm First step towards formal Quadratic Sieve
Quadratic sieve Invented by Pomerance (1981) and improved to MPQS later
General number field sieve Best factorization method till date (more details)

Notation:  where  is a positive constant and  is a constant. Indicates sub-exponential for .

 

Factoring Hardware

Reference: Journal articles and conference proceedings [Most of the links point to different section of this document for details]

The best algorithms for factoring, till date, are Elliptic Curve Method (for small prime factors) and General Number Field Sieve (for arbitrary numbers without any known/anticipated structure). While ECM relies on fast elliptic curve point multiplication and fast finite field arithmetic, the Number Field Sieve depends heavily on relation generation (sieving by primes for smoothness verification) and fast linear algebra over GF(2). Most of the special purpose hardware for factoring has been proposed to facilitate either of these three areas of computation. We will discuss some of the following in the scope of this project.

Hardware from the Past

Modern Day Sieving Hardware

Hardware for NFS: Relation Collection

Hardware for NFS: Linear Algebra

Hardware of the Future

 

<< Prev: Contents Next: SPDs from Past >>