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

/*
 * 
 * Author: Sebastian Wolfgarten, sebastian@wolfgarten.com
 * Date: 05/March/2005
 * Description: Generates a prime of a given size by using Fermat's algorithm
 *
 **/

public class Practical12_prime {

	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 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);
			
			r = Practical12_prime.expm(n,a,n.subtract(BigInteger.ONE));
			i = i.add(BigInteger.ONE);

			if (r.compareTo(BigInteger.ONE) != 0) return false;
						
		}	
			
		return true;
		
	}
	
	public static BigInteger prime(BigInteger d) {
		
		BigInteger prime = new BigInteger(d.bitLength(),new SecureRandom());
		BigInteger t = new BigInteger("10");
		
		while (Practical12_prime.fermat(prime,t) == false) {
			
			prime = new BigInteger(d.bitLength(),new SecureRandom());
			
		}
			
		return prime;		
		
	}
	
	public static void main(String[] args) {
		
		BigInteger d = new BigInteger("1000");
		
		System.out.println("Generating a d-bit prime..."+Practical12_prime.prime(d));

	}

}