[13337] in cryptography@c2.net mail archive
Primality Algorithm
daemon@ATHENA.MIT.EDU (Jill.Ramonsky@Aculab.com)
Mon May 19 12:46:57 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Jill.Ramonsky@Aculab.com
To: cryptography@metzdowd.com
Date: Mon, 19 May 2003 13:29:05 +0100
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@metzdowd.com
