Introduction to Cryptography with Coding Theory, 3rd Edition

9.3 Primality Testing

Suppose we have an integer of 300 digits that we want to test for primality. We know by Exercise 7 in Chapter 3 that one way is to divide by all the primes up to its square root. What happens if we try this? There are around $3\times {10}^{147}$ primes less than ${10}^{150}$. This is significantly more than the number of particles in the universe. Moreover, if the computer can handle ${10}^{10}$ primes per second, the calculation would take around $3\times {10}^{130}$ years. (It’s been suggested that you could go sit on the beach for 20 years, then buy a computer that is 1000 times faster, which would cut the runtime down to $3\times {10}^{127}$ years – a very large savings!) Clearly, better methods are needed. Some of these are discussed in this section.

A very basic idea, ...