title: Computing remainder of polynomial division
body: <p>Does the following code implement modular reduction of the polynomial multiplication of f•g modulo <em>x</em><sup><em>p</em></sup>−<em>x</em>−1? As we know, to get the modular reduction, we first multiply the polynomials f and g, then divide by <em>x</em><sup><em>p</em></sup>−<em>x</em>−1, and the remainder is the result h = f•g.</p>
  <p>I could not see how the code below does this. The degrees of the polynomials are at most <em>p</em>−1, i.e., they look like f(<em>x</em>) = 1+<em>x</em>−<em>x</em><sup>2</sup>+....−x<sup><em>p</em>−1</sup> which is represented as an array <code>f[p]</code> = {1, 1, -1,... -1}. And array <code>h</code> = <code>fg[p+p-2]</code> stands for the product of f and g.</p>
  <p>Can someone explain this to me?</p>
  <pre><code>for (i = p+p-2;i &gt;= p;--i) 
  {
      fg[i-p] = fg[i-p]+fg[i];
      fg[i-p+1] = fg[i-p+1]+fg[i];
  }
  for (i = 0;i &lt; p;++i) h[i] = fg[i];
  </code></pre>