title: Optimize conversion between list of integer coefficients and its long integer representation
body: <p>I'm trying to optimize a polynomial implementation of mine. In particular I'm dealing with polynomials with coefficients modulo <code>n</code>(might be <code>&gt;2^64</code>) and modulo a polynomial in the form <code>x^r - 1</code>(<code>r</code> is <code>&lt; 2^64</code>). At the moment I represent the coefficient as a list of integers(*) and I've implemented all the basic operations in the most straightforward way.</p>
  
  <p>I'd like the exponentiation and multiplication to be as fast as possible, and to obtain this I've already tried different approaches. My current approach is to convert the lists of coefficients into huge integers multiply the integers and unpack back the coefficients.</p>
  
  <p>The problem is that packing and unpacking takes a lot of time.</p>
  
  <p>So, is there a way of improving my "pack/unpack" functions? </p>
  
  <pre><code>def _coefs_to_long(coefs, window):
      '''Given a sequence of coefficients *coefs* and the *window* size return a
      long-integer representation of these coefficients.
      '''
  
      res = 0
      adder = 0
      for k in coefs:
          res += k &lt;&lt; adder
          adder += window
      return res
      #for k in reversed(coefs): res = (res &lt;&lt; window) + k is slower
  
  
  def _long_to_coefs(long_repr, window, n):
      '''Given a long-integer representing coefficients of size *window*, return
      the list of coefficients modulo *n*.
      '''
  
      mask = 2**window - 1
      coefs = [0] * (long_repr.bit_length() // window + 1)
      for i in xrange(len(coefs)):
          coefs[i] = (long_repr &amp; mask) % n
          long_repr &gt;&gt;= window
  
      # assure that the returned list is never empty, and hasn't got an extra 0.
      if not coefs:
          coefs.append(0)
      elif not coefs[-1] and len(coefs) &gt; 1:
          coefs.pop()
  
      return coefs
  </code></pre>
  
  <p>Note that I do <em>not</em> choose <code>n</code>, it is an input from the user, and my program wants to prove its primality(using the AKS test), so I can't factorize it.</p>
  
  <hr>
  
  <p>(*) I've tried several approaches:</p>
  
  <ol>
  <li>Using a <code>numpy</code> array instead of a list and multiply using <code>numpy.convolve</code>. It's fast for <code>n &lt; 2^64</code> but terribly slow for <code>n &gt; 2^64</code>[also I'd like to avoid using external libraries]</li>
  <li>Using <code>scipy.fftconvolve</code>. Doesn't work at all for <code>n &gt; 2^64</code>.</li>
  <li>Represent the coefficients as integers from the start(without converting them every time). The problem is that I don't know of an easy way to do the <code>mod x^r -1</code> operation without converting the integer to a list of coefficients(which defeats the reason of using this representation).</li>
  </ol>