Skip to content

Instantly share code, notes, and snippets.

@drawers
Last active October 6, 2015 02:11
Show Gist options
  • Save drawers/0f395eaed5c0046cf344 to your computer and use it in GitHub Desktop.
Save drawers/0f395eaed5c0046cf344 to your computer and use it in GitHub Desktop.
An implementation of a divide-and conquer method of calculating modular exponents
public class ModularExponent {
//ModularExponent
//An implementation of divide-and-conquer method of calculating modular exponents
//See Introduction to Algorithms, Corment et al.
//tested correct to (a,b,n) = (256,256,256)
public static int modularExponent(int a, int b, int n) {
if (a < 0 || b < 0 || n < 0) {
throw new IllegalArgumentException("Arguments must be positive integers");
}
int c = 0;
int d = 1;
char [] bits = Integer.toBinaryString(b).toCharArray();
for (int k = 0 ; k < bits.length; k++) {
c = c * 2;
d = Math.multiplyExact(d,d) % n;
Integer i = new Integer(3);
if (bits[k] == '1') ) {
c++;
d = Math.multiplyExact(d,a) % n;
}
}
return d;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment