FYI
WOW! :eek:
But can it dice, slice, and julienne?
Tripler
I am such an asshole. 
You know, I’m really bad at math and almost anything math-related, but I have an inordinate fondness for primes. (I have a tendency to recite primes in my head when I’m bored or trying to sleep.) This is really…well…NEATO.
Thanks, astro.
What real-world implications does this have? anyone?
I’m sure the financial industry would love to know indivisible numbers, i.e. selling shares at whole dollars, rounding foreign currency conversions by specifying integer amounts. . .
Not to mention the nuclear physics. Wooo!
Tripler
We haven’t even touched on the academics of it, yet.
I’d have to read up on cryptography algorithms, but it seems to me that if you could generate huge primes at will, one might be able to assign a unique RSA-type encryption to each message. The way it stands now, if you lose your private RSA key (i.e. stolen by a angry ex-employee) all your past messages can be decrypted. Using randomly-selected huge primes for the individual messages means each message will have to be decrypted individually.
This will have a little impact, but not much. The really sexy problem is figuring out how factor composite numbers quickly. That would have a much larger effect on cryptography (Bryan’s post is accurate, btw).
Being able to generate primes faster may make RSA key-pair generation faster, but the encryption time would still be slow. Usually you just use RSA encryption to encrypt the key for a different (faster) algorithm such as DES. You generate new DES keys for each message, but you keep the same RSA private key and keep it safe. The main advantage of public-private key pair schemes is non-repudiation. That is, if you encrypt something with your private key, I can use your public key to decrypt it and I can be sure that it came from you. This is what makes digital certificates work.
Bah! Everybody knows P-time can’t hold a candle to P-Funk!
I’m pretty sure the financial industry can already easily figure out any prime numbers within the range of the total number of all shares of stock in the world.
Ooh! ooh! it’s exciting!
My views:
I won’t believe it until someone like Gary Miller says it works. There are some lurking doubts about this claim that I’ve seen pop up in a few places.
We already know how to prove primaility in polynomial time if you’re willing to relax an issue. For example, the aforementioned Gary Miller already gave a poly time algorithm, assuming ERH. (Which is why some wonder if the new result also assumes ERH and is nothing new.) There is also a method that provies prime/composite in “almost certainly” polynomial time. Note that since we need large primes (and not large composites) there are algorithms (again due to Miller, not Rabin) that can provide them in short time with high probablility. There are what people use “in real life”. So no real practical impact, but potentially very big theoretically. (Now, if factoring were poly time, we’d have a really important result, not just to RSA stockholders.)
So we can generate all the RSA keys we want day in and day out already. That’s the first problem with Bryan Esker’s post. The second problem ignores the whole point of public key cryptosystems. Namely, key distribution. If key distribution were not a problem, then we’d all use one-time pads. If you’re generating new RSA keys for each message, you may as well save yourself the trouble and generate one-time pads (which are far easier to create, encrypt and decrypt, but far harder to distribute). (I’m leaving out a lot of cryto-detail here. But think about it, someone sends you an RSA key and says to encrypt the Big Plans using it and send it to them. How do you know this came from “them” since it is the only key you’ve got? Well, they sign it, but with what key? Cyclic stuff.)
(I’ll ask Miller about this the next time I have dinner with him. But since it was 3 years since the last dinner, don’t hold your breath. :))
Remind us what ERH is?
Dude, yer not helping me here. . .
Tripler
I may waste bandwidth, but sometimes I sound smart. . .
Never mind, I found it. ERH is the extended Riemann hypothesis, for those playing along at home.