Integer Factoring

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 "second category" algorithms, the running time depends solely on the size of the integer to be factored

Parameters

$n$ : number of bits in the integer

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 5 of 5 algorithms


Shanks's square forms factorization (SQUFOF)	2007	$O(2^{n/4})$	$O(n)$
General number field sieve	1996	$O(\exp((1+o(1))(64n/9)^{1/3}(log n)^{2/3})$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(\Gamma n^{4/3} \log n)$
Dixon's algorithm	1981	$O(e^{2 \sqrt{2} \sqrt{n\log n}})$	$O(n+(B/\log B)^2)$
Quadratic sieve	1981	$O(e^{\sqrt{(1+o(1))n \log n}})$ , under assumption about numbers in a sequence behaving randomly in a given range	$O(n+(B/\log B)^2)$
Continued fraction factorization (CFRAC)	1931	$O(e^{\sqrt{2n\log n}})$	$O(n+(B/\log B)^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 2 of 2 other relevant algorithms


Buhler, Lenstra, Pomerance	1991
Pomerance, Wagstaff	1983