import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;

public class RabinMiller {

	private static final BigInteger ZERO = BigInteger.ZERO;
	private static final BigInteger TWO = new BigInteger("2");
	private static final BigInteger THREE = new BigInteger("3");
	private ArrayList<BigInteger> primes;

	public RabinMiller(){
		primes = new ArrayList<BigInteger>();
		primes.add(new BigInteger("2"));
		primes.add(new BigInteger("3"));
		primes.add(new BigInteger("5"));
		primes.add(new BigInteger("7"));
	}

	/**
	 *
	 * @param number
	 * @return
	 */
	public boolean isPrime(BigInteger number){
		if(number.compareTo(THREE) < 0) return true;
		if(primes.contains(number)) return true;

		for(BigInteger a : primes)
			if(number.mod(a).equals(ZERO))
				return false;

		int s = 0;
		BigInteger d = number.subtract(new BigInteger("1"));

		//While d is even divide d until it's an odd number
		while(d.mod(TWO).equals(ZERO)) {
			s++;
			d = d.divide(TWO);
		}

		for(int i = 0; i < 20; i++){
			BigInteger a = randomBigInteger(number);
			if(tryComposite(a, d, number, s)) return false;
		}
		return true;
	}

	/**
	 * Get a random BigInteger
	 * @param range
	 * @return random BigInteger
	 */
	private BigInteger randomBigInteger(BigInteger range){
		BigInteger a;

		Random rand = new Random();
		do{
			a = new BigInteger(range.bitLength(), rand);
		} while(a.compareTo(TWO) < 0 || a.compareTo(range) >= 0);

		return a;
	}

	/**
	 *
	 * @param a
	 * @param d
	 * @param n
	 * @param s
	 * @return
	 */
	private boolean tryComposite(BigInteger a, BigInteger d, BigInteger n, int s) {
//		BigInteger x = powMod(a, d, n);
		BigInteger x = a.modPow(d, n);
		if(x.equals(BigInteger.ONE) || x.equals(n.subtract(BigInteger.ONE))) return false;

		int j = 1;
		for(; j < s; j++){
//			if(a.modPow(TWO.pow(j).multiply(d), n).equals(n.subtract(BigInteger.ONE))) return false;
			if(x.modPow(TWO, n).equals(n.subtract(BigInteger.ONE))) return false;
		}

		return true;
	}

	/**
	 *
	 * @param base
	 * @param exp
	 * @param mod
	 * @return
	 */
	private BigInteger powMod(BigInteger base, BigInteger exp, BigInteger mod) {
		if(base.equals(ZERO)) return ZERO;
		if(exp.equals(BigInteger.ONE)) return BigInteger.ONE;

		if(exp.mod(TWO).equals(ZERO)) {
			return powMod(base, exp.divide(TWO), mod).pow(2).mod(mod);
		} else {
			return base.multiply(powMod(base, exp.subtract(BigInteger.ONE), mod)).mod(mod);
		}
	}

	public BigInteger generate_prime(int bits){
		Random rand = new Random();
		while(true){
			BigInteger p = new BigInteger(bits, rand);
			if(isPrime(p)) return p;
		}
	}

	/**
	 * Main
	 * @param args
	 */
	public static void main(String[] args){
		RabinMiller rm = new RabinMiller();
		BigInteger prime1 = new BigInteger("1");
		BigInteger prime2 = new BigInteger("17");
		BigInteger prime3 = new BigInteger("18");
		BigInteger prime4 = new BigInteger("15485863");
		BigInteger prime5 = new BigInteger("15485864");
		ArrayList<BigInteger> generated_primes = new ArrayList<BigInteger>();

		long startTime = System.nanoTime();
		for(int i = 0; i < 100; i++){
			generated_primes.add(rm.generate_prime(512));
		}
		long endTime = System.nanoTime();
		double timeSec = (endTime-startTime) / 1000000000;

		int i = 0;
		for(BigInteger b : generated_primes){
			System.out.println(i + ": " + b);
			i++;
		}
		System.out.println("time taken in seconds: " + timeSec);

	}
}