Integer Factoring

Description

Given an $n$-bit integer $N$, find a non-trivial factorization $N=pq$ (where $p, q>1$ are integers) or return that $N$ is prime. For "first category" algorithms, the running time depends on the size of smallest prime factor.

Related Problems

Related: Smallest Factor

Parameters

n: number of bits in the integer

B: bound parameter (if needed)

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Trial division	1202	$O({2}^{n/2})$	$O(n)$ auxiliary	Exact	Deterministic
Wheel factorization	1940	$O({2}^{n/2})$	$O(n)$ auxiliary	Exact	Deterministic
Pollard's rho algorithm	1975	-	$O(n)$ auxiliary	Exact	Deterministic	Time
Pollard's p − 1 algorithm	1974	$O(B*log B*log^{2}(n)$)?	$O(n+B)$ auxiliary	Exact	Deterministic	Time
Williams' p + 1 algorithm	1982	$O({2}^ (n))$	$O(n)$ auxiliary?	Exact	Deterministic	Time
Lenstra elliptic curve factorization	1987	$O(e^{(\sqrt(({1}+o({1}))n*log n))})$	$O(n)$ auxiliary?	Exact	Deterministic	Time
Fermat's factorization method	1894	$O({2}^n)$	$O(n)$ auxiliary	Exact	Deterministic	Time
Euler's factorization method	1940	$O({2}^{(n/{2})})$	$O(n)$ auxiliary	Exact	Deterministic
Dixon's algorithm	1981	$O(e^{({2} \sqrt({2}) \sqrt(n*logn))}){4}	$O(n+(B/logB)$^{2})?	Exact	Deterministic	Time
Continued fraction factorization (CFRAC)	1931	$O(e^{\sqrt({2}n*logn)})$	$O(n+(B/logB)$^{2})?	Exact	Deterministic	Time
Quadratic sieve	1981	-	$O(n+(B/logB)$^{2})?	Exact	Deterministic	Time
Rational sieve	1993	$O(e^{sqrt(({2}+o({1})$)n*logn)})	$O(n+(B/logB)$^{2})?	Exact	Parallel	Time
Shanks's square forms factorization (SQUFOF)	2007	$O({2}^{(n/{4})$})	$O(n)$?	Exact	Deterministic	Time
Special number field sieve	1940	$O(exp(({1}+o({1})$)({32}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically?	$O(n^{2/3})$	Exact	Deterministic	Space
General number field sieve	1996	$O(exp(({1}+o({1})$)({64}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically?	$O(n^{2/3})$	Exact	Deterministic	Time & Space
Shor's algorithm Quantum Implementation	1994	$O(n)$	$O(n)$	Exact	Quantum	Time & Space

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff