how it works

## Generating and testing primes

To generate a prime, all we do is pick a random number in the desired range over and over again until we find one that's prime. Nothing fancy. In fact, no one really knows a better way to find primes!

This means we run a lot of tests of the form "is this number prime?" We use the Baillie-PSW primality test to answer this question. It has been proven to always work on numbers with up to 64 bits (18 digits), and no one has ever found a composite number that it thinks is prime. Therefore, if this website ever gives you a non-prime number, let everyone know! It would be a mathematical discovery.

That said, because we want you to feel truly safe and not rely on conjecture, we also apply the Miller-Rabin primality test with 7 rounds for numbers with more than 64 bits (mostly because we like the number 7). Running this on a 50 digit number (166 bits) with 7 rounds provably has a chance of failure of one in 5 quadrillion (see this paper by Damgard, Landrock, and Pomerance for how we arrived at that estimate). Numbers with more digits have an even smaller chance of failure.

## Math games

Our prime number game uses a hardcoded list of around 150 primes and spits these out at random, starting with mostly small ones and allowing larger and larger primes to appear as the game goes on. The composite numbers are either RSA numbers, i.e. the product of two primes, or simply random composite integers - it's about half and half. The RSA numbers can be tricky to distinguish from primes, especially after you obtain a score of 100. Although most who try cannot reach 100 - can you?