/**
 * FastExpon is a fast computational algorithm for computing large exponents. x^e % m
 * This algorithm was used for a cryptography course dealing with RSA.
 * Feel free to slice it up for yourself. :)
 * @author Alan Lambkin
 * @version 1.0 September 2006
 */

public class FastExpon
{
        public long y = 1;

        /**
         * Performs the calculation...
         * While the exponent is not zero:
         * If the exponent is even, square the base, mod m, and divide the exponent by 2.
         * If the exponent is odd, mulitply the base times y (initially set to 1) mod m,
         * now place that value into y, and subtract 1 from the exponent.
         * @parm        x      the base
         * @parm        e      the exponent
         * @parm        m      the mod
         * @return      The answer, x raised to e, mod m.
         */
        public long fex(long x, long e, long m)
        {
                while (e != 0)
                {
                        if (e%2==0)
                        {
                                x=x*x%m;
                                e=e/2;
                        }
                        else
                        {
                                y=x*y%m;
                                e=e-1;
                        }
                }
                return y;
        }

        /**
         * Just a simple main program so I can test before posting.
         * Prints out the answer.
         */
        public static void main(String[] args)
        {
                long x = 6916502;
                long e = 2773637;
                long m = 8326363;
                FastExpon f = new FastExpon();
                System.out.println(x + " raised to the " + e + " power, mod " + m + " = " + f.fex(x,e,m));
        }
}