On Mon, 12 Mar 2001 [EMAIL PROTECTED] wrote:
> 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).
<Blush> this is exactly the same as the more conventional number-theoretic
transforms. I promise to think next time before asking.
Doesn't the above imply g is real? How can you get a complex integer
out of successive powers of g?
> 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.
That's good to know. I don't suppose sqrt(1/2) is necessarily a power of
two when p is not a Mersenne prime, is it? Or is it that this is possible
with an even more carefully chosen primitive root g?
> 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).
Neat!
> 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.
As I remember, he *had* implemented it but the project is in limbo now for
several reasons: first, the Alpha compiler wouldn't interleave the integer
and floating point instructions, and also Ernst mentioned that
non-power-of-two transforms in GF(p^2) had some subtle difficulty
(something about the order that you applied the various radices being
important). Last I heard he was embarking on implementing a mixed
integer/complex FFT in assembly language, but that was quite a while ago
and he likely has moved on.
Thanks again,
jasonp
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
