To contact us Click
HERE
A three-hour movie begins at 11am. When does it end? In countries like the US that use a twelve hour clock, we say it ends at 2pm, even though 11 + 3 = 14. This is a first example of
modular arithmetic, a simple and beautiful generalization of ordinary arithmetic that underlies much of modern cryptography and your ability to safely conduct financial transactions on the web.
One of the first multiplication facts you learn in school is 12 = 3*4. Numbers that can be
factored into smaller pieces this way are called
composite. Not all numbers are composite; those that are not are called
prime. 13 is prime, because if it did have factors, at least one would be smaller than 4 (since 4*4 is 16, which is already too big), yet neither 2 nor 3 works.
Subtle connections between modular arithmetic and prime numbers led to the invention of
public key codes, which have all sorts of uses, including allowing people to digitally sign documents and to verify that the documents have not been tampered with during transmission.
Today we are going to start at the beginning and explore how modular arithmetic works and how it connects with prime numbers. By the end you will understand how public key codes perform their magic, all without any math beyond multiplying whole numbers.
In clock arithmetic, also called arithmetic
mod 12, any time weadd two numbers and the sum goes over twelve, we subtract twelve fromthe answer to bring it back into the standard range 1..12. Actually,mathematicians prefer to use 0..11 as the standard range, and we willadopt that convention here as well. It just means that when you see 12as the answer, you subtract 12, leaving zero.
For example, 3+4=7 mod 12, just as it does in "ordinary" arithmetic,but 11+4=3 mod 12, because the ordinary sum is 15, and then wesubtract 12, leaving 3.
This sort of thing works even if we add more than two numbers:11+11+11+11 = 8 mod 12, because the ordinary sum is 44, andsubtracting 36 (three repetitions of twelve) leaves 8.
A quick way to do this last result in your head is to think of 11 as-1, so four copies added together is -4, which is also 8. Why doesthis work? Remember that 12 and 0 are the same thing, so starting from12 and subtracting one (to get 11) is the same as starting from zeroand subtracting one (to get -1).
Here is the
addition table for arithmetic mod12. Unlike the ordinary version you learned in school, which is just asmall piece of an infinitely large set of addition facts, this tableis
complete: the numbers 0..11 are the only ones that are"allowed" in mod 12, so there are no other addition facts to memorize!
| Addition Mod 12 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 |
| 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 |
| 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 |
| 5 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 |
| 6 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 |
| 7 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 8 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 9 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 10 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 11 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
The upper left portion of this table should look very familiar; it isthe ordinary addition table for small numbers. Note the symmetries:every diagonal that runs north-east to south-west is constant. Inparticular, the upper right triangle is mirror symmetric to the lowerleft triangle, which means addition is
commutative: a+b = b+a,just as for ordinary addition.
I colored all the zero results violet, and all the ones lightblue. These highlight the new feature of modular arithmetic: wherewe would ordinarily have a 12, we put zero, and continue from therewith 1, 2, 3, instead of 13, 14, 15.
As mentioned above, 11+1 = 0 mod 12, so 11 acts like -1. Pairsthat sum to zero that way are called
additive inverses. Icolored the zeros violet to help us spot inverses. For instance, inmod 12, the (additive) inverse of 10 is 2, or equivalently, 10 actslike -2 in ordinary arithmetic.
Now let's make a multiplication table mod 12. We find amuch more complicated pattern: look at the jumble of violet cells in the middle!
| Multiplication Mod 12 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 2 | 0 | 2 | 4 | 6 | 8 | 10 | 0 | 2 | 4 | 6 | 8 | 10 |
| 3 | 0 | 3 | 6 | 9 | 0 | 3 | 6 | 9 | 0 | 3 | 6 | 9 |
| 4 | 0 | 4 | 8 | 0 | 4 | 8 | 0 | 4 | 8 | 0 | 4 | 8 |
| 5 | 0 | 5 | 10 | 3 | 8 | 1 | 6 | 11 | 4 | 9 | 2 | 7 |
| 6 | 0 | 6 | 0 | 6 | 0 | 6 | 0 | 6 | 0 | 6 | 0 | 6 |
| 7 | 0 | 7 | 2 | 9 | 4 | 11 | 6 | 1 | 8 | 3 | 10 | 5 |
| 8 | 0 | 8 | 4 | 0 | 8 | 4 | 0 | 8 | 4 | 0 | 8 | 4 |
| 9 | 0 | 9 | 6 | 3 | 0 | 9 | 6 | 3 | 0 | 9 | 6 | 3 |
| 10 | 0 | 10 | 8 | 6 | 4 | 2 | 0 | 10 | 8 | 6 | 4 | 2 |
| 11 | 0 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Can you see the pattern here?
As in ordinary arithmetic, multiplying anything by zero gives zero, sothe first row and column are violet. But any combination whose productwould have been 12 (or a higher multiple like 24, 36, 48, 60, etc.) alsoturns into zero, when we work mod 12. So for example, 3*4=0 mod 12,resulting in a violet cell in the table. In fact, all the "extra"violet cells involve a product that produces a 12, like2*6, or a higher multiple, like 6*10.
Despite the jumbled appearance, there is still a mirror symmetry between the upperright and bottom left of the table: multiplication, like addition, is
commutative, meaning order does not matter: 5*7 = 7*5, both inordinary arithmetic and in modular arithmetic, and in general, a*b =b*a regardless of what numbers we use for 'a' and 'b'.
Let's compare this to the multiplication table mod 13. Arithmetic mod13 works the same way as mod 12, except that now the allowed numbersare 0..12, and we subtract 13 as needed to get larger numbers into thestandard range. The addition table has the same nice diagonal patternas in the mod 12 table, so I won't show it again. But themultiplication table mod 13 looks quite different than the mod 12version.
| Multiplication Mod 13 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 2 | 0 | 2 | 4 | 6 | 8 | 10 | 12 | 1 | 3 | 5 | 7 | 9 | 11 |
| 3 | 0 | 3 | 6 | 9 | 12 | 2 | 5 | 8 | 11 | 1 | 4 | 7 | 10 |
| 4 | 0 | 4 | 8 | 12 | 3 | 7 | 11 | 2 | 6 | 10 | 1 | 5 | 9 |
| 5 | 0 | 5 | 10 | 2 | 7 | 12 | 4 | 9 | 1 | 6 | 11 | 3 | 8 |
| 6 | 0 | 6 | 12 | 5 | 11 | 4 | 10 | 3 | 9 | 2 | 8 | 1 | 7 |
| 7 | 0 | 7 | 1 | 8 | 2 | 9 | 3 | 10 | 4 | 11 | 5 | 12 | 6 |
| 8 | 0 | 8 | 3 | 11 | 6 | 1 | 9 | 4 | 12 | 7 | 2 | 10 | 5 |
| 9 | 0 | 9 | 5 | 1 | 10 | 6 | 2 | 11 | 7 | 3 | 12 | 8 | 4 |
| 10 | 0 | 10 | 7 | 4 | 1 | 11 | 8 | 5 | 2 | 12 | 9 | 6 | 3 |
| 11 | 0 | 11 | 9 | 7 | 5 | 3 | 1 | 12 | 10 | 8 | 6 | 4 | 2 |
| 12 | 0 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
There are no violet cells outside the first row and first column! That isbecause 13 is prime, so there are no combinations a*b that equal13. In fact, because 13 is prime, there are not even any combinationswith a*b equal to a multiple of 13, like 26 or 39, unless either a orb itself is a multiple of 13, and that never happens since 12 is thelargest allowed value.
Moreover, this time every row and column has a light blue 1 in itsomewhere (ignoring the first row and first column, which are just multiplication by zero). Thatis quite interesting. Just as summing to zero gave us a version of"negative" numbers, multiplying to yield one gives us a version of"fractions". If a*b=1, we say that a and b are
multiplicative inverses. In ordinary arithmetic, this requires fractions: themultiplicative inverse of 5 is 1/5, which is not a whole number. Inthe mod 12 world, only four numbers had inverses, and they were allself-inverses at that: 1*1=1, 5*5=1, 7*7=1,and 11*11=1. But in mod 13,
every number (except zero) has aninverse, and they follow quite a jumbled looking pattern.
For example, the (multiplicative) inverse of 2 is 7, because 2*7=1 mod 13 (normally2*7=14, but subtract 13 to get 1). The inverse of 3 is 9, because 27is one more than 26, which is a multiple of 13. And so on, withoutmuch pattern other than the fact that
every row and columnhas exactly one light blue cell.
In fact, the mod 13 multiplication table has a lot in common with a giant Sodokupuzzle: again ignoring the violet row and column, we see that each ofthe numbers 1..12 shows up exactly once in every row and everycolumn. That means that any given row or column isa
permutation (i.e. a shuffling or re-ordering) of the numbers1..12. This is quite different from the mod 12 case, where certainnumbers, like 0, showed up far too often, and other numbers, like 1,showed up too infrequently.
Now let's think for a minute about cryptography. A good cipher system must behard to break, but it must also be
possible to decode it,otherwise it is useless. This means it must involve permutations, likemultiplication mod 13 does, rather than transformations that"collapse" information, like multiplication mod 12.
To see what I mean, consider the ancient (and way too simple to besecure) Caesar Cipher. This involves permuting the letters of the alphabet byshifting each one forward a set amount, such as by 3 letters. Forexample, we could encrypt "THE EAGLE" as "WKH HDJOH" by moving the T threeletters forward past UV to W, the H three letters forward past IJ toK, the E three letters forward to H, and so on.
Because the Caesar Cipher involves a permutation, it can be decoded byreversing the permutation, i.e. shifting three letters back. Thus Wshifts back to T, K to H, H to E, and so on.
In contrast, consider a "cipher" that encodes consonants as A andvowels as B. We could encrypt "THE EAGLE" as "AAB BBAAB", but we wouldhave a problem if we try to decrypt it. There is no way toknow
which consonant any given A stands for, or which vowel anygiven B stands for, except through accidents of English spelling. It is a little tricky thinking up examples, but thanks toRegex Dictionary, using the"regular expression" search pattern
^[^aeiou][^aeiou][aeiou]$
we find that AAB could mean TWO or WHO, not just THE. If we count 'y' as aconsonant, AAB could mean BYE, DYE, or LYE. If 'y' is a vowel, itcould mean CRY. And so forth.
So ciphers need to involve permutations. Now, modern ciphersare much more complicated than just shifting individual letters. Computers represent everything as bits (zeros and ones). A message is just along string of bits.
Block ciphers like the USGovernment's
Advanced Encryption Standard (AES) take 128 (or256 etc.) bit chunks at a time and perform numerous arithmetic andbit-permuting operations on them to mix them up. The user specifiesa
key, i.e. a password, which controls
which permutationis used, much like the number 3 acted as the "key" in our earlier Caesarcipher example. The recipient ofthe message, who also knows the key, uses it to reverse thepermutations, thereby decoding themessage. A Stick Figure Guide to the Advanced Encryption Standard providesa fun "cartoon" introduction to the details of the permutationalgorithm, if you are curious.
Block ciphers like AES are very efficient and very secure.However, block ciphers have one major drawback. Both the sender andthe recipient of the coded message need to have
advanceknowledge of the key - yet the key must be secret to prevent any thirdparty from intercepting, reading, or modifying thetransmission.
Suppose "Alice" wants to buy from a web site that "Bob"runs. She needs the communication encrypted so people cannot find outher credit card number. But she cannot just send Bob an AES key forthem to use to encrypt the session, since the key itself also needs tobe protected!
Enter "public key" codes. These combine modular arithmetic andprime numbers in such a way that Alice and Bob can indeed agree ona secret AES key, even though they have never met and initially haveno shared secret to use as the key.
Security is actually a bit more complicated then just the encryption part. We alsoneed
protocols that can for instance prevent "replay attacks",where an eavesdropper who cannot decode your message nonetheless cancopy it and resend the copy at a later time. Think about a messagethat withdraws money from your bank - such as gets transmittedwhenever the bank processes a check you wrote - you don't want someonereplaying that and transferring the money twice, even if they cannotdecode or alter the message directly. Fortunately, once you havegood encryption, you can define appropriate protocols to preventthis (e.g. including a unique transaction number as part of themessage, thus allowing duplicate messages to be detected),so we will focus on the encryption and leave protocols for another discussion.
To understand how public key encryption works, we need onemore arithmetic operation. So far, we have looked at the modular arithmeticversions of the addition table and the multiplication table. Theoperation we need now is
raising to a power. Suppose we startwith the number 6 in the mod 13 system. If we multiply it by itself,we are raising it to the second power (
squaring it), and we get6*6 = 36 = 10 mod 13, because 26 is a multiple of 13.
Next, let's multiply together three copies of 6. This is calledraising it to the third power, or
cubing it. We get 6*6*6 = 8mod 13, because 6*6*6 = 216, and 208 is a multiple of 13. However,there is an easier way to get this result. We already know that 6*6 =10 mod 13, so 6*6*6 is the same as 10*6 = 60 = 8 mod 13, because 52 isa multiple of 13.
We can keep going this way, as shown in the following table. We willuse the notation 6^n to mean n copies of 6 multiplied together, so 6^2= 6*6 and 6^3 = 6*6*6. Just like addition is repeated counting, andmultiplication is repeated addition, raising to a power is just repeatedmultiplication. Here are the powers of 6 in mod 13 arithmetic:
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 6^n mod 13 | 6 | 10 | 8 | 9 | 2 | 12 | 7 | 3 | 5 | 4 | 11 | 1 |
There is a very special feature to this table: it goes all the way ton=12 before we get a result of 1. That makes 6 a
primitive rootof mod 13 arithmetic: in other words, a number whose powers generateall the values (except of course zero).
Not every modular arithmetic has primitive roots. For example, in mod12, if you try raising numbers to powers, you will find that none getvery far. For example, the powers of 2 are 2, 4, 8, but then theyrepeat back to 4, 8, 4, 8, forever. When you think about it,multiplying even numbers together yields even numbers, and since 12 iseven, the result stays even after converting mod 12. So we will neverget 5, or 1, as an answer. But odd numbers also turn out to fail: forexample, 7*7 = 1 mod 12, which means we get a repeating sequence 1, 7,1, 7.
Gauss (a very famous mathematician of the early 1800's) showedthat we can always find a primitive root if we do arithmetic mod pwhere p is a
prime, like 13 or 17. For example, 10 is aprimitive root mod 17. It is not the only one; you can verify forinstance that 5 is also a primitive root mod 17, and that 13 is not.
We now know enough to describe the Diffie-Hellmanpublic key code. Alice and Bob agree to use a specific prime number pand a specific primitive root r mod p. These numbers do not need to bekept secret, although the prime p does need to be
large: largein the sense that writing p in decimal form might involve 300 digits,rather than just two (as in the case of the primes like 13 or17). They will perform all their arithmetic mod p.
Alice chooses a
large random number 'a', and Bob
independentlychooses a large random number 'b'. Here large means that 'a' and 'b' areperhaps 100 digits long: smaller than p, but still much larger thanordinary numbers, so their web browser programs will need special codeto do the calculations accurately. Independent means Bob and Alice do not need tocommunicate to make their choices: they each choose on their own, soAlice does not know 'b' and Bob does not know 'a'. Random means the choice isunpredictable to outsiders: it might depend on the timing ofall the keystrokes on their computers over the past day, measured inmicroseconds. As a result,
only Alice knows 'a',and
only Bob knows 'b', even if someone eavesdrops on theirconversations.
Alice now sends the number r^a mod p to Bob. Bob, at the same time, sendsthe number r^b mod p to Alice. Again, all of this can be done in "plaintext": these are just random looking large numbers, and no harm is done ifsomeone else eavesdrops on them.
Now for the simple but critical fact that makes it all work: (r^a)^b =(r^b)^a, because both sides are just r^(a*b). In other words, orderdoes not matter for repeated exponentiation (just as it does notmatter for multiplication), because both sides are just a*b copies ofr multiplied together. And the same is true even if we work mod p.
Since this point is central, let's do an example for clarity. Consider(5^3)^2. We start inside parentheses with 5^3 = 5*5*5, then wesquare this, which means we multiply it by another copy of 5*5*5. Thusaltogether we have to calculate 5*5*5 * 5*5*5. That is six copies of 5multiplied together, or 5^6. If we reverse the order, and look at(5^2)^3, we get 5*5 inside parentheses; now we cube it, i.e. wemultiply three copies of 5*5 together, forming 5*5 * 5*5 * 5*5, whichagain is just six copies of 5 multiplied together, or 5^6. So we getthe same answer either way.
Because of this, if Alice takes the number r^b mod p she received fromBob, and raises it to the power 'a' (using her own secret number 'a'),she computes r^(a*b) mod p. And if Bob takes the number r^a mod p thathe received from Alice, and raises it to the power 'b' (using his ownsecret number 'b'), he too computes r^(a*b) mod p. This means thatAlice and Bob now
share a secret, namely the large and randomlooking integer r^(a*b) mod p.
Alice and Bob can now use this shared secret as their AES key. Nowthey can have an extended conversation encrypting as much informationas they need to complete the purchase process. They don't needpublic key encryption any more; that was just used to provide themwith a shared but secret AES key. That is fortunate, because modulararithmetic on 300 digit numbers is slow compared to using AES toscramble the bits of the real message.
Again, the actual process inside your web browser is a little morecomplicated - there are some additional protocols to ensure that noone replays their communication, or modifies it without theirknowledge - but all of these extra steps are predicated on this basicability to get Alice and Bob to share a secret without in fact havingto communicate it directly.
Why did we need the mod p stuff? Why not just use regular arithmetic?I'm glad you asked. Doing everything mod p is precisely what makes theprocess secure. Suppose we use ordinary arithmetic. Suppose aneavesdropper "Eve" listens in on the conversation. When she receivesr^b, she can reverse the process by taking logarithms: the log base rof the number she received is just 'b', and calculating logarithms iseasy for a computer. Once she knows 'b', she can take the r^a value(which like r^b was sent un-encrypted) and raise it to the power 'b',thereby computing the secret key. Now she will be able to listen toand decode the entire subsequent purchase transaction, since she knowsthe AES key; she can also encrypt her own messages with the same keyand potentially trick Alice and Bob into believing they are legitimate.
What's different when we do this mod p? Only one thing: taking alogarithm mod p turns out to be extremely difficult, even for thefastest known computer algorithms. So,
provided no one invents a fastway to solve the
discrete logarithm problem (a reasonably safebet, since many smart people have been (unsuccessfully) attempting itfor several decades now, for obvious reasons), the time required tobreak this sort of code grows
exponentially in the number ofdigits involved. That is why the prime p needs to be at least 300 digits long,and 'a' and 'b' need to be at least 100 digits long: by using really bignumbers, we can make breaking the code take an arbitrarily long time.
Computers do get faster every year, and a well fundedeavesdropper (like a national government) could run a bunch ofcomputers in parallel to speed up the attempt, butthe process works well enough for now. That's because exponentialgrowth is really fast - as you may recallfrom Powers of Two Back in Time, one can go from a time scale of seconds toa time scale of the age of the universe in just 59 powers of two. Soby using enough digits in p, a, and b, one can literally ensure thatall the computers in the world could not break the code in a millionyears.
Someone
might discover a fast algorithm for discretelogarithms. No one knows whether such an algorithm is even possiblefor
ordinary computers, let alone how it would work, but a fastalgorithm
is known for
quantum computers. Fortunately,quantum computers are just in their infancy, and are not yet practicalon a large scale. In addition, there are apparently public key codesthat use tricks for which fast quantum algorithms do not (yet)exist. So at least in the short run, our present systems givereasonable security
in theory.
Of course, there are some caveats in practice. There is an almostlimitless number of things that can go wrong "outside the box". Ifyour web browser or the server web site has been compromised in somefashion, e.g. by a computer virus, or by an improperly programmedprotocol, then the communication may be insecure. Or, take the case ofthe recent Iranian capture of an American drone airplane. Accordingto Bruce Schneier's blog onSecurity, Iran did not break the encryption for controlling the drone:instead, they claim they just jammed the drone's access to GPS navigationsignals, which apparently forced it to make an emergencylanding. Similarly, criminals who want to get your bank passwordapparently focus less on trying to break the encryption than onsimpler techniques like sending you "phishing" emails that attempt totrick you into typing your password directly into their fake website.
So there we have it: modular arithmetic and prime numbers areat the heart of our modern "e-commerce" system of secure web sites,thanks largely to the "magic" of public key cryptography. Mathematically,they work extremely well, although staying secure in practice is amuch harder problem!
If you liked this article, you may also like Why are there exactly five Platonic solids?, or perhaps Counting and Number Systems.
Please post questions, comments and other suggestions using the box below, or email me directly at the address mentioned in the Welcome post. Remember that you can sign up for email alerts about new posts by entering your address in the widget on the sidebar. If you prefer, you can follow
@ingThruMath on Twitter, where I will tweet about each new post to this blog. The Contents page has a complete list of previous articles in historical order. Now that there are starting to be a lot of articles, you may also want to use the 'Topic' and 'Search' widgets in the side-bar to find other articles of related interest.
I hope you enjoyed this discussion. You can click the "M"button below to email this post to a friend, or the "t" button toTweet it, or the "f" button to share it on Facebook, and so on. Seeyou next time!
The Associated Press ran a story summarizing thenew report from the Intergovernmental Panel on Climate Change.The report uses careful language to clarify the strength of the evidencefor each of its conclusions. The relevant quote for us is:
I have labeled the vertical scale "hypothetical" frequency toemphasize that this is not a plot of real temperature data.It is just a "bell shaped curve" designed to illustrate the ideas. The black line represents the original 20th century climatefor some hypothetical location, with an average temperature of 40degrees. The taller parts of the graph correspond to the more commontemperatures: in this location, most temperatures are between 0 and80, with temperatures as low as -40 or as high as +120 extremely rare. The red line represents the climate at some future point whenthe average temperature has risen 5 degrees, to 45. In this example,we have not changed the shape of the curve at all: we have simplyshifted it five units to the right (real climate modeling alsoattempts to understand how the shape might change). This makes thetypical temperature range 5 to 85. Temperatures over 100 arerare, since both curves are close to zero near the righthand side of the chart.Now let's now zoom in on the right-most part of the curve: the"right tail", representing the very hottest days.
Look at the blue line. Days over 110 are quite rare (about one in 12years for the black line), but they happen more than twice asoften under the red curve (about one in 5 years). So even a small shift inthe curve (5 degrees out of a typical spread of 80 is about a 6%shift) can produce a large change in extreme conditions (2.5 times asoften, in this example). My example curves were drawn using a "normal" distribution,which is the widely used "bell-curve" shape of classical statistics,but there is no particular reason that real temperature data needs tobe shaped that way. Let's now look at some actual temperature data,and see if we can illustrate a 1-in-20 year event becoming a 1-in-2year event. You can get real temperature readings from many sources. Somecountries make it particularly easy to download large amounts data for free.Australiahas a particularly user friendly site. I downloaded the daily maximumtemperature (degrees Celsius) in Melbourne, station number 086071, forthe years 1868 through 2010, inclusive, which provide 52,230 qualitychecked daily values with no missing values. We will use the following R code to make the graphs. Asdiscussed in many previous posts, you can follow along by downloadingyour own completely free copy of the open source, high quality,statistical programming language R fromThe Comprehensive R Archive Network.
Next, we zoom in on the section above 40 Celsius (104 Fahrenheit):
The sample sizes for extreme events are by definition low,so by nature this sort of prediction isvery sensitive to the exact nature of the shift in the curve(i.e. does it also change its shape, not just slide over), as well asto where we draw the line to denote "extremes". If we choose 42 C (108 F) as out threshold, days that hot orhotter would be expected to occur ten times more often in future thanin the past, because while only 40 past observations were that hot,400 future ones are. If we want to look for a 1-in-20 year event in the historicaldata, we need a temperature threshold that is reached or exceeded only7 times among the 52,230 observations. That is 44.1 C in this data set(the vertical blue line in the last chart). Temperatures reach or exceed thisin the hypothetical future data set 109 times, which is 16 times moreoften, making it an almost every year occurrence!Climate change is a complex subject, and careful data analysisand modeling require great technical sophistication. Nonetheless,these examples illustrate the simple point that while we may not knowthe exact amount of the impact, a relatively small shift in theaverage value of the temperature distribution can indeed produce verylarge increases in the relative frequency of rare events like heat waves.I hope you enjoyed this discussion. You can click the "M"button below to email this post to a friend, or the "t" button toTweet it, or the "f" button to share it on Facebook, and so on.If you enjoyed this topic, you may also like Tracking Hurricane Irene.Please post questions, comments and other suggestions using the box below, or G-mail me directly at the address mentioned in the Welcome post. Remember that you can sign up for email alerts about new posts by entering your address in the widget on the sidebar. If you prefer, you can follow @ingThruMath on Twitter, where I will tweet about each new post to this blog. The Contents page has a complete list of previous articles in historical order. Now that there are starting to be a lot of articles, you may also want to use the 'Topic' and 'Search' widgets in the side-bar to find other articles of related interest. See you next time!
Source: http://en.wikipedia.org/wiki/File:Kencf0618FacebookNetwork.jpgThis is typical of diagrams of social networks: some highlyinterconnected people and groups, but also many others with just a fewconnections. The "six degrees of separation" game works because ofthis structure: pick any two people on the planet, and you will besurprised how often they can be connected by a chain of six "friends":even people who keep to themselves often know someone with a widercircle of friends; one of those may know a "hub" (a person with a verylarge number of connections), and before you know it, you have accessto a great many others through friends of friends of friends. The"Linked In" professional networking site uses the same principle toexpand your list of 100 contacts into hundreds of thousands of people"in your network".Just as before, we can use logarithms. The base ten log of 10^n is 'n',so instead of saying someone has 1, 10, 100, or 1000 friends, we cancould refer to them as being at level 0, 1, 2, or 3 on a"connectedness" scale.The same idea works for income. In the United States, many people havean annual income between $10,000 and $100,000 (10^4 and 10^5). But afew people have much larger incomes: one million dollars a year(10^6), or ten million (10^7) or one hundred million (10^8). Ratherthan writing these in words, or with lots of zeros, it is much moreconvenient to just write the exponents: 4, 5, 6, 7, 8. This isespecially handy if we want to make a graph: we can easily put thenumbers 4 through 8 on the horizontal axis of a graph, but if insteadwe wanted to put 10,000 through 100,000,000, we would have a problem:the vast majority of the US population (the part from ten thousand to one hundred thousand) wouldbe squashed down to a tiny portion of the left end of the axis,indistinguishable from zero. It would be like looking for your houseon a globe of the world: the scales are just too different.We can play the same trick using powers other than ten. In Powers of Two Back in Time, we looked back one second, two seconds,four, eight, and so forth: these are powers of 2, written 2^n to meann copies of 2 multiplied together. The base two logarithm of2^n is just n. We saw that quite modest values of n convert toenormous chunks of time: 2^25 seconds is roughly one year, but 2^35seconds is roughly one thousand years, and 2^45 is roughlyone million years: back to prehistoric times. 2^55 seconds isa billion years, taking us back to the days of single celledorganisms, long before dinosaurs or mammals; and 2^59 seconds is 18billion years, which is larger than the age of the universe: we cannotgo back that far! Once again, rather than write really big numbers,it is easier to talk about the logarithms,since they are familiar sized: often one to ten, certainly less thanone hundred.We end with a more elaborate example, which also uses base two logarithms:musical pitch. Scientists measure the frequency of sound vibrations incycles per second, also known as Hertz (Hz). For example, the lowest(longest and deepest sounding) string at the extreme left end of apiano vibrates 27.5 times per second(see Piano key frequencies at Wikipedia), while the highest (and shortest)string at the extreme right end vibrates 4186 times per second. Thatis a lot faster!If we divide 27.5 into 4186, we get 152.2, which might suggest thatthere should be 152 keys on the keyboard, equally spaced at multiplesof 27.5. This turns out not to be the case.There are actually 88 keys on a piano keyboard, and their frequenciesare not evenly spaced at all. For example, the second note from theleft is at 29.1 Hz, not even 2 cycles per second faster than the 27.5one. But the second to last note on the right is at 3951 Hz, or 235cycles per second slower than the 4186 one.What is going on? It turns out that what the human ear perceives asequal intervals of musical pitch is related to what the mechanicalmeasurement of vibration would see as equal ratios offrequency.For example, every time you go up one octave in pitch,you double the frequency. The lowest note on the piano iscalled A, and the subsequent white keys are called B, C, D, E, F, G,after which they repeat back to A. This second appearance of A isone octave higher than the first. If you play two notes anoctave apart on a conventional western musical instrument like thepiano, they blend very harmoniously. This is because a note withfrequency f also produces frequencies 2f, 3f, 4f, and so on; the notean octave higher produces 2f, 4f, 6f, and so on, which blends inperfectly.William A. Sethares wrote a fascinating book, Tuning Timbre Spectrum Scale. He demonstrates unconventional (synthesized) instruments thatproduce sounds in non-integer ratios (e.g. f, 2.1f). They do not soundgood when you play notes an octave apart, but they do soundgood when played using wider intervals more appropriate to theirsound spectrum. But that's a topic for another day.If we look at all the A keys on the piano keyboard, and write F=27.5for the frequency of the first one, then the frequencies of the othersare at 2*F, 4*F, 8*F, 16*F, and soforth. Here is a littletable that summarizes this:
To be concrete, let's focus on the base two logarithm function, whichwe will abbreviate L. You can review Logarithmsif you are a little rusty on the concept, but do not worry:you won't have to calculate with them yourself. The whole point is tolook behind the curtain and see how the computer does it. All we care about is that L is a curved function, not astraight line, and that there is no simple formula for calculating it,which makes it challenging.Let's start with a graph of the L function. We will create it using R,which (as regular readers will recall) is a free, high quality, opensource programming environment well suited to statistics and relatedcalculations. Read Koch Snowflakes for detailed instructions on downloading andinstalling R. Now run the following code:
Logarithms in any base are zero at x=1. They go down to negativeinfinity as x approaches zero, as shown by the steep part at the left of thegraph. They grow without limit as x grows, but very slowly, asindicated by the relatively flat part toward the right side of thegraph. Recall that L(2^n) is n, so for instance, L(16) is 4, L(32) is5, and L(64) is 6. Even L(1024) is just 10, so the curve grows everflatter as you move further right.Now to the question of computing L. Recall that the basic propertyof logarithms is that they translate multiplication into addition. Insymbols:
So as a first approximation, we could say that L(x) is roughly x-0.95, atleast on the interval from x=1 to x=2 that is our focus. However, thatis not nearly good enough: computer calculations with real numberstypically are accurate to 16 decimal digits, so we should aim forthat as well.However, this gives us an idea. If a straight line was a pretty goodfit, might we be able to find a quadratic that is an even better fit?Indeed we can. In fact, calculus provides a useful tool here, calledTaylor series. A Taylor expansion is just a polynomial that is a"good" fit to the function at a particular point. We can ask for alinear fit, a quadratic fit, or even higher order polynomials. Thehigher the order, the better the match, since the Taylor polynomial isdesigned to match the function value, its slope, and as many higherorder derivatives (e.g. curvature) as it can based on its order.Recall the formula for Taylor series from Calculus:
To use it, we need to know the value of the function and itsderivatives at a specific point x0. To avoid circularity, we assumethat we do not know how to compute logarithms yet, so we need tochoose x0 to be someplace where we know the answers inadvance. Choosing x0=1 works well, since log(1) is just zero.Since we have to calculate derivatives, it is handy to switch to thenatural log function log(x) instead of the base two log L. (Some people write 'ln' for natural log, instead of 'log'.)Since 
The first few terms are a good approximation near x=1.The next chart shows log(x) in black, with thequadratic x-1-(x-1)^2/2 in red.
The red line seems to be a very good fit except near the left andright edges of the chart. It is goodenough that we need to switch to plotting the error, rather thanthe curves themselves, in order to really see what is happening.The next plot therefore shows the error, A(x)-log(x), where A is ourapproximation, here the Taylor quadratic centered at x=1.
Now we can see that the error is smaller near x0=1 than faraway. Even at the edges of the graph it is never more than 0.02 insize. Alas, this is still much too big to be practical.However, we can go further and try a cubic Taylor polynomial. The nextchart adds a red curve to the previous chart. The red curve is theerror when we add the (x-1)^3/3 term to our approximation.
Clearly, the error is smaller, but not enormously so. This suggeststhat to get errors as small as 10^(-16) will require using a lot ofterms in the Taylor series.An easy way to compute Taylor polynomials is to use Maxima,a free, high quality, open source symbolic mathematics programdescribed in detailin Calculus Calculator.The following code computes the 4th order polynomial around x0=1.
Now the vertical scale is 4e-06, which means 4 times 10^(-6), or0.000004. That is a big improvement over the 0.02 we had before, butit suggests that we will still need a lot more terms before wefinally get to 10^(-16) accuracy.Very high order polynomials with large numbers of terms can be numericallyunstable: small amounts of error in the coefficients can get magnifiedinto big errors in the result. Soadding a lot more terms might not actually meet our goal, though it would beworth a try. Also, using lots of terms takes a long time to calculate, so if we couldfind a more efficient process, that would be nice.Is there something else we can try?The inverse of the natural log function is the exponential function'exp'. The Taylor series for exp converges much more rapidly, becausethe coefficients scale like 1/(n!) instead of like 1/n. That suggests wecan use Taylor series to efficiently calculate exp. Once we have donethat, can we use it to somehow find natural logs?Indeed we can. Newton's Method is a powerful algorithm forfinding roots (zeros) of functions. It uses the linear Taylorpolynomial: since f(x) is approximately f(x0)+f'(x0)(x-x0), then iff(x) is zero, we can solve for the root at x = x0 - f(x0)/f'(x0).If the function f is not exactly linear, this newvalue of x will not be exactly the root, but if x0 was a good initialguess, the new x will be an even better approximation to the true root. Thismeans that if we iterate a few times, using
we should quickly reach a very accurate answer.Suppose we want to calculate log(c) for some number c.We choose f(x) = exp(x) - c. This function will be zero when x =log(c). Applying Newton's method means using the iteration
We are pleased to see errors in the 10^(-12) range, a greatimprovement over the 10^(-6) we had with the log function at tenterms. Why the difference? Look at the Taylor series for exp:
Notice the coefficients. The 24 is 4! and the 120 is 5!, so we knowthat by the tenth term, the coefficients are getting verysmall. Therefore, dropping the eleventh and higher order terms doesnot introduce much error. As a result, we can get a highly accurateapproximation to 'exp' just by using a few more terms in this series.We have used graphs of numerical experiments to assess the accuracy ofour approximations. This is of course somewhat circular: if mycomputer did not already have a working version of the log function, Iwould not have been able to make these graphs. The mathematicalside of Numerical Analysis, therefore, consists of proving inequalitybounds on approximations. For example, using Taylor's theorem in theform that includes a "remainder" term allows us to put an upper boundon how large the error can possibly be, even if we do not yet know howto calculate log or exp. That breaks the circularity and gives us (orcomputer designers, anyhow) peace of mind.If you liked this article, you may also like System Dynamics: Feedback Models, or check out the Contents page for a complete list of past topics.Please post questions, comments and other suggestions using the box below, or email me directly at the address given by the clues at the end of the Welcome post. Remember that you can sign up for email alerts about new posts by entering your address in the widget on the sidebar. If you prefer, you can follow @ingThruMath on Twitter, where I will tweet about each new post to this blog. The Contents page has a complete list of previous articles in historical order. Now that there are starting to be a lot of articles, you may also want to use the 'Topic', 'Search' or 'Archive' widgets in the side-bar to find other articles of related interest.I hope you enjoyed this discussion. You can click the "M"button below to email this post to a friend, or the "t" button toTweet it, or the "f" button to share it on Facebook, and so on. Seeyou next time!
