Epilogue: Efficient Prime Finding Algorithms Are Central to Modern Computing

The sieve of Eratosthenes slaps

In the code-alongs, we implemented TrivialPrimeFinder() and SieveOfEratosthenes(). The table below contains the run times of our implementation for a variety of different input values of n for these functions. Each row of this table also contains the speedup obtained from running SieveOfEratosthenes(), which is the ratio of the running time of TrivialPrimeFinder() against this faster approach.

You will notice a manifestation of a general rule in the table above, which is that the larger an input dataset we provide to two algorithms, the greater the speedup for the faster algorithm. We hope that you now see why speed is such an important consideration when designing algorithms, especially in the modern era, as the amount of data that we are generating is growing at an ever-faster rate, so we need fast algorithms more than ever before.

Even given the clear need for efficient algorithms, it may not seem as though prime numbers have any relevance to modern computing. And yet the ability to find large prime numbers quickly is central to a fundamental development in computer science called public key cryptography that we use every day.

Public key cryptography depends on finding primes

A fundamental property of the internet is that when you transmit a message (email, bank transaction, or even a private Google query), this message should be understood by the recipient, but not by anyone else who may be eavesdropping on the transmission. We therefore need to encrypt, or transform the message in some way, so that only the desired recipient can decrypt the transmission on the other end of the channel to reveal the original message.

Most encryption schemes that we might imagine are called symmetric, meaning that we use the same approach for encrypting and decrypting the message, called a key. For example, say that we encrypt a word by taking the next letter in the alphabet for each character, so that HELLO becomes encrypted as IFMMP. This key is symmetric because we can decrypt a message by taking the previous letter in the alphabet at each position. Although a code-breaker could quickly unravel this scheme, there is a much greater problem that arises for symmetric encryption approaches, which is that the key is private; the sender and receiver must agree upon the scheme in advance, since sending it on a public channel would defeat the purpose of encryption altogether. Private-key approaches are generally useless online, where we cannot meet the recipients of our messages in person. Private keys also present an apparent catch-22: the key itself is a message that we want to hide from eavesdroppers.

This straightforward problem of information-hiding seemed unsolvable for most of human history, until the late 1970s, when three mathematicians devised a new encryption scheme based on a public key. Their critical insight was that knowing the key used for encryption does not automatically imply that it is easy to decrypt the message, if the recipient knows certain additional details about the key.

This may sound mystical, but say that the recipient picks two very large prime numbers p and q (they may be around 300 digits long in practice), and form n = p · q, which they publish as the public key. Without getting into the details of how the encryption is performed, the key will be asymmetric in that knowing n does not help an eavesdropper know how to decrypt the encrypted message; the only way to decrypt the message is to know the primes p and q. No one has ever found an algorithm that can quickly factor a very large number n, and so someone listening in on the channel who sees the encrypted message will not be able to determine p and q; the recipient, on the other hand, knows these numbers and can decrypt the encrypted message quickly.

Public key cryptography exemplifies a seminal idea in computer science that rests on a foundation of beautiful mathematics. In the next chapter, we will see how computation can be used to find answers to biological questions without needing to run a single experiment, and we hope that you will join us.

Time for extra practice

This brings our chapter to a close. But there is still so much to do! It’s now your turn to apply what you have learned to new contexts and solve some fun exercises involving integers.