Nathan Karst
  • Home
  • Teaching
  • Research

Modular multiplicative inverses in Matlab

1/30/2014

4 Comments

 
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: 
>> 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:
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
4 Comments
Fidia link
9/26/2015 07:44:26 pm

Very helpful ! thx

Reply
Nikki
2/28/2016 12:10:52 am

Thank you!:D

Reply
Kevin Neilson
5/13/2016 03:28:52 pm

Thanks; this was helpful.

Reply
143 Records link
10/3/2024 11:46:09 pm

Grreat read thankyou

Reply



Leave a Reply.

    Archives

    June 2015
    May 2015
    February 2015
    December 2014
    October 2014
    September 2014
    August 2014
    July 2014
    May 2014
    March 2014
    February 2014
    January 2014
    December 2013
    October 2013
    July 2013
    June 2013
    May 2013
    April 2013
    March 2013
    February 2013
    January 2013

    Nathan Karst

    Doing and teaching mathematics. 

    Categories

    All

    RSS Feed

Powered by Create your own unique website with customizable templates.
Photo from ByoLogyc