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
RSS Feed
