Did anyone implemente algoritem for finding prime numbers in polynomial-time as describe in "Primes in P" by Manindra Agrawal, Neeraj Kayal and Nitin Saxena. Any code would be welcome. Or at least translation of line 12 to some programming language. Thanks. You should never let your fears become the boundaries of your dreams.

Never did but if you can quote the text I can give it a try ^_^

For line 12, the authors suggest "repeated-squaring and Fast-Fourier Multiplication". I have little knowledge of the latter, but I''m sure google will tell you what you need to know

Can anyone clarify what the comma is for in (mod x^r-1,n)? I''ve never seen a comma used there before.

quote:

---

a = b(mod x^r-1,n)?

---

Edit: Sorry, it means that a is congruent to b in "the ring Z_n / (x^r -1 )".

afaik this is just the same as a = b mod lcm(x^r - 1, n). (lcm is the least common multiple)

And I take back my skepticism after reading some commentaries on the paper.

[edited by - sQuid on September 29, 2002 8:25:24 PM]

My advanced algorithms course looked at the paper for a few days during the summer(right after it was published), and it indeed does work. But the thing to remember is that in P in this case means x^12, and there are better algorithms out there already to find primes. This could have some interesting applications later on, but right now primes in P is a novelty, and not of any "real" use.

~Mike

It is impossible to implement this algorithm without
knowing the (currenly unknown)constant c.
This paper only proves
the existence of a prime number algorithm that runs in P,
but it is not really implementable yet.
Without a proof of what the constant is
(or at least a theoretical limit of its size),
it is possible that you will get some wrong answers
from the algorithm if you tried to implement it in its
current form. You would at least have to make a table of
numbers for which you get wrong answers from the algorithm,
and check the input against that list.
If the input number is in the list,
use the number''s primality that is stored in the
associative list, otherwise run the algorithm as usual.



Steven Borkman
Home Page: http://www.borkman.mygamesite.net
Video Game Page: http://www.dev.mygamesite.net

quote:

---

Edit: Sorry, it means that a is congruent to b in "the ring Z_n / (x^r -1 )".

afaik this is just the same as a = b mod lcm(x^r - 1, n). (lcm is the least common multiple)

And I take back my skepticism after reading some commentaries on the paper.

[edited by - sQuid on September 29, 2002 8:25:24 PM]

---

Are you sure that's right?
I think it might mean a = b (mod x^r -1) (mod n)
In other words, do one mod and then the other in sequence.



Steven Borkman
Home Page: http://www.borkman.mygamesite.net
Video Game Page: http://www.dev.mygamesite.net



[edited by - borkman on October 4, 2002 3:27:52 PM]

how big is the biggest number you expect to check ? i could give you code to a program that can calculate primes up to 7.5 million in about 5 minutes on a pentium 3 700 mhz computer