package cz.muni.fi.pv079.exercises04;

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;

/**
 * Class implements several algortihms for primality testing
 * 
 * @author Tomas Sedmik, tomas.sedmik@gmail.com
 * @since 2012-11-06
 */
public class PrimalityChecker {

    private static List<BigInteger> numbers = new ArrayList<BigInteger>();

    /**
     * Test if number is divisible by 2 or 3, then to check through all the numbers
     * of form 6k ± 1 <= sqrt(n).
     * Method is described here: http://en.wikipedia.org/wiki/Primality_test#Naive_methods
     * 
     * @param number testing number
     * @return true - number is prime, false - number is composite or zero or negative
     */
    private static boolean naiveIsPrime(BigInteger number) {

        if (number.signum() == -1 || number.signum() == 0) {
            return false;
        }

        if (number.equals(new BigInteger("1")) || number.equals(new BigInteger("2"))
                || number.equals(new BigInteger("3"))) {
            return true;
        }

        if (number.remainder(new BigInteger("2")).equals(BigInteger.ZERO)) {
            return false;
        }

        if (number.remainder(new BigInteger("3")).equals(BigInteger.ZERO)) {
            return false;
        }

        for (int i = 1; i < (Math.sqrt(number.doubleValue() - 1) / 6); i++) {

            int first = 6 * i + 1;
            int second = 6 * 1 - 1;

            if (number.remainder(new BigInteger(Integer.toString(first))).equals(BigInteger.ZERO)
                    || number.remainder(new BigInteger(Integer.toString(second))).equals(BigInteger.ZERO)) {

                return false;
            }
        }

        return true;
    }

    /**
     * Use Miller-Rabin primality test
     * Some info here:
     * http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Algorithm_and_running_time
     * 
     * primality test are also part of Java standard library (java.math.BigInteger)
     * 
     * @param number testing number
     * @return true - number is composite, false - number is probably prime, zero or negative
     */
    private static boolean probabilisticIsComposite(BigInteger number) {
        
        if (number.signum() == -1 || number.signum() == 0) {
            return false;
        }
        
        if (number.equals(new BigInteger("1")) || number.equals(new BigInteger("2"))
                || number.equals(new BigInteger("3"))) {
            return false;
        }

        if (number.remainder(new BigInteger("2")).equals(BigInteger.ZERO)) {
            return true;
        }

        // Miller-Rabin
        // 100 rounds for error 2ˆ-100
        int rounds = 100;
        BigInteger two = new BigInteger("2");
        for (int k = 0; k < rounds; k++) {
            
            // generate random number a : 1 < a < n-1
            // repeat if 'a' isn't in the interval
            BigInteger a;
            do {
                a = new BigInteger(number.bitCount(), new SecureRandom());
            } while (a.compareTo(two) < 0 || a.compareTo(number.subtract(BigInteger.ONE)) >= 0);                
          
            // compute 's' and 'd' such that n-1 = 2ˆs * d, where d is odd
            int s = 1;
            BigInteger d = number.subtract(BigInteger.ONE).divide(two);
            while (d.mod(two).equals(BigInteger.ZERO)) {
                d = d.divide(two);
                s++;
            }
            
            // x <-- aˆd mod n
            BigInteger x = a.modPow(d, number);
            if (x.equals(BigInteger.ONE) || x.equals(number.subtract(BigInteger.ONE))) {
                continue;
            }
            
            for (int r = 1; r < s; r++) {
                x = x.modPow(two, number);
                if (x.equals(BigInteger.ONE)) {
                    
                    // number is composite
                    return true;
                }
            }
        }
        
        return false;
    }

    /**
     * Fast deterministic test - Deterministic Miller-Rabin test
     * Info here:
     * http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
     * 
     * @param number testing number
     * @return true - number is prime, false - number is composite, zero or negative
     */
    private static boolean deterministicIsPrime(BigInteger number) {

        if (number.signum() == -1 || number.signum() == 0) {
            return false;
        }
        
        if (number.equals(new BigInteger("1")) || number.equals(new BigInteger("2"))
                || number.equals(new BigInteger("3"))) {
            return false;
        }

        if (number.remainder(new BigInteger("2")).equals(BigInteger.ZERO)) {
            return true;
        }

        // Deterministic Miller-Rabin        
        BigInteger two = new BigInteger("2");
        BigInteger m_zero = new BigInteger("-1");
        BigInteger limit = number.subtract(BigInteger.ONE);
        BigInteger a = new BigInteger("2");
        
        // compute 's' and 'd' such that n-1 = 2ˆs * d, where d is odd
        int s = 1;
        BigInteger d = number.subtract(BigInteger.ONE).divide(two);
        while (d.mod(two).equals(BigInteger.ZERO)) {
            d = d.divide(two);
            s++;
        }
            
        do {
            
            // x <-- aˆd mod n
            BigInteger x = a.modPow(d, number);
            
            // for all r in [0, s-1]
            for (int r = 0; r < s; r++) {
                
                // a^((2ˆr)*d) mod n
                BigInteger newX = a.modPow(two.pow(r).multiply(d), number);
                
                if (!x.equals(BigInteger.ONE) && !newX.equals(m_zero) && !newX.equals(number.subtract(BigInteger.ONE))) {
                    
                    // number is composite
                    return false;
                }
            }
            
            a.add(BigInteger.ONE);
            
        } while (a.compareTo(limit) > 0);
        
        return true;
    }

    public static void main(String[] args) {

        // prepare numbers        
        numbers.add(new BigInteger("45"));
        numbers.add(new BigInteger("294409"));
        numbers.add(new BigInteger("2").pow(34).add(BigInteger.valueOf(-1)));
        numbers.add(new BigInteger("2").pow(15).add(BigInteger.ONE));
        numbers.add(new BigInteger("29999856887"));
        numbers.add(new BigInteger("10153819680618218479901419131383363171764295930331359528212205495414872953389742271874906272354026775259001016704358783553372269"));

        // start testing
        for (BigInteger i : numbers) {
            
            long start = System.currentTimeMillis();

            // decide which method will be used (based on a size of tested number)
            // threshold is set: naivePrime < 2000 < probabilisticNotPrime | deterministicPrime
            // n <= 2000 ... 15 equations with naive method
            if (i.compareTo(new BigInteger("2000")) < 0) {
                System.out.print(i);
                if (naiveIsPrime(i)) {
                    System.out.print(" - Is prime");
                } else {
                    System.out.print(" - Not prime");
                }
            } else {
                System.out.print(i);
                if (probabilisticIsComposite(i)) {
                    System.out.print(" - Not prime");
                } else if (deterministicIsPrime(i)) {
                    System.out.print(" - Is prime");
                } else {
                    System.out.print(" - Not prime");
                }
            }
            
            long end = System.currentTimeMillis();
            System.out.println(" (" + (end - start) + " ms)");
        }
    }
}