Pete's Log: Prime Envy
Entry #568, (Coding, Hacking, & CS stuff)(posted when I was 22 years old.)
As promised in log entry 506 I shall share detailed notes from the math department grad student seminar entitled "Prime Envy" ... I think Perk wanted detailed notes, but I lost the notebook containing those notes for a while. But it's been rediscovered, and I hope to decipher my notes well enough to make sense.
October 12, 2000: "Prime Envy" by Chris Monico, ND math department. Rebecca Weber invited me to another entertaining math department grad student seminar. It began as the last math seminar I attended: math grad students trying to order pizza. It was a very entertaining process, there was a very close vote between ordering from pizza hut vs. ordering from papa johns. During this time a few choice quotes came up: "he's just swiss and he's confused." and "You're stepping on the prime number!"
So this Chris character apparently has discovered a prime number which is in the list of the top 5000 primes. So that's cool and all. His prime number is about 20,000 digits long. Lots o' digits. He printed out about half his number or so and put it on a long continous strip of paper that was draped around the room. Cool. So the subject of the talk was ways of finding prime numbers. Probabilistic testing was discussed briefly. There are algorithms that can be used to figure out what the probability is that a certain number is prime. There exist, however, a certain set of numbers known as Carmichael numbers that show up as false positives in these tests, such as 561. But they can be eliminated easily enough, I'm told. The main probabilistic primality test is apparently the Rabin-Miller test, apparently used in RSA software packages. Some more entertaining quotes: "There's no rigorous way to say this ... it has good runtime!" (after attempting to explain the principles the algorithm is based on, and giving up) and "this is just a guy, you call him up?" (grad student who wanted to know how exactly the algorithm worked)
The main part of the talk was about other methods tho. So you can either find primes that fit certain patterns or test arbitrary numbers. Turns out the latter is practically infeasible. For the former there are many different varieties of patterned primes. Some common means are Lucas-Lehman (sp?) which finds Mercennes Primes, Pepin's Test (which finds Fermat primes) and Proth. I've written down a lot of math for each of these methods, but I didn't understand the math at the time, so I've got no chance of decrypting it in my notes now. But of interest is the fact that for encryption purposes, probabilistic primality tests are more secure than the above patterned prime methods, since if you know a package uses only primes of a certain pattern, it's pretty easy to do circumvent the factoring step upon which the security of these systems is based.
Finally there's the primality tests for arbitrary numbers. These are scary. I don't understand them at all. There's the Jacobi-Sum test, which was implemented once in code and took hundreds of thousands of lines to implement. And it turns out to be only probablistically in P. So chances are good you'll get a result in polynomial time, but there's a small chance that the program won't halt on a particular number you give it. There's apparently also some elliptic curve test for testing primality of arbitrary numbers, but I'm missing notes on that.
I'm really bitter that I was forced to waste as much time as I did on math courses that taught me stuff I never used instead of match courses that could have taught me how to really understand the stuff above. There's so much cool math out there that I don't understand. Like the stuff above. grrr... hmmm... all this seems to be lacking in coherence.