ModExp.java

Below is the syntax highlighted version of ModExp.java from §5.6 Cryptography.

/******************************************************************************
 *  Compilation:  javac ModExp.java
 *  Execution:    java ModExp a b n
 *  
 *  Computes a^b mod n using repeated squaring.
 *
 *   % java ModExp 17 5 10
 *   7
 *
 *   %  java ModExp 43417 53535 34310
 *   12053
 *
 *   % java ModExp 345343417 542323535 324244310
 *   23504373
 *
 ******************************************************************************/

public class ModExp {

    // return a^b mod n
    public static int modexp(int a, int b, int n) {
        if (b == 0) return 1;
        long t = modexp(a, b/2, n);  // use long for intermediate computations to eliminate overflow
        long c = (t * t) % n;
        if (b % 2 == 1)
           c = (c * a) % n;
        return (int) c;
    }

    public static void main(String[] args) {
        int a = Integer.parseInt(args[0]);
        int b = Integer.parseInt(args[1]);
        int n = Integer.parseInt(args[2]);
        StdOut.println(modexp(a, b, n));
    }

}