integer factorization

Work in Progress

Summary

Integer factorization algorithms

Main IdeaTime ComplexitySpaceWorks well whenRemarks
trial divisiontest candidate factors upto bits has a small factordeterministic

slow for large factors
fermat’s factorizationsearch for , then For odd (n=pq), exactly (\frac{p+q}{2}-\lceil\sqrt n\rceil) increments before reaching this pair. bitstwo factors are close togetherdeterministic

potentially very slow for widely separated factors

remove factors of 2 first.
pollard rhoGenerate 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. bits using Floyd/Brent cycle detectionA factor is relatively small.Restart with a different seed or polynomial if the gcd becomes (n).
pollard p-1Choose (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 methodReplace the fixed group of order (p-1) with varying elliptic curve groups; a failed inversion can reveal a factor., with additional arithmetic costs depending on (b).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 sieveCollect 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.
GNFSCollect 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))