Nathan Karst
  • Home
  • Teaching
  • Research

Powers modulo n in Matlab

3/8/2014

1 Comment

 
Many modern cryptographic techniques rely on modular powers. In order for these schemes to be secure, the base, exponents, and modulus are often quite large. I'm currently using Matlab in the cryptography course I'm teaching, and double precision overflow was immediately a problem for even relatively small examples. I've coded up an implementation of the left-to-right binary method that allows us to do so more realistic examples: 
function rem = powMod(base,exponent,modulo)
% POWMOD(BASE,EXPONENT,MODULO) computes BASE^EXPONENT mod MODULO using the
% right-to-left binary method.
if (modulo^2 > bitmax)
    error('Modulos is too large!')
end

rem     = 1;
base    = mod(base,modulo);
e   = fliplr(str2num(dec2bin(exponent)')'); % this is the best/worst line ever; lsb in e(1).
n   = length(e);
for i = 1:n
    if e(i) == 1
        rem = mod(rem*base,modulo);
    end
    base = mod(base^2,modulo);
end
The method itself is really neat. I think it would make a great project for an undergraduate with a little prior coding experience. 

Notice that even here we could have double precision overflow if the square of the modulus is too large. I've been thinking about either implementing a variable precision method, or switching out of Matlab entirely the next time I run the course. I think a natural alternative would be Python. If anyone has any thoughts, feel free to post or email. 
1 Comment

    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