Smallest Factor

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.

Parameters

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 8 of 8 algorithms


Lenstra elliptic curve factorization	1987	$O(e^{\sqrt{(1+o(1))n\log n}})$	$O(n)$
Williams' p + 1 algorithm	1982	$O(2^n)$	$O(n)$
Pollard's p − 1 algorithm	1974	$O(B \log(B) \log^2(n))$	$O(n+B)$
Wheel factorization	1940	$O(2^{n/2})$	$O(n)$
Euler's factorization method	1940	$O(2^{n/2})$	$O(n)$
Special number field sieve	1940	$O(\exp((1+o(1))(32n/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)$
Fermat's factorization method	1894	$O(2^n)$	$O(n)$
Trial division	1202	$O(2^{n/2})$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms