Fermat's little theorem states: if p is prime, then for every 1 <= a p, a^{p-1} = 1 (mod p) So pick a random positive integer a < P, and if it passes Fermat's little theorem, then it's prime and if it doesn't, then it's likely still prime (with very few exceptions... Eg: Carmichael numbers, but Carmichael numbers are EXTREMELY rare, where you can probably just have a small list of them)