Skip to content

Instantly share code, notes, and snippets.

@cciollaro
Created October 17, 2013 23:36
Embed
What would you like to do?
A right-to-left binary modular exponentiation algorithm in java i.e. calculating a^b mod n
public class ModExp {
public static void main(String[] args) {
System.out.println(modExp(4,13,497));
}
public static int modExp(int a, int b, int n){
int d = 1;
String k = Integer.toBinaryString(b);
for(int i = 1; i <= k.length(); i++){
if(k.charAt(k.length()-i) == '1'){
d = (d*a) % n;
}
a = (a*a) % n;
}
return d;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment