Search code examples
creductionmodular

Computing remainder of polynomial division

Does the following code implement modular reduction of the polynomial multiplication of f•g modulo xp−x−1? As we know, to get the modular reduction, we first multiply the polynomials f and g, then divide by xp−x−1, and the remainder is the result h = f•g.

I could not see how the code below does this. The degrees of the polynomials are at most p−1, i.e., they look like f(x) = 1+x−x2+....−xp−1 which is represented as an array f[p] = {1, 1, -1,... -1}. And array h = fg[p+p-2] stands for the product of f and g.

Can someone explain this to me?

for (i = p+p-2;i >= p;--i) 
{
    fg[i-p] = fg[i-p]+fg[i];
    fg[i-p+1] = fg[i-p+1]+fg[i];
}
for (i = 0;i < p;++i) h[i] = fg[i];
Solution

  • Does the following code stand for modular reduction of the polynomial multiplication of f.g by mod (x^p-x-1)?

    Yes.

    The degree of the polynomials are at most p-1, i.e., they look like f(x)= 1+x-x^2+....-x^{p-1} which is shown as an array f[p]={1,1,-1,...,-1}.

    No, the reduced polynomial has degree at most p−1, but this is code to reduce the result of a multiplication. Two polynomials of degree up to p−1 have been multiplied, producing a polynomial of degree up to 2p−2, and the job of this code is to take the remainder modulo xp−x−1.

    To do this, i iterates through the degrees from 2p−2 (written p+p-2) to p. It starts at 2p−2 since that is the highest degree that might be present in the product, and it stops at p since that is the lowest degree for which there is a quotient whose multiple can be subtracted.

    Then, for each degree i, it subtracts a multiple of xp−x−1: Let c be the coefficient of xi, fg[i]. Then this code subtracts c•xi−p•(xp−x−1) = c•xi − c•xi−p+1 − c•xi−p:

    • Subtracting c•xi would yield zero in fg[i]. This is implemented simply by ignoring the coefficients at indices p and above; they are not copied into the h result by the loop at the end.
    • − c•xi−p+1 is subtracted by adding c (fg[i]) to the coefficient of xi−p+1, in the code fg[i-p+1] = fg[i-p+1]+fg[i];.
    • − c•xi−p is subtracted by adding c (fg[i]) to the coefficient of xi−p, in the code fg[i-p] = fg[i-p]+fg[i];.

    When the first for loop completes, all multiples of the polynomial have been subtracted from the initial product, leaving only the remainder.

    Then for (i = 0;i < p;++i) h[i] = fg[i]; simply copies the new coefficients into h.