Last updated
Factorization Algorithm Comparison
- Trial division: Tests all primes up to √n — simple, works well for n up to ~10 million
- Pollard's rho: Probabilistic, much faster for large composites — used for n up to ~10^20
- Quadratic sieve: Best for numbers up to ~10^100
- General number field sieve (GNFS): Best known algorithm for very large numbers — used to factor RSA challenge numbers
- Quantum algorithms (Shor's): Would factor large numbers efficiently — threatens RSA if large quantum computers are built
Examples
Example 1: Basic Factorization
Factorize: 360
Step-by-step:
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
Result: 360 = 2 × 2 × 2 × 3 × 3 × 5
Exponential notation: 360 = 2³ × 3² × 5¹
Factor tree:
360
/ \
2 180
/ \
2 90
/ \
2 45
/ \
3 15
/ \
3 5
Example 2: Finding GCD Using Prime Factorization
Find GCD(48, 180):
48 = 2⁴ × 3¹
180 = 2² × 3² × 5¹
GCD = product of minimum powers of shared primes:
2: min(4, 2) = 2²
3: min(1, 2) = 3¹
5: not in 48, so excluded
GCD(48, 180) = 2² × 3 = 4 × 3 = 12
Verification: 48 ÷ 12 = 4 ✓ | 180 ÷ 12 = 15 ✓
Example 3: Finding LCM Using Prime Factorization
Find LCM(12, 18, 30):
12 = 2² × 3¹
18 = 2¹ × 3²
30 = 2¹ × 3¹ × 5¹
LCM = product of maximum powers of all primes:
2: max(2, 1, 1) = 2²
3: max(1, 2, 1) = 3²
5: max(0, 0, 1) = 5¹
LCM(12, 18, 30) = 4 × 9 × 5 = 180
Verification:
180 ÷ 12 = 15 ✓
180 ÷ 18 = 10 ✓
180 ÷ 30 = 6 ✓