parallel_invert.py

def parallel_invert(l, n):
   '''Inverts all elements of a list modulo some number, using 3(n-1) modular multiplications and one inversion.'''
   culm = l[:]
   for i in xrange(len(l)-1):
      culm[i+1] = (culm[i] * l[i+1]) % n

   try:
      inv = invert(culm[-1], n)
   except ZeroDivisionError:
      return gcd(culm[-1], n)

   for i in xrange(len(l)-1, 0, -1):
      culm[i] = (inv * culm[i-1]) % n
      inv = (inv * l[i]) % n
   culm[0] = inv

   return culm