Computer Scientists find method to quickly discover primes?

August 8, 2002 4:52 AM

Computer Scientists find method to quickly discover primes? If the claims outlined in this article are correct, an age-long problem of number theory maybe solved. I wonder about the implications for cryptography; any cypherpunks care to comment?
posted by costas (26 comments total)

Computer Scientists find method to quickly discover primes?

Er, no - read it again. Computer scientists find method to establish whether a particular number is prime or not prime. Different.
posted by Dan Brilliant at 5:17 AM on August 8, 2002

Practical implications for symmetric ciphers or RSA-based cryptography (SSL, SSH, AES, Blowfish - pretty much everything you and your sysadmin are encountering day to day) as I understand it: extremely little to none.

Implications for those people offering hundreds of thousands of dollars for finding the Nth prime where N is some stupidly large number: possibly bad, but this is more a test than an algorithm to find primes - you still have to iterate through a stupidly large number of them.

Stuff in crypto you actually should be worried about because the NSA probably had it decades ago: DJ Bernstein's latest finds (first link courtesy of slashdot).
posted by Ryvar at 5:39 AM on August 8, 2002

Full paper here
posted by yerfatma at 6:14 AM on August 8, 2002

Implications for cryptography: none. There are already fast prime-testing algorithms out there. Their only drawback is that they are probabilistic; the more confident you want to be that the number is prime, the more times you have to run the algorithm. But these algorithms are more than good enough for CS purposes, and they're probably considerably faster than an implementation of this deterministic algorithm.

The real interest is that this proves that prime-testing is a P class algorithm, which nobody could prove before.
posted by ptermit at 6:15 AM on August 8, 2002

the comments on slashdot are pretty good.

basically, there was already a probabilistic algorithm that was practically useful. so the practical implications of this work are minimal.

but maybe it will lead to more useful work via further developments (i don't know enough to judge whether this is likely or not)

in more detail: the probabilistic algorithm can tell you (very quickly) whether a number is likely to be a prime. also, critically (for it to be useful), it can be repeated (there are some details that make this less odd than it sounds) and each time it says "yes, this is probably a prime", you are more sure. if you run this (fast) algorithm enough times, you end up being more confident that the number is a prime than you are that your computer has malfunctioned. in other words, for all practical work, it´s a certainty.

this new work, on the other hand, gets you the answer without any uncertainty. and it's polynomial, which means that the running time doesn't "explode" as numbers get bigger. however, it´s n^3, which means that it is still very slow for big numbers.
posted by andrew cooke at 6:17 AM on August 8, 2002

You beat me to it, costas! I've been staring at the paper. They claim that it's an "unconditional deterministic polynomial-time algorithm," and if so, it seems like it could be a pretty big deal for computer scientists and number theorists, at least.
posted by Songdog at 6:18 AM on August 8, 2002

I don't think it's O(n^3), andrew. The authors say that it's O((log n)^12), which is a lot better. They also say that if a particular unproven conjecture is correct then it will actually perform at O((log n)^6). And if another particular unproven conjecture is correct then they'll be able to modify it to be O((log n)^3).
posted by Songdog at 6:21 AM on August 8, 2002

I read a little of the paper up until I realized that my actual comprehension was something like "words words words, letters, numbers, numbers." Anyone want to take a stab at explaining the basic ideas here in non-formula English for those of us who are very curious but whose education failed them? It would be appreciated.

Amusing that a paper with such potentially important implications on computer science looks like it was faxed in. Would HTML or even PDF text have been that difficult?
posted by joemaller at 7:02 AM on August 8, 2002

joemaller: let's try.

A P class problem means that if the input is of a given size, the algorithm takes a number of steps that is a polynomial (rather than exponential) function of the input size.

What this means is that the rate of increase in time to solve, as the inputs get bigger, is a straight line on a graph rather than an upward curve.

What that boils down to, is that a class of problems which were previously thought to be very hard for large inputs, are now considered to be manageable.

Hope that helped (still sounds a bit mathsy to me).
posted by walrus at 7:15 AM on August 8, 2002

joemaller - Here's a PDF. It is an unpublished paper, though, and there's at least one typo.
posted by Songdog at 7:53 AM on August 8, 2002

there already exists a reliable method for getting prime numbers, the prime number *#^! bear.
posted by alicila at 8:03 AM on August 8, 2002

modern-day encryption is in much more danger from quantum computing, but with QC is also the promise of proposedly-unbreakable encryption. there is already a programming language proposed for a quantum computer platform.
posted by moz at 8:24 AM on August 8, 2002

alicilia, that's frickin' brilliant. I love it. How'd you come across that?
posted by delfuego at 11:13 AM on August 8, 2002

i don't know. i've just known about it for a long time and this article made me think about it again. it's pretty old, i thought everyone knew about it. this morning when i posted it i also opened up a window and left it open. right now my bear is at the prime number 135173 and has been up for 4 hours.
posted by alicila at 12:07 PM on August 8, 2002

SongDog - sorry, that was from memory. perhaps it was from someone talking data size (bit count) while you're talking number value...? (for n) (i'm due to go to a meeting so haven't checked with the paper to see if that makes sense).
posted by andrew cooke at 12:18 PM on August 8, 2002

NP, Andrew, I'm not positive anyway. They use two different notations interchangeably in the paper: O(log^12 n) and O((log n)^12). I was assuming that this was an accident, given the other little editorial issues, and in any event these two notations should refer to the same thing, but you never know. I didn't read the paper terribly closely anyway. I know a lot more about CS than I do about number theory, so this is only partly within my ken.

By the way though, I just love their style:

The ultimate goal of this line of research is, of course, to obtain an unconditional deterministic polynomial-time algorithm for primality testing. Despite the impressive progress made in primality testing so far, this goal has remained elusive. In this paper, we achieve this.

(emphasis mine)
posted by Songdog at 1:13 PM on August 8, 2002

i'm no expert either. out of curiousity i started reading koblitz's course in number theory + crypto (springer verlag) a while back. it's very nicely written and although i've still not finished the exercises in the first chapter, i'd recommend it to anyone looking for a good start to number theory (largely because people whose taste i trust recommended it to me).

ps while i might favour british reserve, it must be nice to be in a position where you can write an abstract like that!
posted by andrew cooke at 1:45 PM on August 8, 2002

Songdog:

I think log^12 (n) and log(n)^n mean the same thing, just like sin² n means the same as sin(n)²

walrus: Well, thanks for explaining the implications now try explaining the actual theory... Your response is like someone asking "how does a car work" and you saying "It lets you go from place to place"


---

Looking at the "basic idea and approach" section, which basically describes what they are doing:

"Suppose that a is coprime to p, then P is prime if and only if (x-a)^p mod p = (x<sup>p - a) mod P"

actually they used the triple equal sign, which means "congruent mod something" in this case, P. For those of you who don't know how modulo arithmetic works, the basic idea is you limit the numbers between zero and P, and after that they 'loop around'

So if P was 8, you would have the numbers 0,1,2,3,4,5,6 and 7. 3 + 4 mod 8 = 7. 4+4 mod 8 = 0. 6 + 7 mod 8 = 5. etc.

So, what "Suppose that a is coprime to p, then p is prime if and only if (x-a)p mod p = (xp - a) mod p"

coprime means that (IIRC) two numbers share no factors. All numbers can be composed of prime factors, for example 6 = 2*3, and 21 = 3*7. 6 and 21 are coprime because they don't share any numbers in the factorization.

but, unfortunately it takes a while to check that. What these guys seem to be doing is rather then modding everything by p, they mod it by (xr - 1,p) I have no idea what they mean by 'comma p' but in the text they just say (xr - 1), which means they mod everything by x to the rth power minus one.

For all prime numbers, the equation up there should hold for all numbers a and r. Unfortunately, some numbers also would show up as prime if a and r are not 'suitable'. So, they pick 'suitable' numbers.

To them, r is 'suitable' if it's prime, which should take O(log(p)6) time. (this means that as you increase p by one, the amount of time it takes to run increases by log(p)6 - log(p-1)). 6. And r - 1 has a prime factor at least r1/2 + q where q is greater then zero. (They used a greek character which looks kind of like an upside down q. I don't know what it's called, but for some reason I call it "wega" when I read it).

Then they check a 'small' number of possible as (in this case, either the number of as or the time it takes to check them increases at a rate of O((square root of r)*log(p)))

The rest of the paper proves all that's true. If I made any mistakes, please let me know.</sup>
posted by delmoi at 3:42 PM on August 8, 2002

you miss one tag...

I'm posting this again because it did screw up the meaning:


Looking at the "basic idea and approach" section, which basically describes what they are doing:

"Suppose that a is coprime to p, then P is prime if and only if (x-a)^p mod p = (x^p - a) mod P"

actually they used the triple equal sign, which means "congruent mod something" in this case, P. For those of you who don't know how modulo arithmetic works, the basic idea is you limit the numbers between zero and P, and after that they 'loop around'

So if P was 8, you would have the numbers 0,1,2,3,4,5,6 and 7. 3 + 4 mod 8 = 7. 4+4 mod 8 = 0. 6 + 7 mod 8 = 5. etc.

So, what "Suppose that a is coprime to p, then p is prime if and only if (x-a)^p mod p = (x^p - a) mod p"

coprime means that (IIRC) two numbers share no factors. All numbers can be composed of prime factors, for example 6 = 2*3, and 21 = 3*7. 6 and 21 are coprime because they don't share any numbers in the factorization.

but, unfortunately it takes a while to check that. What these guys seem to be doing is rather then modding everything by p, they mod it by (x^r - 1,p) I have no idea what they mean by 'comma p' but in the text they just say (x^r - 1), which means they mod everything by x to the rth power minus one.

For all prime numbers, the equation up there should hold for all numbers a and r. Unfortunately, some numbers also would show up as prime if a and r are not 'suitable'. So, they pick 'suitable' numbers.

To them, r is 'suitable' if it's prime, which should take O(log(p)⁶) time. (this means that as you increase p by one, the amount of time it takes to run increases by log(p)⁶ - log(p-1)). ⁶. And r - 1 has a prime factor at least r^{1/2 + q} where q is greater then zero. (They used a greek character which looks kind of like an upside down q. I don't know what it's called, but for some reason I call it "wega" when I read it).

Then they check a 'small' number of possible as (in this case, either the number of as or the time it takes to check them increases at a rate of O((square root of r)*log(p)))

The rest of the paper proves all that's true. If I made any mistakes, please let me know.
posted by delmoi at 3:44 PM on August 8, 2002

walrus:
A P class problem means that if the input is of a given size, the algorithm takes a number of steps that is a polynomial (rather than exponential) function of the input size.

What this means is that the rate of increase in time to solve, as the inputs get bigger, is a straight line on a graph rather than an upward curve.

Not to be picky, but a polynomial function is a not a straight line (unless your plotting on a logrithmic graph or the exponent is equal to one). A polynomial function will still curve up if the exponent of the polynomial is greater than one.

For example n^^2 (n squared) is a polynomial function

2*2=4
3*3=9
4*4=16

In this case n has been incremented by 1 in each step, but the increase in y for each increment in n is not a constant factor and thus nonlinear (and curves up).
posted by tallpaul at 4:21 PM on August 8, 2002

delmoi: fyi: (in the pdf version at least) that thing you're calling "wega" is a lower case delta (and i'm impressed that you can not know that and still make sense (at least at the level i understand things) of the contents!) (this is not intended to be condescending, but i know it reads odd on preview...)
posted by andrew cooke at 4:30 PM on August 8, 2002

in case it's not obvious from the above (it wasn't for me), the reason the they use the extra (x^r-1) is to "fold down" the expansion of (x-a)^p to powers of x which are smaller than r (i guess maybe it is obvious now i've written it down). that saves them from evaluating a polynomial in all the powers of x up to x^p, but means that their identity is no longer true - it can produce false positives. hence the checking.

ps so when they say mod(x^r-1,p) they mean modulo both x^r-1 and p. at least, that's my current best guess.
posted by andrew cooke at 4:42 PM on August 8, 2002

andrew cooke: I don't know why I would know what it's called. I think I might have heard the name once or twice before in my math classes, but I didn't I really cared. The way I saw it, it was just another variable. There is probably some kind of connotation to it, like a, b, and especially c are usually 'constants' whereas x,y and z are variables, t is a parametric variable, etc.

Actually, the symbol was used in my calc book in the description of the method used to determine if a limit in a multidimensional function existed. Since I was working through the examples last night to try to understand I had to 'internally vocalize' it and I just called it 'wega' for some reason. If I had understood the process right away I probably would have just used some other letter. It was a pretty strange coincidence to see it again today.

As far as being able to understand the text, it's all discrete math which is required for CS majors at my university. And I've taken the class twice :P. I've always enjoyed math, but I'm hardly a math geek.

Ultimately, I can draw the character if I need to, which is all that's really needed for homework :)
posted by delmoi at 4:48 PM on August 8, 2002

delmoi - yes, (log x)^n and log^n (x) mean the same thing. I just meant that this inconsistency could represent a typo, especially since there are other typos in the paper. But I believe that you are correct and that the authors mean the same thing in each instance.

I am, however, confused about coprimes: 6 and 21 do share a common prime factor. They are both divisible by 3. Maybe I'm misunderstanding you, but would you mind clarifying this?
posted by Songdog at 4:58 PM on August 8, 2002

delmoi: ok. i come from a physics/maths background (at a very traditional uk university) so didn't realise you could have gone through a maths course without having lectures where maybe half the time the lecture is reading out greek characters...

coprime - 6 & 21 are not coprime (8 and 21 would be).
posted by andrew cooke at 5:17 PM on August 8, 2002

Incidentally, the reason (log n)^12 is polynomial is because to input a number n requires log n bits. So this is polynomial in the size of the input.
posted by metaforth at 12:12 PM on August 11, 2002