I'm teaching a introductory cryptography and coding theory course this semester in which we're using Matlab to implement a bunch of different cryptosystems. I was a little surprised to see that Matlab doesn't have a built-in function (that I could find, at least) that computes in the inverse of $x$ modulo $n$ if it exists.

There's actually a fairly pretty solution. Bezout's identity tells us that for any integers $x$ and $y$ not both zero, there exist integers $a$ and $b$ such that a linear combination gives the greatest common divisor of $x$ and $y$. $$ax + by = gcd(x,y).$$ Matlab actually gives us hooks to compute $a$ and $b$ in it's gcd function:

There's actually a fairly pretty solution. Bezout's identity tells us that for any integers $x$ and $y$ not both zero, there exist integers $a$ and $b$ such that a linear combination gives the greatest common divisor of $x$ and $y$. $$ax + by = gcd(x,y).$$ Matlab actually gives us hooks to compute $a$ and $b$ in it's gcd function:

>> help gcd

GCD Greatest common divisor.

G = GCD(A,B) is the greatest common divisor of corresponding elements

of A and B. The arrays A and B must contain integer values and must be

the same size (or either can be scalar). GCD(0,0) is 0 by convention;

all other GCDs are positive integers.

[G,C,D] = GCD(A,B) also returns C and D so that G = A.*C + B.*D.

These are useful for solving Diophantine equations and computing

Hermite transformations.

So suppose we want the multiplicative inverse of $x$ modulo $n$. We know (or could show from first principles with relatively little work) that $x$ has a multiplicative inverse modulo $n$ if and only if $gcd(x,n) = 1$. So Bezout's identity tells us that there exist integers $a$ and $b$ such that $$ax + bn = 1.$$ Since $bn \equiv 0 \bmod n$, we're left with $ax \equiv 1$, which shows that $x^{-1} \equiv a \bmod n$.

Here's my implementation in Matlab:

Here's my implementation in Matlab:

function xInv = modInv(x,n)

% ModInv(x,n) computes the multiplicative inverse of x modulo n if one

% exists; errors if no such inverse exists

if gcd(x,n) ~= 1

error('x has no inverse modulo n')

end

[d, a, b] = gcd(x,n);

xInv = mod(a,n);

end