A Beautiful Mind From India Is Putting the Internet on Alert [Determination of Prime Numbers]

The Wall Street Journal ^ | Monday, November 4, 2002 | LEE GOMES

[TroutStalker]

Will Manindra Agrawal bring about the end of the Internet as we know it? The question is not as ridiculous as it was just two months ago.

Prof. Agrawal is a 36-year old theoretical computer scientist at the Indian Institute of Technology in Kanpur, India. In August, he solved a problem that had eluded millennia of mathematicians: developing a method to determine with complete certainty if a number is prime.

[chance33_98]

There is actually a formula for calculating the Nth prime that exists (a related problem) but due to it's use of factorials it is impossible to work with, there is a wealth of info on primes and it is only a matter of time before we see more of these solved. Thanks for posting!

[DB]

"encryption system takes two big, and secret, prime numbers and multiplies them"

I've never heard that before...

[wildandcrazyrussian]

Hey I'm disappointed. I thought the proof was going to be part of the article!

Don't forget India is where our mis-named "Arabic" numerals originated (1-2-3-4...) before being BROUGHT west by the Islamic traders. Just think what a prosperous civilization India and Eastern Europe and the Middle East and northern Africa would have CONTINUED to be if there han't been 1400 years of genocidal jihad invasions.

[Principled]

prime bump

[tictoc]

What is it with you Indians?

First you invent the zero, then Ramanujan, then this guy?

Have you no mercy on the schoolchildren?

Deviant sadistic torturers!

[IronJack]

derandomizing polynomial time algorithms

I used to know a dancer from New Orleans who could do that. And twirl two tassles in opposite directions.

[JAWs]

Hey I'm disappointed. I thought the proof was going to be part of the article!

Well, that's what you get when you have Fremat as the reporter!

[Doctor Stochastic]

The article is a bit misleading. It's never been "hard" to determine if a number is prime, in the sense of knowing how to do it. It's been "slow." Agrawal's paper displays an algorithm that is asymptotically faster than previous versions. (NOTE: Technospeak Alert: The new algorithm is polynomial in the size of the prime, previous algorithms have been at best sub-exponential.)

It's a nice result.

[boris]

"First you invent the zero, then Ramanujan, then this guy?"

Don't forget Chandrasekhar.

The Hungarians invented Paul Erdos. Erdos and Ramanujan are smiling somewhere.

===============================

I recommend two excellent biographies:

The Man Who Knew Infinity (Ramanujan)
The Man Who Loved Only Numbers (Erdos)

--Boris

[boris]

"Well, that's what you get when you have Fremat as the reporter!"

Fremat? Wasn't he the guy who proved that the square of hypotenuse isn't the square of the two opposing sides?

Or did he invent the "get out of math class free" card in Monopoly?

--Boris

[spodefly]

The aricle is interesting from the math standpoint to the extent that I understand it (spodefly.math.understanding = 0). What strikes me is this:

(2 young math genius') ... had planned to join him on his U.S. victory tour. But the American Embassy in New Delhi, the times being what they are, refused them visas. The two young geniuses had to stay home.

Sure, if your name is Mohammed Akbar and you have C4 in your tennis shoe and jihad in your heart, the INS will grant you a visa, but if your name is Parameswaran Ghandi and you are a math genius ... forget it.

[CanadianFella]

Don't forget Kama Sutra

[2 Kool 2 Be 4-Gotten]

The article is a bit misleading. It's never been "hard" to determine if a number is prime, in the sense of knowing how to do it. It's been "slow." Agrawal's paper displays an algorithm that is asymptotically faster than previous versions. (NOTE: Technospeak Alert: The new algorithm is polynomial in the size of the prime, previous algorithms have been at best sub-exponential.)

Got it. Thanks for the succinct explanation. So this is quite a development.

[Maelstrom]

Damn...the number seive idea is mine from 5-6 years ago.

If it's the same idea, it's fairly simple and should have been described in the article.

As you begin with numbers you calculate all the number of which they are factors by multiplication, up to a given variable limit. As you reach numbers that are not accounted for by this, you identify them as primes.

Example:
(primes, 1,2,3, multiples are then 4 and 6 meaning 5 is prime...continue multiplying in a 2x2 array and arranging the resulting multiples sequentially)

I was hoping to get paid for it by finding the highest prime number.

[chance33_98]

Are you part of the mersenne prime project?

[ThePythonicCow]

two big, and secret, prime numbers and multiplies them

Yeah - that's how the public key encryption schemes work.

The public key is visible to anyone who might either want to send you a message that only you can read, or to decode a message and be sure it came from your. The private key is the other half of that, known only to you.

The private key is the pair of primes, and the public key their product. To send me a message, you encode with my public key, and I decode it with my private key. Or I can "sign" a message by encoding it with my private key, and then only my public key will decode it.

If anyone ever figured out a reasonably fast way to factor large numbers, then all the current encryption schemes that are essential to secure internet communication fail.

Not everything is encrypted using public/private key technology, as the arithmetic is expensive for that. But often at the beginning of a session, public/private keys are used to exchange a temporary cipher (big random number) that is then used to encode the rest of the session using more traditional "secret code" techniques.

See further for example How SSL Works AN INTRODUCTION TO KEY CRYPTOGRAPHY .

[matthew_the_brain]

this sounds like another cold fusion type discovery......I also was looking for the proof. I doubt this whole thing.

[ozidar]

Damn...the number seive idea is mine from 5-6 years ago.

Nice to meet you, Erastosthanes.

[ThePythonicCow]

The article is a bit misleading. It's never been "hard" to determine if a number is prime, in the sense of knowing how to do it. It's been "slow."

Mathematicians use "hard" to describe computationally expensive problems, as in "NP-hard".

See for example: NP-Hard Problem.