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.