title: Up-to-degree N polynomial multiplication
body: <p>I am wondering if there are fast algorithms to do polynomial multiplication <code>modulo N</code>, i.e. given two polynomials of degree <code>N</code>, </p>
  
  <p><img src="https://latex.codecogs.com/gif.latex?p_N%28x%29%20%3D%20%5Csum_%7Bn%3D0%7D%5EN%20a_n%20x%5En" alt="eq1"> </p>
  
  <p><img src="https://latex.codecogs.com/gif.latex?q_N%28x%29%20%3D%20%5Csum_%7Bm%3D0%7D%5EN%20b_m%20x%5Em" alt="eq2"></p>
  
  <p>I am interested in their product but only up to degree N, i.e.</p>
  
  <p><img src="https://latex.codecogs.com/gif.latex?p_N%28x%29%20q_N%28x%29%5C%2C%20mod%5C%2CN%20%3D%20%5Csum_%7Bk%3D0%7D%5EN%20%28%5Csum_%7Bi%3D0%7D%5Ek%20a_i%20b_%7Bk-i%7D%20%29%20x%5Ek" alt="Eq3"></p>
  
  <p>Note that the <code>k</code> sum only goes to <code>N</code> (not to <code>2N</code> as it would in normal polynomial multiplication). For example given </p>
  
  <p><img src="https://latex.codecogs.com/gif.latex?p_2%28x%29%3Dx%5E2&plus;3%20x&plus;2%2C%20q_2%28x%29%20%3D%203%20x%5E2%20&plus;7%20x&plus;%204" alt="eq4"></p>
  
  <p>the result should be:</p>
  
  <p><img src="https://latex.codecogs.com/gif.latex?p_2%28x%29%20q_2%28x%29%5C%2C%20mod%5C%2C%202%20%3D%2031%20x%5E2%20&plus;26%20x%20&plus;%208" alt="Eq5"></p>
  
  <p>I am aware that there are fast <a href="https://www.geeksforgeeks.org/multiply-two-polynomials-2/" rel="nofollow noreferrer">algorithms to do polynomial multiplication</a> but I wonder if they can be applied to the restricted polynomial multiplication I am interested in.</p>