# Modular Inversion

Python code for two algorithms to compute the inverse of an arbitrary
element of a prime field is presented below.

The first is an implementation of algorithm 2.107 in the Handbook of Applied
Cryptography.

def inverse_mod(x, p):
assert 0 < x < p
a, b, x2, x1, y2, y1 = p, x, 1, 0, 0, 1
while b > 0:
[q, b], a = divmod(a, b), b
x1, x2 = x2 - q * x1, x1
y1, y2 = y2 - q * y1, y1
return y2 if y2 >= 0 else y2 + p

The second is an implementation of algorithm 14.61 in the same book.

def inverse_mod_binary(x, p):
assert 0 < x < p
v, a, c = p, 1, 0
while True:
while not x & 1:
if a & 1: a = a + p
a = a >> 1
x = x >> 1
while not v & 1:
if c & 1: c = c + p
c = c >> 1
v = v >> 1
if x == v:
return c
if x > v:
x = x - v
a = a - c
if a < 0: a = a + p
else:
v = v - x
c = c - a
if c < 0: c = c + p

### Notes:

- The second algorithm usually performs slower than the first on
desktop computers. On the other hand it doesn't require bigint
divisions, it just needs additions and shifts. This may be
interesting especially for microcontroller implementations.