# Prime solution wows the math world!
**URL:** https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199
**Category:** Miscellaneous and Personal Stuff I Must Share
**Created:** [August 9, 2002, 8:57pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199 "2002-08-09T20:57:11Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@astro](https://boards.straightdope.com/u/astro)
#### Post date: [August 9, 2002, 8:57pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/1 "2002-08-09T20:57:11Z")
FYI
[Prime solution wows the math world](http://www.msnbc.com/news/792126.asp)
> [@](#):
>
> Scientists say algorithm offers ‘foolproof’ way to find primes
>
> NEW DELHI, Aug. 9 — Indian computer scientists say they have solved a mathematical problem that has eluded researchers for 2,200 years — and could be crucial in modern times in improving computer configurations.
[The algorithim](http://www.cse.iitk.ac.in/news/primality.html)
---
### Author:  [@Tripler](https://boards.straightdope.com/u/Tripler)
#### Post date: [August 9, 2002, 9:06pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/2 "2002-08-09T21:06:54Z")
WOW! :eek:
But can it dice, slice, and julienne?
Tripler
I am _such_ an asshole. 😃
---
### Author:  [@papergirl](https://boards.straightdope.com/u/papergirl)
#### Post date: [August 9, 2002, 10:26pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/3 "2002-08-09T22:26:02Z")
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.**
---
### Author:  [@Mangetout](https://boards.straightdope.com/u/Mangetout)
#### Post date: [August 9, 2002, 11:24pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/4 "2002-08-09T23:24:36Z")
What real-world implications does this have? anyone?
---
### Author:  [@Tripler](https://boards.straightdope.com/u/Tripler)
#### Post date: [August 9, 2002, 11:46pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/5 "2002-08-09T23:46:18Z")
> [@](#):
>
> \*Originally posted by Mangetout \*
> \*\*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.
---
### Author:  [@Bryan\_Ekers](https://boards.straightdope.com/u/Bryan_Ekers)
#### Post date: [August 10, 2002, 2:45am UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/6 "2002-08-10T02:45:18Z")
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.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [August 10, 2002, 5:57pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/7 "2002-08-10T17:57:34Z")
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).
---
### Author:  [@kferr](https://boards.straightdope.com/u/kferr)
#### Post date: [August 10, 2002, 7:02pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/8 "2002-08-10T19:02:27Z")
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.
---
### Author:  [@KneadToKnow](https://boards.straightdope.com/u/KneadToKnow)
#### Post date: [August 10, 2002, 7:29pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/9 "2002-08-10T19:29:50Z")
> [@](#):
>
> this result is a major breakthrough, likened by some to the P-time solution to Linear Programming announced in the 70s
Bah! Everybody knows P-time can’t hold a candle to P-Funk!
---
### Author:  [@waterj2](https://boards.straightdope.com/u/waterj2)
#### Post date: [August 10, 2002, 7:58pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/10 "2002-08-10T19:58:10Z")
> [@](#):
>
> 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. . .
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.
---
### Author:  [@Tansu](https://boards.straightdope.com/u/Tansu)
#### Post date: [August 10, 2002, 8:40pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/11 "2002-08-10T20:40:18Z")
Ooh! ooh! it’s exciting!
---
### Author:  [@ftg](https://boards.straightdope.com/u/ftg)
#### Post date: [August 10, 2002, 9:29pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/12 "2002-08-10T21:29:51Z")
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. :))
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [August 10, 2002, 11:00pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/13 "2002-08-10T23:00:14Z")
Remind us what ERH is?
---
### Author:  [@Tripler](https://boards.straightdope.com/u/Tripler)
#### Post date: [August 11, 2002, 9:37pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/14 "2002-08-11T21:37:10Z")
> [@](#):
>
> \*Originally posted by waterj2 \*
> \*\*
> 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. \*\*
Dude, yer not helping me here. . .
Tripler
I may waste bandwidth, but sometimes I _sound_ smart. . .
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [August 11, 2002, 10:10pm UTC](https://boards.straightdope.com/t/prime-solution-wows-the-math-world/123199/15 "2002-08-11T22:10:14Z")
> [@](#):
>
> \*Originally posted by ultrafilter \*
> \*\*Remind us what ERH is? \*\*
Never mind, I found it. ERH is the extended Riemann hypothesis, for those playing along at home.