Last active
May 10, 2022 20:29
-
-
Save ttezel/4635562 to your computer and use it in GitHub Desktop.
Modular Exponentiation in Matlab (x ^ y mod n)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%{ | |
Problem 7 (i): modexp function | |
Returns x ^ y mod n for x, y, and n > 1. | |
%} | |
function result = modexp (x, y, n) | |
%anything raised to 0th power = 1 so return 1 | |
if (y == 0) | |
result = 1; | |
return; | |
end | |
%recurse | |
z = modexp(x, floor(y/2), n); | |
%if even square the result | |
if (mod(y, 2) == 0) | |
result = mod(z*z, n); | |
return; | |
else | |
%odd so square the result & multiply by itself | |
result = mod(x*z*z, n); | |
return; | |
end | |
end | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thank you! How could I plot such a function or fft it? Using plot(0:L,modexp(x,0:L,n)) does not work...