Prime Number Tester

Trial Division Method

A deterministic primality test that:

1. Checks if number ≤ 1 → composite
2. Checks if number is 2 → prime
3. Checks even numbers → composite if divisible by 2
4. Tests odd divisors from 3 up to √n
5. If any divisor found → composite
6. If no divisors found → prime

Guaranteed accurate but slow for large numbers

Miller-Rabin Test

A probabilistic primality test that:

1. Writes n-1 as d×2^s
2. Chooses random witnesses (5 in our case)
3. For each witness a:
   • Computes x = a^d mod n
   • If x ≡ 1 or x ≡ -1 → continue
   • Squares x up to s-1 times looking for -1
4. If any witness shows compositeness → composite
5. If all witnesses pass → probably prime

Fast for large numbers with 97.5% accuracy (5 iterations)