Wraparound multiplicaton vs mullo

[David Harvey]

On Oct 17, 2009, at 5:03 PM, Niels Möller wrote:

>> How about recursing into the same routine for the multiplication
>> modulo 2^(n/2) - 1?
>
> The current code is not organized that way, it evaluates the
> polynomial at +1, -1 (for x^2-1) and +1, -1, i (for x^4-1), performs
> full balanced multiplication for each point, then interpolates a
> polynomial of the same degree as the inputs, evaluates that polynomial
> at B^{n/2} or B^{n/4}, and in that evaluation, the highest coefficient
> wraps around.

Ok I see.

There are so many more options along these lines.... one could do x^2  
- x = x*(x-1), i.e. arithmetic modulo B^(2n) - B^n; I think this  
could still be successfully used for REDC, but this needs some more  
thought. I expect the evaluation/interpolation for x^2 - x would be  
slightly cheaper than for x^2 - 1.

Then of course x^3 - x, or more generally (x - a[1]) ... (x - a[n]).  
So e.g. instead of x^4 - 1, you could do x^4 - 5*x^2 + 4 = (x^2 - 1)  
* (x^2 - 4). I bet that could be made faster than using x^4 - 1.

Perhaps there should be a sequence of best algorithms, one for each  
number of pieces?

david