Modular Exponentiation Using Double-and-add Approach in Java

This code uses the double-and-add / square-and-multiply algorithm to reduce the computational cost when computing expensive modular exponentiations a^e = r mod n.

Input

Each line contains a space-separated list of an integer basis a, an integer exponent e and an integer modulus n - all integers are positive.

Output

For each input line, a unique integer r ∈ {0,...,n} is returned such that a^e = r mod n.

Example files:

• modexp_sample.in      // input file
• modexp_sample.out     // output for the example