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 | |
I found it useful! Is there any way to do the modular exponentiation by a non-recursive method though?
A very well done code
Thank you! How could I plot such a function or fft it? Using plot(0:L,modexp(x,0:L,n)) does not work...
Why don't you just use rem
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks!