Primality testing

In this section, we examine some simple general methods for determining if a number is prime. There are much more efficient (and complicated) primality tests what those which we discuss here ^1.4 - see for example [BS].

The first prime to be discovered having over 1 million digits was the Mersenne prime, $2^{6972593}-1$. The primality of this integer was determined by Nayan Hajratwala in 1993, who received $ 50000 from the Electronic Frontier Foundation as a reward for it's discovery. The first person who discovers a prime having over 1 billion digits may win $ 250000.