Why is factoring hard?

No polynomial-time classical algorithm is known for integer factorization. The best algorithm (GNFS) has sub-exponential complexity. For a 2048-bit RSA key (product of two 1024-bit primes), factoring is infeasible with current technology. Quantum computers (Shor's algorithm) can factor in polynomial time — a threat to RSA, but large quantum computers do not yet exist.

What is Pollard's rho?

A probabilistic factoring algorithm that uses a random walk modulo n. It finds a factor in O(sqrt(p)) where p is the smallest prime factor — much faster than trial division for numbers with small factors. It works by finding a collision in the random walk (birthday paradox) and using GCD to extract a factor.

TASK

Factor integers into primes

Integer factorization decomposes a number into its prime factors. Learn trial division, Pollard's rho, and why factoring is hard.

1

Integer factorization finds prime factors: 60 = 2^2 × 3 × 5. Methods: trial division (try all primes up to sqrt(n)), Pollard's rho (random walk, finds small factors fast), Pollard's p-1 (when p-1 is smooth), quadratic sieve and GNFS (for large numbers). Factoring is believed to be hard (no polynomial-time classical algorithm) — this is the basis of RSA security.
2

Factor Calculator →
Factor an integer into its prime factors. The tool handles small to medium numbers efficiently. For large numbers (> 10^20), factoring becomes very slow — this is expected and is why RSA with large keys is secure.
3

Gcd Calculator →
Use GCD as a factoring aid. If gcd(n, m) > 1, you found a factor of n. This is used in Pollard's p-1 and other factoring algorithms. The GCD is fast (Euclidean algorithm, O(log n)) even for large numbers.

Frequently asked questions

Why is factoring hard?: No polynomial-time classical algorithm is known for integer factorization. The best algorithm (GNFS) has sub-exponential complexity. For a 2048-bit RSA key (product of two 1024-bit primes), factoring is infeasible with current technology. Quantum computers (Shor's algorithm) can factor in polynomial time — a threat to RSA, but large quantum computers do not yet exist.
What is Pollard's rho?: A probabilistic factoring algorithm that uses a random walk modulo n. It finds a factor in O(sqrt(p)) where p is the smallest prime factor — much faster than trial division for numbers with small factors. It works by finding a collision in the random walk (birthday paradox) and using GCD to extract a factor.