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×10147 primes less than 10150. This is significantly more than the number of particles in the universe. Moreover, if the computer can handle 1010 primes per second, the calculation would take around 3×10130 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×10127 years – a very large savings!) Clearly, better methods are needed. Some of these are discussed in this section.

A very basic idea, ...

Get Introduction to Cryptography with Coding Theory, 3rd Edition now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.