import java.math.BigInteger;

public class Power {


    public static void main(String args[]) {

	// The numbers we want to calculate
	BigInteger p = new BigInteger("470371337651747200580641806655577929345787339815775238995809");
	BigInteger q = new BigInteger("44998447341177314016702369046401726397149954873177618720838261");
	BigInteger num = new BigInteger("65979868121280433192872534207000052486263592074347425701725573245489523638457262351946261146698247560345");
	BigInteger n = p.multiply(q);
	
	// Modular Exponentiation
	BigInteger result1 = power(num, num, n);
	System.out.println(result1.toString());

	// Benchmark for Modular Exponentiation
	long sumTime = 0;
	for (int i = 0; i < 100; i++) {
	    long startTime = System.nanoTime();
	    result1 = power(num, num, n);
	    long endTime = System.nanoTime() - startTime;
	    sumTime += endTime;
	}
	
	System.out.print("\nAvg Time Taken for 100 Modular Exp (ns): ");
	System.out.println(sumTime / 100);
	System.out.println("\n");

	// CRT
	BigInteger result2 = crt(num, num, p, q);
	System.out.println(result2.toString());

	// Benchmark for CRT
	sumTime = 0;
	for (int i = 0; i < 100; i++) {
	    long startTime = System.nanoTime();
	    result2 =  crt(num, num, p, q);
	    long endTime = System.nanoTime() - startTime;
	    sumTime += endTime;
	}

	System.out.print("\nAvg Time Taken for 100 CRT (ns): ");
	System.out.println(sumTime / 100);


	// Debug, to check answer
	// Answer is
	// 7653857691010022313223577564966738411275905583436529086118418613982850185838405413953588038245207580313446648868475771207
	//BigInteger ans = num.modPow(num, n);
	//System.out.println(ans.toString());

	// Results
	// Avg Time Taken for 100 Modular Exp (ns): 7672280
	// Avg Time Taken for 100 CRT (ns): 7214456
	// ** Faster By about 6% **

    }

    // Calcuates val^exponent (MOD mod)
    // By means of Modular Exponentiation
    // Using algo in Trappe & Washington pg 93-94
    public static BigInteger power(BigInteger val, 
				   BigInteger exponent, 
				   BigInteger mod) {

	// To store intermediate results
	BigInteger a = exponent;
	BigInteger b = BigInteger.ONE;
	BigInteger c = val;
	BigInteger two = new BigInteger("2");

	// if val^0 = 1
	if (a.equals(BigInteger.ZERO))
	    return BigInteger.ONE;

	while (!a.equals(BigInteger.ZERO)) {
	    
	    // test if a is even
	    // because bit 0 will be 0(false) if it is even
	    if (!a.testBit(0)) {
		// a is even

		// a = a/2
		a = a.divide(two);
		
		// b = b (do nothing)

		// c = c^2 (mod n)
		c = (c.multiply(c)).mod(mod);
	    } else {
		// a is odd

		// a = a - 1
		a = a.subtract(BigInteger.ONE);
		
		// b = b*c (mod n)
		b = (b.multiply(c)).mod(mod);

		// c = c (do nothing)
	    }

	}

	return b;
				
    }

    // Uses Chinese Remainder Theorem to calculate
    // val^exponent (MOD p*q), where n = p*q
    public static BigInteger crt(BigInteger val,
				 BigInteger exponent,
				 BigInteger p,
				 BigInteger q) {
	// Calculate n = p*q
	// Alternatively, we can directly pass in n as a parameter
	BigInteger n = p.multiply(q);

	// Number "system" changed to
	// (mod p, mod q) system

	// Get p1 and q1, which represent
	// p and q respectively in the new system
	// i.e. (num MOD p, num MOD q) = (p1, q1)
	BigInteger p1 = val.mod(p);
	BigInteger q1 = val.mod(q);
	
	// Instead of taking num^num MOD n
	// We do 
	// (p1 MOD p, q1 MOD q)^num
	// = (p1^num MOD p, q1^num MOD q) (in our "new" MOD number system)

	// raise p1 to num, mod p
	p1 = power(p1, exponent, p);

	// raise p2 to num, mod q
	q1 = power(q1, exponent, q);

	// we have answer!
	// but need to convert back to integer
	// use CRT
	// solve simultaneous congurences:
	// x = p1 (mod p)
	// x = q1 (mod q)
	//
	// We need (by CRT):
	// t1 = p1 * q * (q^-1 (mod p))
	// t2 = q1 * p * (p^-1 (mod q))
	// x = t1 + t2 (mod p*q)

	BigInteger t1 = p1.multiply(q).multiply(q.modInverse(p));
	BigInteger t2 = q1.multiply(p).multiply(p.modInverse(q));
	BigInteger x = (t1.add(t2)).mod(n);

	// solved, x is the answer (in integer)
	return x;
    }
    
}