Let’s look at the Internet code in action, but with very small p and q so that we can easily follow what’s going on. We’ll say that for his soccer-shirt website, Bob has chosen the primes 3 and 11, so that the public clock calculator that customers must use to encrypt their credit card number has 33 hours on it. Bob keeps the primes 3 and 11 secret because they are the key to decoding messages, though he makes the number 33 public because this is the number of hours on his public clock calculator. The second piece of information made public on Bob’s website is the encoding number E —let’s say it’s 7. Everyone who buys a shirt from Bob online is doing exactly the same thing: raising their credit card number to the power 7 on a 33-hour clock calculator.
Bob’s soccer-shirt website is visited by a customer who was one of the first ever recipients of a credit card, and its number is 2. Raise 2 to the power 7 on the 33-hour clock calculator, and you get 29.
Here’s a clever way to calculate 27 on the 33-hour clock calculator. We need to start multiplying 2s together: 22 = 4, 23 = 8, 24 = 16, 25 = 32. As we go to higher powers of 2, the hand on the clock winds farther around the clock face, and when we get to multiply by 2 for a sixth time, the hand is doing more than a whole revolution. There’s a little trick we can do here that makes it look as though the clock hand is reversing its direction rather than spinning around farther. We simply say that 32 o’clock on our 33-hour clock calculator is –1 o’clock. Then, after we’ve gotten to 25 = 32, two more multiplications by 2 will get us to –4, or 29 o’clock. This way, we are spared having to calculate 2 to the power 7—that is, 128—and then finding the remainder upon dividing by 33. For very big numbers, this sort of saving is invaluable for a computer trying to calculate things quickly.
Figure 4.17 Calculating powers on a 33-hour clock calculator.
How can we be sure that the customer’s encrypted number, 29, is secure? After all, a hacker can see this number travelling through cyberspace and can easily look up Bob’s public key, consisting of the clock calculator with 33 hours and the instruction to raise the credit card number to the power 7. To crack this code, all the hacker needs to do is find a number that, multiplied together 7 times on the 33-hour clock calculator, gives the answer 29.
Needless to say, it’s not that easy. Even with normal arithmetic, squaring numbers can be done on the back of an envelope, but it’s much tougher to undo the process and search for the square root. The extra twist comes from computing powers on a clock calculator. You very quickly lose sight of the starting point because the size of the answer bears no relationship to where you started.
In our example, the numbers are small enough for the hacker to be able to try every variation to find the answer. In practice, websites use clocks in which the number of hours has over one hundred digits, so an exhaustive search is impossible. You may well be wondering how, if it is so difficult to solve this problem on the 33-hour clock calculator, any Internet trading company can recover a customer’s credit card number.
Euler’s more general version of Fermat’s little theorem guarantees the existence of a magic decoding number, D. Bob can multiply the encrypted credit card number together D times to reveal the original credit card number. But you can work out what D is only if you know the secret primes p and q. Knowledge of these two primes becomes the key to unlocking the secrets of this Internet code, because you must solve the following problem on the secret clock calculator:
E × D = 1 (modulo (p – 1) × (q – 1))
When we put in our numbers, we find that we have to solve the equation
7 × D = 1 (modulo (2 × 10))
That’s asking us to find the number that, when multiplied by 7, gives a number with a remainder of 1 upon division by 20. D = 3 will work because 7 × 3 = 21 = 1 (modulo 20).
And if we raise our encrypted credit card number to the power 3, the original card number reappears:
293 = 2 (modulo 33)
Being able to recover the credit card number from the encoded message depends on knowing the secret primes p and q, so anyone wanting to hack the codes on the Internet needs a way to take a number N and crack it into its prime divisors. Every time you buy a book online or download a music track, you are using the magic of prime numbers to keep your credit card secure.
THE MILLION-DOLLAR QUESTION
The code makers are always trying to keep ahead of the code breakers. In case the prime-number code is ever cracked, mathematicians are constantly coming up with ever more clever ways to send secret messages. A new code called elliptic curve cryptography, or ECC for short, is already being used to protect the flight paths of aircraft, and the million-dollar prize for this chapter relates to understanding the mathematics of the elliptic curves behind these new codes.
There are a multitude of different elliptic curves, but they all have equations like y 2 = x +3 + ax ++ b. Each curve corresponds to different values of a and b: for example, a = 0 and b = –2 gives us y 2 = x +3 – 2.
This equation defines a curve that I can draw on graph paper, as shown in the following figure, by finding a succession of points (x, y ). I put in a value of x, and then I calculate the equation x +3 – 2 and take its square root to get the corresponding value of y. For example, if x + = 3, then x +3 – 2 = 27 – 2 = 25. To get y, I need to take the square root of 25, since y 2 = x +3 – 2, so y is 5 or –5 (because minus times minus is plus, there are always two square roots). The graph you get is symmetrical about the horizontal axis because all the square roots have a mirror root that is negative. Here, we’ve found the two points (3, 5) and (3, –5).
Figure 4.18 The graph of an elliptic curve.
Those points on the elliptic curve are very nice because x + and y are both whole numbers. Can you find any other points like this? Let’s try putting x + = 2. Then x +3 – 2 = 8 – 2 = 6, so y = √6 or –√6. In the first example, 25 had a whole number square root, but the square root of 6 is not so tidy. The ancient Greeks proved that there is no fraction, let alone whole number, that when you square it it gives 6. √(6 written as a decimal number races off to infinity with no pattern at all:
√6 = 2.449489742783178 . . .
The million-dollar question relates to finding the points on this curve where both x + and y are whole numbers or fractions. Most of the time they aren’t, because when you put in x, the y won’t be a whole number or even a fraction because most numbers don’t have a nice square root. We were lucky to find that (3, 5) and (3, –5) are nice points on the curve, but are there any others?
The ancient Greeks came up with a beautiful piece of geometry that showed how to get more points (x, y ), where both x + and y are fractions, once you’ve found one. Draw a line that just touches the first point you’ve found—it mustn’t go through it; it must be at just the right angle to glance the curve, as shown in the following graph. We call this line the tangent to the curve at that point. By extending this line, we find that it will cut the curve at a new point. The exciting discovery is that the coordinates of this new point will also both be fractions.
Figure 4.19 How to find more points on the elliptic curve with coordinates that are fractions.
For example, if we draw the tangent at the point (x, y ) = (3, 5) on the elliptic curve y 2 = x +3 – 2, we find that it crosses the curve at a new point, (x, y ) = (), where both coordinates are fractions. With this new point, we could repeat the procedure and get another point where both x + and y are fractions:
Without this bit of geometry, it would be very hard to discover that feeding in the fraction
will give you a y that is also a fraction.
In this example, you can keep repeating this bit of geometry and get an infinite number of pairs of fractions (x, y ) that are points on this curve. For a general elliptic curve y 2 = x +3 + ax ++ b, if you’ve got one point (x +1, y 1) on the curve where both x +1 and y 1 are fractions, then setting
and
will give you another point on the curve where both x +2 and y 2 are fractions.
; For our curve y 2 = x +3 – 2, this generates an infinite number of points on the curve where both x + and y are fractions, but there are curves where it’s impossible to get an infinite number of points. For example, take the curve defined by the equation y 2 = x +3 – 43 x ++ 166. On this curve, it turns out that there are only a finite number of points where both x + and y are whole numbers or fractions:
(x, y ) = (0, 0), (3, 8), (3, –8), (–5, 16), (–5, –16), (11, 32), (11, –32)
In fact, they all have whole-number coordinates. Trying to use the geometry trick or algebra to get more points with fractions just delivers one of these seven points again.
The million-dollar question, called the Birch and Swinnerton-Dyer conjecture, asks whether there is a way to tell which elliptic curves will have an infinite number of points where both coordinates are whole numbers or fractions.
You might say who cares? Well, we all should, because the mathematics of elliptic curves is now being used in mobile phones and smart cards to protect our secrets, as well as in air traffic control systems to ensure our safety. With this new code, your credit card number or message is converted by clever math into a point on this curve. To encrypt the message, the math moves the point around to another point using the geometry just explained to generate new points.
Undoing this geometric procedure requires some math that currently we can’t do. But if you manage it and crack this million-dollar problem, you probably wouldn’t worry about the million dollars, because you’d end up being the most powerful hacker on the planet.
SOLUTIONS
Substitution Cipher Decoded
“A mathematician, like a painter or a poet, is a maker of patterns.
“If his patterns are more permanent than theirs, it is because they are made with ideas. The mathematician’s patterns, like the painter’s or the poet’s, must be beautiful; the ideas like the colours or the words, must fit together in a harmonious way. Beauty is the first test: there is no permanent place in the world for ugly mathematics.”
The cipher is the following:
Table 4.14
An Easy Challenge
It landed heads. 13,068,221 = 3,613 × 3,617. Both 3,613 and 3,617 are primes that have a remainder of 1 upon division by 4. There is a way to factorize this number quickly, using a method discovered by Fermat. If you square 3,615, you get 13,068,225, which is 4 away from 13,068,221. 4 is also a square. Now, if you use a bit of algebra that tells you that a 2 – b 2 = (a + b ) × (a – b ), you get
13,068,221 = 3,6152 – 22 = (3,615 + 2) × (3,615 – 2) = 3,613 × 3,617.
Five
THE QUEST TO PREDICT THE FUTURE
If time travel were possible, it would be easy to predict the future—I could just come back from next year and tell you what happens. Sadly, though, we don’t yet know how to travel through time, and many of the ways in which people claim to be able to predict the future, such as gazing into crystal balls or casting horoscopes, are complete mumbo jumbo. If you really want to know what’s going to happen tomorrow, next year, or far into the next millennium, your best bet is mathematics.
Mathematics can predict whether the earth will be hit by an asteroid and how long the sun will keep burning. But there are still some things that even mathematicians find hard to forecast. We have the equations to explain, for example, the weather, population growth, and the turbulence behind a soccer ball moving through the air, but some of those equations we don’t know how to solve. The million-dollar prize for this chapter will go to the person who can crack the equations of turbulence and predict what will happen next.
The ability of mathematics to predict the future has given those who understand the language of numbers immense power. From the astronomers of ancient times who could predict the movements of the planets in the night sky to the hedge fund managers of today who predict movements of prices on the stock market, people have used mathematics to take a peek into the future. The power of mathematics was recognized by St. Augustine, who warned, “Beware of mathematicians, and all those who make empty prophecies. The danger already exists that the mathematicians have made a covenant with the Devil to darken the spirit and to confine man in the bonds of Hell.”
While some modern math is admittedly devilishly hard, rather than keeping us in the dark, its practitioners are constantly on the lookout for new ideas to shed light on future events.
HOW DID MATH SAVE TINTIN?
In Hergé’s comic-strip book Prisoners of the Sun, the young Belgian reporter Tintin is taken prisoner by an Inca tribe after he strays inside the Temple of the Sun God. The Incas condemn Tintin and his friends Captain Haddock and Professor Calculus to be burned at the stake. The fire is to be lit by a magnifying glass that will focus the sun’s rays onto the pile of wood. Tintin is, however, allowed to choose the time of their death. But can he use this favor to save himself and his friends?
Tintin does the math and learns that a solar eclipse will hit the area in a few days’ time, so he chooses the time of their death to coincide with the eclipse. (Actually, someone else did the math; he saw the prediction in a newspaper cutting.) Shortly before the eclipse is due, Tintin calls out, “The Sun God will not hear your prayers! O magnificent Sun, if it is thy will that we should live, give us now a sign!” And just as the math predicted, the sun disappears and the terrified tribe releases Tintin and his friends.
Mathematics is the science of spotting patterns, and that’s how math gives us the power to look into the future. Early astronomers gazing at the night sky soon realized that the movements of the moon, sun, and planets repeat themselves. Many cultures use these celestial patterns as a way of keeping track of the passing of time. Many different calendars are possible because the sun and moon dance to a crazy syncopated rhythm as they make their way across the sky, but one thing these calendars have in common is the role of mathematics in making sense of the cycles of the moon and the sun to mark time. What’s curious is the role played by the number 19 in determining when moving holidays like Easter are celebrated each year.
The basic unit of time common to all these calendars is the 24-hour day. This isn’t the time it takes the earth to spin once on its axis—that’s a little less: 23 hours, 56 minutes, and 4 seconds. If we were to use this slightly shorter period as the length of a day, our clock and the rotating earth would get more and more out of sync as all those extra 3 minutes and 56 seconds accumulated, until eventually, noon on the clock would happen at midnight. So for timekeeping purposes, we define a day—or, to use the correct term, a solar day—as the time it takes the sun to return to the same position in the sky as seen from the same point on the earth’s surface. After one complete rotation, the earth will have moved around its orbit by about of a revolution, so it takes about of a rotation, or another of a day—about 3 minutes and 56 seconds—for the sun to return to the same point in the sky.
To be a little more precise, the earth takes 365.2422 of these solar days to go once around the sun. The Gregorian calendar, the one used by most countries, is based on a close approximation to this cycle. 0.2422 is almost a quarter, so by adding an extra day to the calendar every four years, the Gregorian calendar keeps in pretty good step with the earth’s movement in its orbit around the sun. A few tweaks are required because 0.2422 isn’t quite 0.25: every one hundred years, we miss out on a leap year, and every four hundred years, we skip the skipping and retain the leap year.
The Islamic calendar uses the cycle of the moon instead. Here, the basic unit is a lunar month, and 12 of these make up a lunar year. A lunar month, the beginning of which is determined by the sighting of the new moon at Mecca, is about 29.53 days, making a lunar year 11 days shorter than a solar year. 365 divided by 11 is approximately 33, so it takes 33 years for the month of Ramadan to cycle its way through the solar year, which is why Ramadan slips through the year as reckoned by the Gregorian calendar.
The Jewish and Chinese calendars mix and match, using the cycle of the earth’s orbit around the sun an
d the cycle of the moon’s orbit around the earth. They do this by adding a leap month roughly every third year, and the key to the calculations is the magic number 19. Nineteen solar years (= 19 × 365.2422 days) almost exactly matches 235 lunar months (= 235 × 29.53 days). The Chinese calendar has seven leap years in every 19-year cycle to keep the lunar and solar calendars in sync.
The number 19 would have been important in Tintin’s calculations because the sequence of eclipses of the sun and moon also repeats itself after 19 years. This episode in Prisoners of the Sun is based on a famous moment in history, when the explorer Christopher Columbus used a lunar eclipse, rather than a solar eclipse, to save his crew when they were stranded on Jamaica in 1503. The local inhabitants were friendly at first but eventually became hostile and refused to supply Columbus and his crew with provisions. With his men facing starvation, Columbus came up with a cunning plan. He consulted his almanac—a book that contained predictions of tides, lunar cycles, and positions of stars used by sailors for navigation—and discovered that a lunar eclipse was due on February 29, 1504. Columbus summoned the locals three days before the event and threatened them: if they didn’t supply him with provisions, he would make the moon disappear.
No supplies turned up—the locals didn’t believe that Columbus had the power to make the moon disappear. But on the evening of February 29, when the moon rose above the horizon, they could see that a piece had already been bitten out of it. According to Columbus’s son Ferdinand, as the moon faded from the night sky, the natives became terrified, and “with great howling and lamentation came running from every direction to the ships laden with provisions, praying to the Admiral to intercede with his god on their behalf.” By precise calculation, Columbus timed his pardon of the locals to coincide with the moon’s gradual reappearance. This story might be apocryphal or embellished by the Spanish to contrast the clever European conquerors with the ignorant locals. But at its heart, it shows the power of mathematics.
The Number Mysteries: A Mathematical Odyssey through Everyday Life Page 19