Nathan Karst
  • Home
  • Teaching
  • Research

Modular multiplicative inverses in Matlab

1/30/2014

3 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
3 Comments

Major progress on Steiner systems

1/17/2014

0 Comments

 
As reported by Gil Kalai, some major progress has been made on Steiner systems. The question is: can you find a collection of subsets , each with size $k$, drawn from an ambient set of size $n$, such that each each subset of size $r \leq k$ appears in exactly $\lambda$ subsets in the collection? These designs have a special place in my heart; my thesis work centered on applying them to dynamic rekeying in smart grid systems.

This is problem has been more or less completely open for over 150 years. There have been some good results for $r =2$ and sporadic constructions for $r \geq 3$. Evidently Peter Keevash has cracked the problem wide open by solving the case of general $q$ and $r$. I'm not sure that anyone saw this sort of generalized construction coming. What's more, it seems that there is a new probabilistic construction technique at the heart of the proof. Incredible!
0 Comments

Cuz, ... science!

1/15/2014

0 Comments

 
Young people doing science is awesome. That is all. 
0 Comments

Gompentz law

1/10/2014

0 Comments

 
I found a quick and interesting article on /r/math this morning about the Gompentz law of human mortality. The basic idea is that the probability that you will die in a given year doubles roughly every 8 years. This could turn into a grisly but interesting exam question in my first-year applied mathematical methods class. 
0 Comments

    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 used under Creative Commons from ByoLogyc