Hi:
[EMAIL PROTECTED] wrote:
>
> Jason Stratos Papadopoulos wrote (to Peter Montgomery):
> >
> > > 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.
> >
>
[...snip...]
> The other "problem" I encountered, which you alluded to,
> is that one of the really nice properties of arithmetic
> over GF(q^2), namely that arithmetic modulo the gaussian
> integers closely mirrors that over the complex numbers,
> fails for non-power-of-2 runlengths, in the sense that
> the conjugation property exploited by complex FFTs which
> pack real inputs into half-length complex vectors no
> longer holds for the modular data. The conjugates are
> still there, but their locations in the transform
> output are all screwed up, to use nontechnical language.
> This probably can be overcome or at least mitigated to
> some degree, but it didn't look like it was going to be
> pretty when I first encountered it. But starting with
> a simple power-of-2 runlength implementation and using
> a good compiler (I plan to switch to C) should be a
> worthwhile effort.
>
I wonder if there is possible to find primitive roots in GF(q^2), say a
+ ib, with the condition
a^2 + b^2 = 1 mod q
If this were possible, then
(a + ib)*(a - ib) = 1 + 0i (mod q)
i, e. the inverse of the root would be the conjugate, and the
transformed of a real integer signal should have the same symmetries
than in trigonometric complex case. Could it resolve the problem for a
non-power-of-two FFT length ?. If the answer is yes: any trick to find
the root other than brute force?
Regards.
Guillermo.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
