Primality Algorithm

[tom st denis]

--- Jill.Ramonsky at Aculab.com wrote:
> 
> 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?

As I understand it it means GF(n)[x]/(x^r - 1) which is fancy talk for
the field generated by (x^r - 1) of characteristic n.  e.g. the
coefficients of the polynomial are reduced mod n.

In all honestly unless you are doing this for research purposes you
might as well just use say 8 rounds of Miller-Rabin.  For all practical
purposes that is just as good [chances of failure < 2^-80].

Tom

__________________________________
Do you Yahoo!?
The New Yahoo! Search - Faster. Easier. Bingo.
http://search.yahoo.com

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