Primality Algorithm

[Jill.Ramonsky at Aculab.com]

Hi all, I have a couple of questions about the much-publicised Agrawal,
Kayal and Sexena algorithm for determining the primality of an integer in
polynomial time.

(1). Does anyone know where I can find an implementation for the algorithm
in C or C++ ?

(2). A slightly more bizarre question in which I confess my own ignorance
... It was my intention to implement this MYSELF in C++ (a task which didn't
sound too difficult), until I realised that I didn't entirely understand the
algorithm. Ahem. My biggest problem is with step 12, which reads:

12.     if ((x-a)^n != (x^n - a)(mod x^r - 1,n)) output COMPOSITE;

(I substituted the ^ symbol for superscripts, and I also substituted "!="
for the symbol "NOT IDENTICAL TO" (Unicode character \u2262), due to the
limitations of ASCII).

Okay - can someone tell me what (mod x^r - 1,n) means?

I mean, I KNOW what (mod n) means. I know that (x)(mod n) means the same
thing as the C expression (x % n) - at least for positive numbers. BUT -
step 12 of the AKS algorithm has got _two_ expressions after the word mod,
separated by a comma, and I have no idea what that means, or how to
translate it into C or C++. Could somebody please explain?

Thanks, and apologies for appearing ignorant.

Jill


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com