A popular encryption scheme
In August 1977, three researchers wrote an article for a mathematical curiosities column in the Scientific American magazine [2]. The article described what has come to be known as RSA encryption, so named after its originators—Rivest, Shamir, and Adelman. The idea behind RSA is that multiplying numbers is easy, but factoring numbers is difficult. In Figure 9.1, we get a 100-digit number by multiplying two 50-digit numbers:
Figure 9.1 – The RSA-100 number
When I presented this multiplication problem to my laptop computer, I got the answer almost instantly. Multiplying two numbers, however large they may be, isn’t challenging for today’s hardware.
But what if we try to solve the problem in reverse? What if we start with the 100-digit number at the bottom of Figure 9.1, and ask a computer to find the two 50-digit numbers at the top of the figure? When I handed this task to a respected mathematics...
