The Integer Factoring Problem

Cryptography · Axiom Academy

LESSON The Integer Factoring Problem The hard mathematical problem underlying RSA cryptography Problem Statement: Given a composite integer n that is the product of two large primes p and q , find p and q . This creates a fundamental asymmetry in computational difficulty: Easy direction (multiplication): Computing n = p × q takes polynomial time Hard direction (factoring): Finding p and q from n has no known polynomial-time algorithm 2. Trial Division: The Naive Approach The most straightforward factoring method is trial division : test every possible divisor up to √n. Why only test up to √n? If n = p × q and p ≤ q, then p ≤ √n. So we're guaranteed to find at least one factor by √n. 3. Modern Factoring Algorithms Sophisticated algorithms exploit mathematical structure to factor much faster than trial division: Despite these improvements, both algorithms are still sub-exponential but super-polynomial - far too slow for cryptographically-sized numbers. The RSA Factoring Challenge tracked progress in breaking RSA numbers of various sizes: Key insight: Each additional bit roughly doubles the difficulty. Moving from 829 bits to 2048 bits (standard today) makes factoring astronomically harder. 5. The Connection to RSA Security Breaking RSA encryption is at least as hard as factoring n, but could it be harder?

This is the written version of the interactive lesson above. See the full Cryptography course.