On Primes

Today is the start of 37 years that Linda and I have been together. Actually we've been together longer than that, but the 37th year of marriage begins today.

 Yesterday I wrote about the number 36 and primes and factoring. Thirty-seven can't be factored. It is a prime number. The only multipliers are one and thirty-seven. Recall a prime has no divisors except itself and 1. So 1 x 37 is the only way to get 37. Next year's 38 is not prime. No even number, except for 2, is prime. After all, the definition of an even number is a number divisible by 2. Thirty-nine isn’t a prime either, it’s 3 x 13. Forty is no prime. The next prime in my anniversary count-up is 41.

 There are patterns in prime numbers. If you write out all the numbers in a big list, and then mark out the numbers that are not prime, you will see patterns. Of course, there are a lot of numbers … actually an infinite amount of just the natural numbers, the integers equal or greater than zero. To begin with, you can eliminate every other number … the even numbers. Besides, it is easy to tell if a number is even, even if it is a large number. Recall that the even numbers all end with 0, or 2, or 4, 6, or 8. You can eliminate a few more. Any number ending in 5 (except for 5 itself) can't be a prime because it is divisible by 5. All numbers ending in 0 are divisible by ten, but we already eliminated them as even numbers.

 So that means a prime number, even a very, very large prime number, must end in 1, 3, 7, or 9. Of course, just because a number ends in one of these doesn't make it a prime. For example, 21 ends in 1, but isn't a prime; 21 = 3 x 7. Same with the other numbers I listed. I'll leave finding a counterexample, that is a number ending in 3, 5, 7, or 9 that isn't a prime, as an exercise for the reader. Note you cannot prove a theorem true by example, but you can prove it false.

  
 Determining if a number is prime is more complicated than just examining the last digit. With very large numbers, it can be quite difficult to determine if they are prime or not. But all candidates to be prime must end in those four digits.

 (By the way, 13 is a prime. So is 23, 43, 53, 73, 83, and 103. But 33 is not. It is 3 x 11. Nor is 63 = 3 x 21 or 93 = 3 x 31. Guess the next nonprime ending in 3. Are you starting to see the patterns?)

 There is a deep and rich and ancient and practical use for all this analysis of primes. It is an area of math called "Number Theory." The ancient Greeks originally studied it nearly a thousand years before Christ was born. All through history, number theory has interested some of the greatest mathematicians of all time and a few very talented amateurs. To this day there are unproven conjectures in number theory and, as I've mentioned previously, it is a fundamental foundation to modern cryptography used to make the Internet safe, provide secure communications, and even implement "digital signatures."

 An ancient method of studying the patterns of primes, at least for the first few hundred numbers, was developed long, long ago. It is still used as the basis for determining primes with very large numbers. The "Sieve of Eratosthenes" is an ancient idea still used in modern computer programs.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
   
   
2. Initially, let p equal 2, the first prime number.
   
   
3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These will be multiples of p: 2p, 3p, 4p, etc.; note that some of them may have already been marked.
   
   
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

As a refinement, it is sufficient to mark the numbers in step 3 starting from p², as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p² is greater than n.

Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count up using an increment of 2p in step 3, thus marking only odd multiples of p greater than p itself. This actually appears in the original algorithm.

You can see why this is called a “sieve” because the nonprimes are sifted out.

There’s a lot more to number theory, and it includes a lot of fascinating games and some really deep insight into the mathematical building blocks. Some search for the face of God in these deep, natural insights. Certainly it seems the “numbers” were created by the Lord, not just invented by man; much more of a “discovery” than an “invention.”

There is much, much more to learn, but I’ll just list the first 1,000 primes and let you do a little exploration.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

I mentioned the use of primes in cryptography. Let’s explore that a little. What is needed is for a successful encryption is a “trap door function.” That’s a calculation that is relatively easy to perform, but almost impossible to determine the inverse function. That is, the calculation that would undo the original.

Consider how easy you could multiply two large prime numbers. (Of course, first you need to determine two large prime numbers. Use the “Sieve.”) Let’s take 911 and 857. Now they can easily be multiplied … even easier with a calculator or computer. 857 x 911 = 780,727.

Now for the inverse function: Given a large number that is known to be the multiple of two large primes, determine the two prime factors. Suppose you didn’t know 857 x 911 created 780,727. How would you determine the factors of 780,727? You might even think it could be a prime … it ends in 7. You could start by taking a list of primes and start dividing. You do have to start at the beginning because this could be 13 x 60,057 … (but it isn’t, 780,741 is).

You could solve this problem in an hour or so with a calculator and systematic testing. A computer program would solve it in seconds. OK. Make the numbers bigger. Suppose the two primes are each 64 bit numbers. Those are numbers can be as large as 9,223,372,036,854,775,807. That would take your personal computer months if not years to calculate. A very fast computer might get it in just hours.

However, if the primes used were as large as 256 bits, then, most likely, even the government’s fastest computers couldn’t solve it in less than years of running.

Yet, if you knew one of the factors, you could divide and calculate the other factor in just seconds … or minutes if doing long division by hand.

That’s the magic trap door function. If you use a number that is the multiple of two large primes as an encryption key, no one can guess or “reverse engineer it” easily or … more significantly … quickly! However, if you know one of the prime factors, you can quickly verify the number and determine the other prime.

I won’t go into any more detail as it gets complicated and all mathy and programmy, but you now see the basic idea. Prime numbers and the difficulty of factoring is at the heart of the method.

Wait, how do we know that some smart mathematician hasn’t figured out a shortcut method to factor the large number quickly. Well, we don’t know. But we do know that mathematicians since ancient times have been looking for that algorithm, and apparently have not found it … yet.

So number theory isn’t just for the ivory towers. IBM and the NBS and the NSA and many other interested parties have worked for years to perfect the methods of encryption … all based on the difficulty of factoring large numbers that are the product of two primes.

It was even in the news yesterday that a new algorithm had been found to use for encryption after five years of research. They chose to use an old method known for many years. All that “state-of-the-art” research and we’re back to the ancient ways. That’s why we think these methods are secure.

Do a little “Google” exploration and discover more. Wiki’s an excellent source.