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.
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.