Primality Testing for Cryptography

Number Theory · Axiom Academy

LESSON Primality Testing for Cryptography Understanding why we need efficient primality tests for modern cryptographic systems like RSA 1. The Need for Large Primes in RSA RSA encryption begins by selecting two large prime numbers p and q , then computing their product n = pq . The security of RSA depends on the fact that while multiplication is fast, factoring n back into p and q is computationally infeasible for large enough primes. Key requirement: For modern security standards, we need primes that are at least 1024 bits (about 308 digits) long. This means we're working with numbers around 10 308 ! The simplest primality test is trial division : check if any number from 2 to n divides n . While this works perfectly for small numbers, it becomes catastrophically slow for cryptographic-sized primes. For a 308-digit number, we'd need to check approximately 10 154 potential divisors. Even checking one billion divisors per second, this would take far longer than the age of the universe (10 17 seconds). 3. Probabilistic vs. Deterministic Tests Modern primality testing takes two main approaches: Probabilistic tests (like Miller-Rabin) run quickly but have a small chance of error. They can conclusively prove a number is composite, but can only say a number is "probably prime" with high confidence. Running multiple rounds reduces the error probability exponentially.

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