integer factorization
Summary
Integer factorization algorithms
| Main Idea | Time Complexity | Space | Works well when | Remarks | |
|---|---|---|---|---|---|
| trial division | test candidate factors upto | deterministic slow for large factors | |||
| fermat’s factorization | search for | For odd (n=pq), exactly (\frac{p+q}{2}-\lceil\sqrt n\rceil) increments before reaching this pair. | two factors are close together | deterministic potentially very slow for widely separated factors remove factors of 2 first. | |
| pollard rho | Generate a sequence modulo (n); a collision modulo an unknown factor is detected through a gcd. | Heuristic expected (O(\sqrt p)) iterations; (O(n^{1/4})) for balanced semiprimes. | A factor is relatively small. | Restart with a different seed or polynomial if the gcd becomes (n). | |
| pollard p-1 | Choose (M) divisible by (p-1); compute (\gcd(a^M-1,n)). | approximately | Small arithmetic state; prime generation/storage adds space depending on implementation. | (p-1) consists of small prime powers. | Requires (p-1\mid M); gcd must lie strictly between (1) and (n). |
| ECM - elliptic curve method | Replace the fixed group of order (p-1) with varying elliptic curve groups; a failed inversion can reveal a factor. | Low in basic stage 1; stage 2 uses additional storage. | A factor is much smaller than (n). | Success depends on smooth curve-group orders; retry with new curves. | |
| quadratic sieve | Collect smooth values of (a^2-n); use linear algebra to construct a congruence of squares. | Large: factor base, relations, sieve arrays, and sparse matrix. | General composites without an exploitable factor structure. | Relation collection and linear algebra dominate; space depends heavily on implementation. | |
| GNFS | Collect rational and algebraic smooth relations to construct a congruence of squares. | Large: relations, factor bases, and sparse matrix. | Very large general composites. | Substantial setup and implementation complexity. |
see L-notation for the subexponential time complexity
Concept
Integer factorization
- decomposition of a positive integer into a product of integers
- numbers are either composites or primes
Fundemental Theorem of Arithmetic
Trial division
- most basic primality test
- if
is composite, it must have a factor
TrialDivision(n): // returns (list F of all prime factors of n)
P <- set of all primes ≤ n**0.5
F <- empty list of factors
for each prime p in P do
if n % p == 0
add factor p to list F
n <- n/p
if F is empty // original n is prime?
add factor n to list F
return F
determining if a number
is prime is non-trivial as increases, most algorithms just try all numbers
Extra
Primality test in python
- trial division adjacent
- save some time by excluding multiples of 2 and 3
python
def isPrime(a):
if a == 2:
return True
if a < 2 or a % 2 == 0:
return False
return not any(a % x == 0 for x in range(3, int(a**0.5) + 1, 2))