Prime numbers have fascinated me since I was in the ninth grade. I didn't care about the big ones, like the 17 million digit one mentioned here. I was interested in finding a pattern to them. It was in the ninth grade that I read an article in Science Digest about scientists who used a Univac computer to search for a pattern to prime numbers.What they did on this behemoth of a computer was simple, yet elegant. Play along at home.
- Grab pen and paper.
- In the center of the page, write the number 1.
- Continue writing numbers in order in a spiral fashion. You should have something that looks like this:
5 4 3 12
6 1 2 11
7 8 9 10
- Continue the number spiral to be as high as you want.
- When your spiral is complete, circle only the prime numbers: 2, 3, 5, 7, 11, 13, 17, and so on.
You'll begin to see a pattern of diagonal lines develop. (Random numbers would not produce anything remotely close to the illustration below.) The illustration below shows the center of the spiral, 1, in blue. All the white dots represent prime numbers plotted in a spiral, just like we did above in Step 3. So, the scientists were partially successful in finding a pattern, if that's even possible. Something's going on here.
In 1983, I decided to take up the same challenge of looking for a pattern to primes using my zippy Commodore 64. I created my own version of their program and had the same luck, no definite pattern. I tried once again about 15 years ago using my more modern Windows 95 machine. The results? A little different. I altered the program to accept any number between 1 and 1,000,000 to be used as the starting point/center of the spiral. (If you want, you can download my little experiment here. Just unzip it and drag the .exe to the desktop.) Having the number 41 as the center/starting point created a distinct diagonal line. This was no accident. If there is a pattern to primes, I'll find it.
Prime Numbers and Encryption
"A computer cannot generate random numbers." Thank you Mr. London, my ninth grade programming teacher. And he's right. A computer cannot do anything randomly. An algorithm (a set of rules) is used to produce pseudo-random numbers by the computer. For instance, if I were to create and run a program that generates 10 random numbers, close, then re-run the same program, the second set of "random" numbers would be the same as the first. This is because the algorithm that generates the random numbers never changes. This is why lotteries use ping pong balls rather than computers to pick the random numbers. (I could go on about statistics and nothing truly being random, but that's best kept for my personal musings.)
To date, there has never been a pattern found to explain the way prime numbers are generated.
Enter RSA encryption. From Wikipedia, "A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message.
Security of Encryption
With RSA, your public key can be published for anyone to encrypt a message that only you can decipher. Why? Because only you have the private key. It is incredibly difficult for others to figure this out from the public key. Factorization of a large prime number is a glacially tedious process which cannot be automated.
By now you may have guessed that the size of the prime numbers used dictate the strength of the encryption. For example, a message encrypted with 5-digit prime numbers (40-bit encryption) yields over 1 trillion possible results. Using 16-digit numbers (128-bit encryption) generates near infinite possible combinations. What does this mean in the real world? Look at it this way. A 128-bit encryption can take about 11,000 quadrillion years to be cracked via brute force, give or take a few millennia. This is why 128-bit encryption is the standard used to protect sensitive data.