Turns out, Primes are in P 444
zorba1 writes "Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem."
Big consequences related to encryption (Score:-1, Interesting)
What's Polynomial Time? (Score:2, Interesting)
Steve
Crypto repercusions? (Score:2, Interesting)
While that may not be thrilling at first, let's use the RCA contest for money as an example. We get a 1024 bit number containing 200 digits in decimal formm, which is the product of exactly two prime numbers. We know then that:
1. We only need to find one prime to easily find the other.
2. The digits in the factors can total no more than 200 digits.
3. One of the factors contains less than 100 digits.
Start at 10^100 and count down using this algorythm, and youll find it in P time instead of NP time. It'll still take forever, literally and figuratively, but wouldn't it take significantly less time than before?
Toodles
If this turns out to be true... (Score:2, Interesting)
What is 'x' and how is 'q' calculated? (Score:4, Interesting)
I'm dead tired (Score:3, Interesting)
"Let q be the largest prime factor of r-1"
Won't getting q boost the thing back into power n complexity?
Nothing revolutionary (Score:3, Interesting)
All this would mean is that now instead of verifying that a number is prime with a (1-10^-10) level certainty in polynomial time, it could now be done with certainty, so there would be no revolution in cryptology, as some other posters suggest.
--Sam L-L
Re:Big consequences related to encryption (Score:2, Interesting)
Consider a simple public key encryption algorithm based on the fact proved in any beginning number theory book that for primes p, q
a^x = a (mod pq) if x = 1 (mod m)
where m = (p - 1)(q - 1)
Now choose your favorite number f and use Euclidean algorithm to efficiently find a number g such that
fg = 1 (mod m)
You may have to try another value of f if the Euclidean algorithm terminated before reaching 1, but it won't take many guesses. Now publish the number f and mod m as your public key and keep g private.
Someone sends text t to you by sending t^f (mod m).
Now you just raise that message to the power g and reduce mod m to recover the original text. (This follows immediately by combining the above statements).
Finally, I'll get to the point. This algorithm is simply busted if p and q are not prime because t^fg will not equal t mod m unless you are very lucky. In fact, if you want to add a bunch of nines to your percentage certainty, just encrypt and decrypt a sample message text and verify that it works.
Re:p=np? (Score:3, Interesting)
O(num_bits**12) time estimates (Score:5, Interesting)
We give a deterministic O((log n)**12) time algorithm for testing whether a number is prime.
[Sorry, the Slashdot filter does not allow me to superscript the 12.]
The algorithm takes O(log2(n)**12) time, where n is number being factored. If we optimistically assume that this algorithm can test the primality of a 16-bit number in one microsecond, then here is how long it would take to test time primality of some larger numbers.
I don't know what a realistic base time for this algorithm really would be, and I don't know where the cross over point against existing exponential time deterministic primality testing algorithms would be, but at least this provide a sense of how log2(n)**12 grows.
Re:Primality testing has never been hard (Score:1, Interesting)
However, there is a certain stunning elegance about this new test for primality (the main loop hit me hard) that almost takes it to the level of Euclid's algorithm for GCD. A loop of the form 'while(r less than n) {...;r++;}' has an in-your-face audacity, especially when we learn that it will deterministically terminate before log(n)^3 (if I'm reading it right)!
Re:for the sake of our eyes (Score:2, Interesting)
Re:Big consequences related to encryption (Score:3, Interesting)
actually test to see if this exponentiation procedure works.
RSA does work with carmichael numbers instead of primes, for example, because
a^c == a (mod c) for all a s.t. (a,c)==1, c a carmichael number
Try it - it works!
Phil
This fact is not new... (Score:2, Interesting)
It basically worked by finding out if numbers were composite, but the algorithm used could be "inverted" to tell you if a number was prime or not by telling you if it was composite or not.
It was very well suited to parallel implementations, too.