On Tuesday, September 10, 2002, at 01:00 PM, [EMAIL PROTECTED] wrote:
Brendan Younger <[EMAIL PROTECTED]> wrote:
>I know there has been some discussion on this list about the
>theoretical possibility of staying in frequency space and doing a bunch
>of point-wise squarings in there instead of computing the inverse DWT
>after every iteration. Now, I'm not suggesting this as a feasible
>avenue for GIMPS as I've read some of the arguments against it in the
>archives. I'm just curious as to how it might proceed if you could
>assume infinite precision, etc. For instance, would it be as simple as:
>
>DWT(x) -> X^n -> IDWT(X^n) == x^n (mod 2^q - 1) (where "n" is now only 2?)
Yes. Of course since you have just one element in your input vector,
the DWT multiplier is just unity, FFT(x) = x, and you're really just
doing a scalar multiply and subsequent modular reduction (that's the
carry step).
I'm sorry, I was talking about a sequence of x's, not just a single one. (i.e. the x_i for the base in the DWT)
>Also, if it *is* this simple, could there be any
>modular reduction of the X^n before doing the IDWT?
AFAIK, no, at least not in a floating-point-FFT-based scheme.
If you were doing a number-theoretic transform modulo 2^q-1
you'd have your mod, but then things again reduce to the one-term
scheme described above. Another question one might ask is, can
one do any part of the normalize-outputs-and-carry step in frequency
space? The problem here is that the forward-FFTed and dyadically-
squared terms contain a mixture (linear superposition, to be
precise) of the actual inverse FFT outputs one wants. Each
term contains a different mix of the n outputs, and in the
Crandall-Fagin DWT scheme, these outputs are w.r.to a mixture
of bases, so even if one had a clever way to effect the normalization
by a constant base in frequency space, it wouldn't work with DWT.
Let me see if I understand correctly. Most of the literature I've seen dealing with NTTs for large-integer multiplication has always said to pick a field with size > (input values)^2 so that you get the exact answer after the INTT. It seems to me that allowing the calculation to overflow in the dyadic squaring in an NTT wouldn't disrupt the final answer. Therefore, my question is whether the LL test can proceed as such:
NTT(x_i) -> X_i = (X_i * X_i - 2) (q - 2 dyadic squarings modulo the NTT modulus and the necessary subtraction by two) -> INTT(X_i) == (0, or some other number) (mod 2^q - 1)
My apologies for not making this more explicit earlier, but I didn't want to be shouted down with a "That's already been considered and discarded" response.
Brendan Younger
