Testing Primality

Discrete Math · Axiom Academy

Learn trial division with the √n bound and probabilistic primality testing using Fermat's test. Excellent work! You've learned two fundamental primality testing methods. Here's what we covered: Trial Division Efficiency: We only need to check divisors up to √n because if n = a × b and both a, b > √n, then a × b > n (contradiction!) Trial Division is Deterministic: It always gives the correct answer but can be slow for large numbers Fermat Test is Probabilistic: If the test fails, the number is definitely composite. If it passes, the number is probably prime (but not guaranteed) Fermat Test Advantage: Much faster for large numbers, uses modular exponentiation instead of checking all divisors Carmichael Numbers: Some composite numbers (like 561) pass the Fermat test for all bases—these are called Carmichael numbers Practical Use: Modern systems use probabilistic tests (like Miller-Rabin) multiple times to achieve extremely high confidence Understanding both deterministic and probabilistic primality tests is crucial for cryptography and number theory. In practice, probabilistic tests with multiple rounds provide excellent speed while maintaining confidence!

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