gf_reference/gfpinv.py

   1 from .state import ST
   2
   3
   4 def gfpinv(a):
   5     # based on Algorithm ExtEucdInv from:
   6     # https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.5233&rep=rep1&type=pdf
   7     p = ST.GFPRIME
   8     assert p >= 2, "GFPRIME isn't a prime"
   9     assert a != 0, "TODO: decide what happens for division by zero"
  10     assert isinstance(a, int) and 0 < a < p, "a out of range"
  11     if p == 2:
  12         return 1  # the only value possible
  13
  14     u = p
  15     v = a
  16     r = 0
  17     s = 1
  18     while v > 0:
  19         # implementations could use count-zeros on
  20         # both u and r to save cycles
  21         if u & 1 == 0:
  22             u >>= 1
  23             if r & 1 == 0:
  24                 r >>= 1
  25             else:
  26                 r = (r + p) >> 1
  27         # implementations could use count-zeros on
  28         # both v and s to save cycles
  29         elif v & 1 == 0:
  30             v >>= 1
  31             if s & 1 == 0:
  32                 s >>= 1
  33             else:
  34                 s = (s + p) >> 1
  35         else:
  36             x = u - v
  37             if x > 0:
  38                 u = x
  39                 r -= s
  40                 if r < 0:
  41                     r += p
  42             else:
  43                 v = -x
  44                 s -= r
  45                 if s < 0:
  46                     s += p
  47     if r > p:
  48         r -= p
  49     if r < 0:
  50         r += p
  51     return r