title: Changing coefficients modulo p in a SymPy polynomial
body: <p>I took a cryptography course this semester in graduate school, and once of the topics we covered was NTRU. I am trying to code this in pure Python, purely as a hobby. When I attempt to find a polynomial's inverse modulo p (in this example p = 3), SymPy always returns negative coefficients, when I want strictly positive coefficients. Here is the code I have. I'll explain what I mean.</p>
  
  <pre><code>import sympy as sym
  from sympy import GF
  
  def make_poly(N,coeffs):
      """Create a polynomial in x."""
      x = sym.Symbol('x')
      coeffs = list(reversed(coeffs))
      y = 0
      for i in range(N):
          y += (x**i)*coeffs[i]
      y = sym.poly(y)
      return y
  
  N = 7
  p = 3
  q = 41
  f = [1,0,-1,1,1,0,-1]
  
  f_poly = make_poly(N,f)
  
  x = sym.Symbol('x')
  
  Fp = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(p))
  Fq = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(q))
  
  print('\nf =',f_poly)
  print('\nFp =',Fp)
  print('\nFq =',Fq)
  </code></pre>
  
  <p>In this code, <code>f_poly</code> is a polynomial with degree at most 6 (its degree is at most <code>N-1</code>), whose coefficients come from the list <code>f</code> (the first entry in <code>f</code> is the coefficient on the highest power of <code>x</code>, continuing in descending order).</p>
  
  <p>Now, I want to find the inverse polynomial of <code>f_poly</code> in the convolution polynomial ring <code>Rp = (Z/pZ)[x]/(x^N - 1)(Z/pZ)[x]</code> (similarly for <code>q</code>). The output of the print statements at the bottom are:</p>
  
  <pre><code>f = Poly(x**6 - x**4 + x**3 + x**2 - 1, x, domain='ZZ')
  Fp = Poly(x**6 - x**5 + x**3 + x**2 + x + 1, x, modulus=3)
  Fq = Poly(8*x**6 - 15*x**5 - 10*x**4 - 20*x**3 - x**2 + 2*x - 4, x, modulus=41)
  </code></pre>
  
  <p>These polynomials are correct in modulus, but I would like to have positive coefficients everywhere, as later on in the algorithm there is some centerlifting involved, so I need to have positive coefficients. The results should be</p>
  
  <pre><code>Fp = x^6 + 2x^5 + x^3 + x^2 + x + 1
  Fq = 8x^6 + 26x^5 + 31x^4 + 21x^3 + 40x^2 + 2x + 37
  </code></pre>
  
  <p>The answers I'm getting are correct in modulus, but I think that SymPy's <code>invert</code> is changing some of the coefficients to negative variants, instead of staying inside the mod.</p>
  
  <p>Is there any way I can update the coefficients of this polynomial to have only positive coefficients in modulus, or is this just an artifact of SymPy's function? I want to keep the SymPy <code>Poly</code> format so I can use some of its embedded functions later on down the line. Any insight would be much appreciated!</p>