Primes in P

[IcemanJer]

Sorry deviate from technical hardware topic to something more, ah I guess, theoretical.

As posted on Slashdot, a professor and his two students in India Institute of Technology have discovered a primality testing algorithm that has a deterministic polynomial running time. The paper can be downloaded here.

Thoughts? Discuss.

 

[rgwalt]

Originally posted by: IcemanJer
Sorry deviate from technical hardware topic to something more, ah I guess, theoretical.

As posted on Slashdot, a professor and his two students in India Institute of Technology have discovered a primality testing algorithm that has a deterministic polynomial running time. The paper can be downloaded here.

Thoughts? Discuss.

I read over the paper, but number theory is not my strong suit. It has been awhile since I've done anything with prime numbers and modulo() terms. That being said, I wonder what speed up we'll see with this method...

Ryan

 

[bassx88]

I read over the paper, but number theory is not my strong suit. It has been awhile since I've done anything with prime numbers and modulo() terms. That being said, I wonder what speed up we'll see with this method...

Ryan

I think we'll be seeing the exact opposite... the breakthrough in this paper is not a faster algorithm, but the fact that it comes up with an answer every time. From what I read elsewhere, previous algorithms would come up empty on some numbers.

 

[heliomphalodon]

This result is really of theoretical, rather than practical, interest. It answers a long-open question on the computational "difficulty" of primality testing.

A polynomial-time factoring algorithm, on the other hand, would be of immense practical interest!

 

[unclebabar]

Am I missing something? Given a list of prime numbers (generated from the mentioned theorem), would it not be possible to reduce any given number into it's prime factors in linear time?

 

[glugglug]

I must be missing it also.

It's trivial to factor any number x in time proportional to sqrt(x), worst case, which is better than linear.
A very similar algorithm will test primeness in sqrt(x) time.

Finding ALL primes <= x takes approximately linear time. (There is a linear part and a part proportional to sqrt(x) * log(x) on the fastest algorithm I know of - and thats actually better than linear if you really think about it...)

 

[glugglug]

Here's a factoring program I just hacked up: fastfactor.exe

sqrt(x) time for primes, faster for non-primes.

 

[glugglug]

Note: the program just posted works up to 281474976710655.

After that you get rounding error from converting the input double to __int64.

(iostream won't handle 64 bit integer input directly, so unless I want to make my own input routines...)

 

[IcemanJer]

RSA is based on the fact that you're taking the prime factor of a number that has something like 300 digits. So essentially every check for prime number is going to take O((the 300 digit number)^12), which, sure is better than before because the algorithm wouldn't yield a 100% correct answer, is still slow.

 

[nave]

Originally posted by: glugglug
I must be missing it also.

It's trivial to factor any number x in time proportional to sqrt(x), worst case, which is better than linear.
A very similar algorithm will test primeness in sqrt(x) time.

Finding ALL primes <= x takes approximately linear time. (There is a linear part and a part proportional to sqrt(x) * log(x) on the fastest algorithm I know of - and thats actually better than linear if you really think about it...)

An algorithm's runtime is usually described as a function of the size of its input. In numerical algorithms such as these (that deal with some number x), I believe the "size" of the input is lg(x) - i.e. the number of bits needed to represent the number - rather than x itself. The algorithm described in the paper runs in O(lg(x)^12), hence it runs in time polynomial in the number of bits needed to represent x - that's the major achievement.

 

[Carceri]

And just to clarify:

The paper describes an algorithm for determining if a number is prime or not without factoring the number, and it does so in polynomial time. Previously we only had algorithm that would output either: Not a prime (and you could be sure that the number wasn't a prime) or it would say prime (but the number still might be a composite). What is done in practice is simply to run the algorithm X number of times. If the chance of a composite number passing as a prime is 1/2 the chance of a composite number passing as a prime after X runs of the algorithm is (1/2)^X. Furthermore the algorithm is pretty fast. The new algorithm described is very slow compared to the probabilistic algorithm, but you can rely on the result 100% after only one run of the algorithm. That's the achievement.

This is useless for factoring. Here you already know that the number is not a prime. And don't even think about writing a list of all primes up to, say, 300 digits and then use that list to help factor a number. You can find some formulas for approximating the number of primes smaller than a certain number here: http://www.utm.edu/research/primes/howmany.shtml

I have implemented a factoring algorithm that can handle any number (if you have the time and memory but currently 60-70 digit numbers are the limit for most computers) It's running time is (as all currently known factoring algorithms) exponential in the number of digits of the number to factor (To be more precise it's O(e^((1+O(1))*Sqrt(ln n * ln ln n)))). You can download the program as well as read about the method here

 

[IcemanJer]

Originally posted by: Carceri
If the chance of a composite number passing as a prime is 1/2 the chance of a composite number passing as a prime after X runs of the algorithm is (1/2)^X.

Wait, you're talking about the running time of the algorithm being O((1/2)^X), right?

 

[Carceri]

Wait, you're talking about the running time of the algorithm being O((1/2)^X), right?

No, I haven't stated what the running time of the probabilistic algorithm for primality testing is, but if it fails with probability 1/2 on a composite number, running the algorithm X times the probability that it will still accept a composite number as a prime is (1/2)^X. As you can see X needs only be rather small (say about 100 or so) before you can be very certain that the number is in fact a prime.

I don't have the running time for the Miller Rabin primality test in my head right now, but if it was O(xx) running the algorithm 100 times would be O(100 * xx) which is still O(xx)

 

[unclebabar]

> And don't even think about writing a list of all primes up to, say, 300 digits and then use that list to help factor a number.

Holy $#%, there's a lot of prime numbers. I was thinking that as the number of digits got bigger, the rarer the possibility of getting another prime. Obviously, there are still plenty at 10^300. Alas, my plans for world domination will have to wait. :|

 

[StumbleBum1]

bump

 

[kylebisme]

Originally posted by: IcemanJer
RSA is based on the fact that you're taking the prime factor of a number that has something like 300 digits. So essentially every check for prime number is going to take O((the 300 digit number)^12), which, sure is better than before because the algorithm wouldn't yield a 100% correct answer, is still slow.

is still cool too