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             if r & 1 != 0:
  23                 r += p
  24             u >>= 1
  25             r >>= 1
  26         # implementations could use count-zeros on
  27         # both v and s to save cycles
  28         elif v & 1 == 0:
  29             if s & 1 != 0:
  30                 s += p
  31             v >>= 1
  32             s >>= 1
  33         else:
  34             x = u - v
  35             if x > 0:
  36                 u = x
  37                 r -= s
  38                 if r < 0:
  39                     r += p
  40             else:
  41                 v = -x
  42                 s -= r
  43                 if s < 0:
  44                     s += p
  45     if r > p:
  46         r -= p
  47     if r < 0:
  48         r += p
  49     return r