Got a prime number? This formula can tell you

November 4, 2002 12:39 PM

Got a prime number? This formula can tell you. Dr. Manindra Agrawal, a professor of mathematics at the Indian Institute of Technology, and two doctoral students have solved a problem that has been puzzling mathematitians for literally centuries: testing with absolute certainty whether a number is prime. More inside.
posted by me3dia (24 comments total)

The formula works even on very large prime numbers. This has some application to the Internet, since current encryption algorithms take two large prime numbers and multiply them together; the formula could provide the basis of even stronger encryption.

On the other hand, some enterprising (and mathematically talented) criminals could use the formula to develop a method of decryption, rendering current Internet security useless.

Download the paper here.
posted by me3dia at 12:41 PM on November 4, 2002

Before the imminent death of modern cryptography is predicted, I'd like to point out that the key to strong crypto is the difficulty of factoring a large number. Just knowing that a number is prime doesn't affect the situation, since your essential magic bullet would have to quickly tell you what the prime factors of some composite number is.

But this is pretty cool, regardless.
posted by cortex at 12:48 PM on November 4, 2002

mathworld has some more information on prime numbers as well as the work by agrawal et. al. in addition, you might be interested in the GIMPS project, a distributed computing effort that aims at proving a particular sort of prime numbers called mersenne primes.
posted by moz at 12:48 PM on November 4, 2002

I'm not certain criminals could use the formula to decrypt anything; it doesn't tell you (AFAIK) how to factor a given number into primes. It just gives you a yes or no answer as to whether it's prime or not.
(on preview: what Cortex said.)
posted by wanderingmind at 12:52 PM on November 4, 2002

Discussed previously, alas.
posted by ptermit at 12:59 PM on November 4, 2002

On the other hand, some enterprising (and mathematically talented) criminals could use the formula to develop a method of decryption, rendering current Internet security useless.

God damn the fucking DMCA. Before 4 years ago, trying to break encryption was a perfectly respectable thing to do. How better to make a solid algorithm than to have people other than the creator trying to break it? Criminalizing such efforts means we all get a security blanket to go along with the inevitably weaker encryption we get.

The amusing thing is that it isn't that much of a stretch to say that merely coming up with the algorithm that they did was in itself a criminal act, since it makes breaking existing encryption algorithms much easier, and this was a clear use of the formula before it was created.

The world is getting pretty fucked up.
posted by kfury at 1:05 PM on November 4, 2002

On the other hand, some enterprising (and mathematically talented) criminals could use the formula to develop a method of decryption, rendering current Internet security useless.

On the other hand, some enterprising (and mathematically talented) criminals could use the formula to develop a stronger method of encryption, rendering current government intelligence initiatives useless.
posted by kfury at 1:07 PM on November 4, 2002

Note of course that people knew algorithms for determining if a number n was prime before -- like checking every whole number up to sqrt(n) to see if divided into n evenly. It just took a long, long time. This takes less time.
posted by namespan at 1:08 PM on November 4, 2002

Right; I don't want to further rain on the parade here, but we already have 'algorithms' that deal with this, and generally in less time -- but these other 'algorithms' only provided a probabilistic proof that a number was prime, i.e., "with probability really super close to 100%, this number is prime." This paper is exciting because we now have a polynomial-time deterministic check instead of a probabilistic check; but for all intents and purposes, the probabilistic checks we have are sufficient. For CS folks, it's exciting since testing for primality is now definitely P and not NP. For other folks, your mileage, it may be varying. As those other folks said, I don't think we're entering a whole new world of cryptography here.
posted by evinrude at 1:08 PM on November 4, 2002

a problem that has been puzzling mathematitians for literally centuries: testing with absolute certainty whether a number is prime

This misses the point completely. Doing what you said is completely trivial: you test all the numbers up to the square root of the one you've got, and see if they divide in evenly. Done.

What Agrawal et. al. did here is very different. They gave an algorithm whose complexity is polynomial in the number of bits of the input (rather than the brute-force method above).

On the other hand, some enterprising (and mathematically talented) criminals could use the formula to develop a stronger method of encryption, rendering current government intelligence initiatives useless.

No. There's nothing going on here that's mystical about numbers or primes or anything else. All this is is a faster algorithm than we knew about before.
posted by gleuschk at 1:10 PM on November 4, 2002

And one that was posted three months ago, to boot.
posted by gleuschk at 1:12 PM on November 4, 2002

we'd be entering a whole new world of cryptography should quantum computing become practical for either the government or the mass-market to use. quantum computing would squash current cryptography methods with its fast factoring, but would also introduce new forms of cryptography that would be difficult to break. (once or twice i've heard that Q.cryptography could be "unbreakable," but i'm kind of wary...)
posted by moz at 1:16 PM on November 4, 2002

Thanks, ptermit. You would have thought that a search for "prime numbers" would have turned that up, but it didn't.


Gleuschk, I was trying to give a layman's explanation of what the formula did -- I'm not a math person, and neither are most people here. My description is accurate, just not very deep. Assuming one read the links, the more nuanced explanation would be clear.
Sorry if my summary ruined it for you.
posted by me3dia at 1:20 PM on November 4, 2002

Quantum cryptography isn't so much unbreakable, even given current theory, as it is 'uneavesdroppable.' Since it relies on a heisenbergian principle of the detection of the data bit itself destroying that bit, it can only be 'listened to' once.

At least I think that was it. I've gotta re-read Singh's The Code Book, as that sounds suspiciously vulneralbe to a man-in-the-middle attack...
posted by kfury at 1:20 PM on November 4, 2002

I was trying to give a layman's explanation of what the formula did -- I'm not a math person, and neither are most people here. My description is accurate, just not very deep.

I understand that my reaction seemed excessively harsh. I apologize for that. Still, I must say that your description is not accurate. The problem solved by this algorithm (not a formula) has not puzzled mathematicians for centuries. The problem that it solves is trivial.

The way that this algorithm solves the problem has indeed puzzled mathematicians for quite some time (the "centuries" part is debatable). But you made no reference to that, when it is in fact the whole point of their result, and of the page you linked.

The previous thread ran into these difficulties as well, and they were (mostly) eventually hashed out.
posted by gleuschk at 1:36 PM on November 4, 2002

"You are visitor N+1, where N is the number of visitors before you.
B0rken HTML courtesy of the web-authoring tool 'Pico' :-)
My girlfriend will refuse to proof-read my pages unless I cross-link to her: The Anna. "

Cute. On a related note, I just discovered the other day that my phone number is prime.
posted by atom128 at 1:38 PM on November 4, 2002

There are two different things commonly lumped under the heading of quantum cryptography. One is quantum key distribution using entangled states, which is nearly practical. You still need an unspoofable channel in order to make sure you've agreed on the same key, but that channel can be low-bandwidth and eavesdroppable, as long as it's not spoofable.

The other technique is quantum computation, which might provide a way to solve NP problems quickly. This could weaken RSA and similar algorithms that depend on the difficulty of factoring large numbers. (I don't know if it also affects discrete-log or elliptic systems.) Quantum computation is much farther from being practical, although simple computations have been performed in the lab.
posted by hattifattener at 2:10 PM on November 4, 2002

Doing what you said is completely trivial: you test all the numbers up to the square root of the one you've got, and see if they divide in evenly.

Actually, just the primes.
posted by Bonzai at 2:45 PM on November 4, 2002

actually, primality checking belongs to a unique class of problems known as NP-easy; any instance of the primality checking problem can be turned into an NP-incomplete problem through a (Legendre) polynomial time reduction.
[/disinformation]
posted by eddydamascene at 3:08 PM on November 4, 2002

>>Doing what you said is completely trivial: you test all the numbers up to the square root of the one you've got, and see if they divide in evenly.

Actually, just the primes.


Well, that's a very slightly less trivial technique, though. You can do the other without any previous knowledge of the sequence of primes. :) Now, WHY you would want to do that is a different issue...
posted by cortex at 4:39 PM on November 4, 2002

Actualy this can nither be used to create a stronger kind of encryption or break current encryption either.

Thanks for playing, though.
posted by delmoi at 8:16 PM on November 4, 2002

Here is my explanation from the last thread

Anyway, as far as practical applications, there are none really. This only lets us be 100% sure if a number is prime rather then 99.9999999....% sure, and isn't all that much faster.

This will make encryption slightly better, in fact you can be 'sure' that the numbers you are using are prime rather then 99.99999999999..% sure.

beyond that, its pretty intresting for numbers freaks and CS nerds, but nothing that will have any impact whatsoever on anything in the real world.
posted by delmoi at 8:32 PM on November 4, 2002

Which is why that Cnet article is so infuriating. How can they miss the point so badly? And rustle up professional academic mathematicians to back up their nonsensical claims? Argh.
posted by gleuschk at 8:43 PM on November 4, 2002

Just wanted you all to know that 2 made the cut...
posted by byort at 7:15 AM on November 5, 2002