Wraparound multiplicaton vs mullo
dmharvey at cims.nyu.edu
Wed Oct 21 14:52:23 CEST 2009
On Oct 21, 2009, at 3:00 AM, Niels Möller wrote:
> Moreover you don't need to write different functions for x^4-1,
> I doubt x^8-1 is a good idea, since I see no efficient way (below the
> FFT range) to compute mod x^4 + 1.
Hang on. I agree with Marco's previous email about doing x^4 - 1 by
working modulo x^2 - 1 and x^2 + 1 and CRT'ing together. My reasoning
is that "I see no efficient way (below the FFT range) to compute mod
x^2 + 1". This is the same reason you have given for not doing x^8 -
1 by working modulo x^4 - 1 and x^4 + 1. So what's the difference?
There seems to be some inconsistency here.
More information about the gmp-devel