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

/*
 * 
 * Author: Sebastian Wolfgarten, sebastian@wolfgarten.com
 * Date: 08/March/2005
 * Description: Uses Miller-Rabin's test to determine whether a given number is prime or not
 *
*/

public class Practical15_mr {

	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).mod(m);
			base = base.multiply(base).mod(m);
			
		} else {

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

		return result;
			
	}

	public static BigInteger gcd(BigInteger a, BigInteger b) {
		
			BigInteger c = new BigInteger("0");
			BigInteger d = new BigInteger("0");
			BigInteger gcd_a_b = new BigInteger("0");
		
			BigInteger q = new BigInteger("0");
			BigInteger r = new BigInteger("0");
			BigInteger s = new BigInteger("0");
			BigInteger t = new BigInteger("0");

			BigInteger previous_q = new BigInteger("0");
			BigInteger previous_s = new BigInteger("0");
			BigInteger previous_previous_s = new BigInteger("0");
			BigInteger previous_t = new BigInteger("0");
			BigInteger previous_previous_t = new BigInteger("0");
			BigInteger minus_one = new BigInteger("-1");
			
			BigInteger mr_x = new BigInteger("0");
			BigInteger mr_y = new BigInteger("0");
			
			int ctr = 0;
			
			do {
				
				if (ctr == 0) {
					
					s = BigInteger.ONE;
					t = BigInteger.ZERO;
				
				}

				if (ctr == 1) {
					
					s = BigInteger.ZERO;
					t = BigInteger.ONE;
				
				}
				
				if (ctr > 1) {
					
					s = minus_one.multiply(previous_q);
					s = s.multiply(previous_s);
					s = s.add(previous_previous_s);

					t = minus_one.multiply(previous_q);
					t = t.multiply(previous_t);
					t = t.add(previous_previous_t);

				}

				q = c;
							
				c = a.divide(b);
				d = a.subtract(b.multiply(c));

				r = a;
				
				a = b;
				b = d;
				ctr++;
				previous_q = q;
				previous_previous_s = previous_s;
				previous_s = s;
				previous_previous_t = previous_t;
				previous_t = t;

			} while (d.compareTo(BigInteger.ZERO) == 1);
			
			gcd_a_b = a;

			//System.out.println("gcd: "+gcd_a_b);
			
			return gcd_a_b;
					
			
	}
	
	public static BigInteger myexp(BigInteger a, BigInteger b) {

		BigInteger result = new BigInteger("1");
		
		while (b.compareTo(BigInteger.ZERO) != 0) {
			
			result = result.multiply(a);
			b = b.subtract(BigInteger.ONE);
				
		}
		
		return result;
			
	}

	public static BigInteger gen_a(BigInteger x) {
		
		BigInteger new_a = new BigInteger(x.bitLength()-1,new SecureRandom());
		BigInteger two = new BigInteger("2");
		
		if (new_a.compareTo(two) <= 0) return Practical15_mr.gen_a(x); 
		
		return new_a;
		
	}
	
	public static boolean mr(BigInteger x, BigInteger t) {
		
		BigInteger d = new BigInteger("0");
		BigInteger a = new BigInteger("0");
		BigInteger b = new BigInteger("0");
		BigInteger two = new BigInteger("2");
		BigInteger s = new BigInteger("0");
		BigInteger s_ctr = new BigInteger("0");
		BigInteger r = new BigInteger("0");
		boolean result = false;
		
		//while (s_ctr.compareTo(x.subtract(BigInteger.ONE)) != 0) {
		while (s_ctr.compareTo(BigInteger.valueOf(x.bitLength())) <= 0) {
		
			if (x.subtract(BigInteger.ONE).mod(Practical15_mr.myexp(two,s_ctr)).compareTo(BigInteger.ZERO) == 0) {

				s = s_ctr;
				
			}	
				
			s_ctr = s_ctr.add(BigInteger.ONE);
			
		}
		
		System.out.println("s: "+s);
		
		d = x.subtract(BigInteger.ONE).divide(Practical15_mr.myexp(two,s));
		System.out.println("d: "+d);
		
		a = Practical15_mr.gen_a(x);
		
		System.out.println("a: "+a);
		
		while (t.compareTo(BigInteger.ZERO) != 0) {

			//System.out.println("expm(x,a,d): "+Practical15_mr.expm(x,a,d));

			if (Practical15_mr.expm(x,a,d).compareTo(BigInteger.ONE) == 0) {
				
				a = Practical15_mr.gen_a(x);
				//System.out.println("Neues a: "+a);
				
			} else {
				
				while (r.compareTo(s.subtract(BigInteger.ONE)) <= 0) {
			
					System.out.println("r: "+r);
					
					b = Practical15_mr.myexp(two,r).multiply(d);
					
					//System.out.println("b: "+b);
					
					//System.out.println("myexp(a,b).mod(x): "+Practical15_mr.myexp(a,b).mod(x));
					
					if (Practical15_mr.expm(x,a,b).compareTo(x.subtract(BigInteger.ONE)) == 0) {
						
						result = true;
						a = Practical15_mr.gen_a(x);
						
					} 
					
					r = r.add(BigInteger.ONE);
				
				}
		
			}	
				
			t = t.subtract(BigInteger.ONE);
			
		}	
			
		return result;
		
	}
		
	public static void main(String[] args) {
	
		BigInteger t = new BigInteger("20");
		//BigInteger x = new BigInteger("973694665856161");
		BigInteger x = new BigInteger("1002241554019844925735664779985060165227393342081023284903459");
		//BigInteger x = new BigInteger("113");

		System.out.println("Is number "+x+" a prime? "+Practical15_mr.mr(x,t));
		
	}

}