- Jan 2, 2003A new version availible here

http://217.35.81.229/gmp/prime1.15.tar.bz2

which corrects some minor bugs , thanks to Phil Carmody

NOTE:

This should still be regarded as experimental. I haven't done any work on it

since May last year and the source code is in a mess since in the middle of

testing some optimizations I discoved a possible problem with it , and until

I can resolve this problem I wont being doing any new optimizations.

A brief description of the problem follows , in the hope that someone can help

me please.

The "problem" is pretty simple .

In the psuedoprime part of the test , we have to calculate a number in the

ring Z/NZ[\delta] and test whether it is a root of unity , where delta is a

primative p^k th root of unity. Like everyone else I represent elements of

this ring as polynominals mod the p^k cyclotomic polynominal , with coeffs as

intergers mod N . Now this is not the most effiecient representation , but it

is simple to program (or is it?). The calculation poses no problem , it's the

test to see whether the result is a root of unity , how do you do it ?

My first try was to power it , and see if it is 1 , this works (but see below)

but is slow.

The second attempt was to check it directly by working out how each root of

unity is represented as a polynominal , and doing a direct compairison , this

works (but see below) and is very fast. This is how everyone does it.

The problem is that the two above approaches assume that the representation of

elements of the ring as polynominals is unique.

A simpler example would be consider the representation of rational numbers as

a pair of intergers , how do test that a number is 1 ? , you must either put

the representation into canonical form (divide top and bottom by the gcd) or

check for all possible representations of 1 as a fraction (which in this case

is trivial)

The "problem" is that I do know how to do this test , but no one else does it

this way , why ???

either they have all forgotten , and that their programs all have this error ,

or that there is some reason/trick that I've missed that gets around it , or

I have a completely incorrect understanding of the algorithm.

I know of no examples of where this happens in practice , although I'm sure I

can construct a artificial example . I think it may happen when the p^k 'th

cyclotomic polynominal is reducible over Z/NZ (where N is the number being

tested) and p,k the usual .

Help please!!!

Jason Moxham

j.l.moxham@... - Next post in topic >>