Primality Testing

Number Theory · Axiom Academy

Exploring algorithms to determine if a number is prime, from simple trial division to probabilistic methods 1. Trial Division: The Foundation The most straightforward method to test if a number n is prime is to check whether any number from 2 to n -1 divides n . If no such divisor exists, then n is prime. However, we can optimize immediately: we only need to check divisors up to √ n . Why? Because if n = a × b with a ≤ b , then a ≤ √n . First Optimization: After checking if n is divisible by 2, we only need to check odd numbers. This cuts our work in half! Better Optimization: After checking 2 and 3, we only need to test numbers of the form 6k ± 1 . Why? All primes greater than 3 can be written as 6k±1 because: So only 6k + 1 and 6k + 5 (equivalently 6k - 1) can be prime! Let's analyze the time complexity of trial division: Naive approach: Check all numbers from 2 to n -1 Optimized with √n: Check divisors up to √ n Further optimized (6k±1): Check only candidates of form 6k±1 up to √ n 4. Beyond Trial Division: Probabilistic Tests While trial division works well for small numbers, it becomes impractical for very large numbers (e.g., 1000-digit numbers used in cryptography). This is where probabilistic primality tests come in. Based on Fermat's Little Theorem : If p is prime and a is not divisible by p , then: To test if n is prime, pick random values of a and check if a n -1 ≡ 1 (mod n ). Complexity: O(k log³ n) for k iterations

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