def invmod(a, n):
    """Return s, the inverse of a: gcd(a,n)=1=as+nt."""
    d, s, t = egcd(a, n)
    assert d == 1
    return s % n

Have you ever wanted to roll-your-own modular multiplicative inverse function??

Me neither, but here we are. :-D

Motivation

Last year while implementing RSA for cryptopals 39, I was admonished by the author to “take the time to get your own EGCD and invmod algorithm working”.

Without such an exhortation to do it myself, I would probably have just reached into Python’s standard library for pow(a, -1, n) to perform a modular inverse, but I was up for a challenge.

Below are notes to myself for future reference, but posted here in case there is value for other learners. Enjoy!

Extending Euclid’s algorithm

You may recall that Euclid’s greatest common divisor (GCD) algorithm makes use of the fact that $gcd(a, b) = gcd(b, a\mod{b})$.

Assuming $d = gcd(b, a\mod{b})$ and $d = bp + (a\mod{b})q$:

Then $d= bp + (a\mod{b})q = bp + (a - \lfloor \frac{a}{b} \rfloor b)q = aq + b(p - \lfloor \frac{a}{b} \rfloor q)$

See below for one way to implement:

def egcd(a, b):
    """Return gcd(a,b), x, y: gcd(a,b)=ax+by."""
    if b == 0:
        d, x, y = a, 1, 0
    else:
        d, p, q = egcd(b, a % b)
        x = q
        y = p - a // b * q
    
    assert a % d == 0 and b % d == 0
    assert d == a * x + b * y
    return d, x, y

Multiplicative inverse

Definition

You may also recall that a multiplicative inverse of $a\mod{n}$ is $\bar{a}$ such that

$a \times \bar{a} \equiv 1 \pmod{n}$

Existence of an inverse

$a$ has a multiplicative inverse modulo $n$ if and only if $gcd(a, n) = 1$.

Consider $ax \equiv 1 \pmod{n}$ iff $ax + kn = 1$.

For a fixed $a$ and $n$, this Diophantine equation has solution $x$ iff $gcd(a, n) \mid 1$.

Usually this suffices to get me to something like the below code.

def invmod(a, n):
    """Return s, the inverse of a: gcd(a,n)=1=as+nt."""
    d, s, t = egcd(a, n)
    assert d == 1
    return s % n

Parting thought

As a not-so-gifted student of math, I battled for awhile to grasp enough number theory to appreciate the interesting bits of RSA (and write this regrettably dense post) 1. There is a good number theory course 2 that helped me get there.

– JW

Footnotes

  1. Much of the above is borrowed from my class notes and submitted code examples for the aforementioned course so it may only make sense to me (or a fellow student) in that context. ↩

  2. See UC San Diego’s excellent “Number Theory and Cryptography” (Coursera) course at https://www.coursera.org/learn/number-theory-cryptography, taught by Dr. Alexander Kulikov. Clear instructional style, plenty of examples, and a nice mix of videos, reading, and tests of understanding. For the hands-on learner, there are lemmas to prove, problems to work and code to write. ↩