Jason Stratos Papadopoulos <[EMAIL PROTECTED]> writes
> Hello again. After working out how to do integer FFTs on the Alpha, I'm
> considering additional code that uses Fast Galois Transforms (FGTs),
> e.g. for complex integers in GF(p^2) for p a prime congruent to 3 mod
> 4. Bill Daly mentioned this idea before on the list (end of 1998) but
> unfortunately didn't give enough details for me to work out the rest.
> I'm considering a 64-bit version for the Alpha and maybe a 32-bit version
> using MMX and two primes on the Pentium. As usual, though, I need some
> pointers with the theory.
>
> The first big question is how you find a primitive root for transforms of
> this type. Richard Crandall gives a closed-form expression when p is a
> Mersenne prime, but if I'm not using a Mersenne prime for p I would still
> need primitive roots.
Assuming the prime p is fixed at compile time, you can specify
a primitive root g (of prder p-1) in the binary. You can try g = 3, 5, 7, ...
until you succeed. You will need the prime factorization of p-1
when you test whether g is really a primitive root, but that is
easy for 64-bit values of p. A symbolic algebra program
such as Maple can assist you in the calculation.
Later, if you want to do an FFT of length n where n divides p-1,
your primitive root (of order n) can be g^((p-1)/n) (mod p).
> The next question involves eighth-roots of 1 modulo p. For FFTs in complex
> numbers, these eighth roots have a special form that need less arithmetic
> than a complex multiply. Is this also the case in GF(p^2) for general p?
> Or do you need a special primitive root to get these savings? In
> principle, an eighth-root of this form could mean a radix-8 FGT is
> possible that uses no integer multiplies.
Over GF(p^2) the primitive root g will have order p^2 - 1
rather than p-1. Again a small search will suffice.
You raise this to the power (p^2 - 1)/n where n divides p^2 - 1.
If p == 7 (mod 8), then there exists a value sqrt(1/2) in GF(p)
such that 2*sqrt(1/2)^2 == 1 (mod p).
The primitive 8th roots of 1 modulo p are
+- sqrt(1/2) +- i*sqrt(1/2),
just as in the complex case. You can optimize
(a + b*i) * (sqrt(1/2) + i*sqrt(1/2))
to
(a - b)*sqrt(1/2) + i*(a + b)*sqrt(1/2)
(with two multiplications modulo p), just as in the complex case.
> Finally, how in blazes do you find a root of two with these strange
> complex integer things? I managed to answer this halfway by myself for
> more conventional integer FFTs, but I have no clue where to begin here.
Assume p == 7 (mod 8). Then 2 is a square mod p, but -1 is not.
The two values of sqrt(2) will be negatives of each other.
Exactly one of these will itself be a square; select that
value for sqrt(2). Then choose sqrt(sqrt(2)) to itself be a square.
Continue until you have the root you want.
In other words, if n is a power of 2, you are looking for
a value x mod p such that
x^((p-1)/2) == 1 (mod p)
x^n == 2 (mod p)
The last argument shows that a common solution exists.
The exponents n and (p-1)/2 are coprime.
If n*n' == 1 (mod (p-1)/2), then x == 2^(n') (mod p).
When n is not a power of 2, such as if p was chosen with
p == 1 (mod 105) to allow transforms of lengths 3, 5, 7,
then you will need to check (when p is chosen at compile time)
whether 2 is an appropriate power.
Ernst Mayer and I exchanged many mailings about
using GF(p^2) when p = 2^61 - 1.
I thought he had implemented it, as part of a
mixed integer/complex FFT.
Peter Montgomery
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
