Wraparound multiplicaton vs mullo

David Harvey 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,  
> x^8-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.

david



More information about the gmp-devel mailing list