import java.math.BigInteger;
import java.security.SecureRandom;

public class Practical11_fermat {

	public static BigInteger expm(BigInteger m, BigInteger a, BigInteger b) {

		BigInteger result = new BigInteger("1");
		BigInteger zwei = new BigInteger("2");
		BigInteger base = new BigInteger("0");
		
		base = a;
		
		while (b.compareTo(BigInteger.ONE) == 1) {
			
			if (b.mod(zwei).compareTo(BigInteger.ONE) == 0) {
				
				result = result.multiply(base);
				base = base.multiply(base).mod(m);
				
			} else {

				base = base.multiply(base).mod(m);
				
			}
			
			b = b.divide(zwei); 
						
		}
		
		if (b.mod(zwei).compareTo(BigInteger.ONE) == 0) {
			
			//result = result.multiply(base);
			result = result.multiply(base).mod(m);
			base = base.multiply(base).mod(m);
			
		} else {

			base = base.multiply(base).mod(m);
			
		}

		return result;
			
	}
	
	public static boolean fermat(BigInteger n, BigInteger t) {
		
		BigInteger i = new BigInteger("1");
		BigInteger two = new BigInteger("2");
		BigInteger r = new BigInteger("0");
		int size = 20;
		BigInteger a = new BigInteger(size,new SecureRandom());
		
		while (i.compareTo(t) <= 0 ) {
			
			if (a.compareTo(n.subtract(two)) >= 0) return fermat(n,t);
			
			System.out.print("a: "+a);
			
			r = Practical11_fermat.expm(n,a,n.subtract(BigInteger.ONE));
			
			System.out.print(" r: "+r);
			
			System.out.println(" t: "+t);
			
			i = i.add(BigInteger.ONE);
			
			if (r.compareTo(BigInteger.ONE) != 0) return false;
						
		}	
			
		return true;
		
	}
		
	public static void main(String[] args) {

		BigInteger n = new BigInteger("18409199");
		BigInteger t = new BigInteger("57");
		
		System.out.println("Fermat: "+Practical11_fermat.fermat(n,t));
		
	}

}