import java.math.*;
import java.io.*;
import java.util.*;


/*
 Written by

  Yip,Alexander S : yipal@MIT.EDU
  Yuditskaya,Sophia C : scyudits@MIT.EDU
  Hydari,Muhammad Z. : hydari@MIT.EDU
 
 October 2, 2001

 May be freely reproduced for educational or personal use
*/


public class FindPrime {
    
    
    static final int NO_OF_TRIES=256;


    public static void testCarmichaelNumbers() {

        // Obtained from ftp.dpmms.cam.ac.uk/pub/Carmichael/carmichael-14.gz
        String[] carMichaelNumbers = new String[]
        {"561", "1105", "1729", "2465", "2821", "6601", "8911", "10585", "15841", 
         "29341", "41041", "46657", "52633", "62745", "63973", "75361", "101101", "115921", "126217",
         "162401","146843929", "161242705", "2023528501"};
        
        boolean failure=false;
        for (int i=0; i<carMichaelNumbers.length; i++) {
            if (isPrime(new BigInteger("7"), new BigInteger(carMichaelNumbers[i]))) {
                System.out.println("CarMichael number " + carMichaelNumbers[i] + 
                                   "was declared a prime");
                failure=true;
        
            }
        }
        if (!failure) { 
            System.out.println("All 23 Carmichael numbers passed the test: ");
            for (int i=0; i<carMichaelNumbers.length; i++) {
                System.out.println(carMichaelNumbers[i]);
            }
        }
    }
    
    
    public static byte[] randomBytePair() {
        // generate two random bytes 
        // first byte can take any value whereas the second is always odd
        // this results in an odd number when these two bytes are 
        // appended

        byte penultimate = (byte)(256*Math.random());
        // Avoids generating even numbers
        byte last = (byte)(256*Math.random());
        while ( last%2 == 0 ) {
            last = (byte)(256*Math.random());
        }

        byte[] randomPair = new byte[2];
        randomPair[0] = penultimate;
        randomPair[1] = last;
        return randomPair;
    }
    
    
    public static boolean isDivisibleBy3or5or7(BigInteger p) {
        BigInteger zero = new BigInteger("0");
        BigInteger three = new BigInteger("3");
        BigInteger five = new BigInteger("5");
        BigInteger seven = new BigInteger("7");
        
        return (  p.mod(three).equals(zero)  || 
                  p.mod(five).equals(zero)  || 
                  p.mod(seven).equals(zero)  );
    }
    
    public static boolean isPrime(BigInteger a, BigInteger p) {
        BigInteger zero = new BigInteger("0");
        BigInteger one = new BigInteger("1");
        BigInteger two = new BigInteger("2");
        BigInteger pMinus1 = p.subtract(one);
        
        int t=0;
        BigInteger u = p.subtract(one);
        while (zero.equals(u.mod(two))) {
            u = u.divide(two);  
            t++;
        }
        
        BigInteger x_i = a.modPow(u, p);
        BigInteger x_iminus1 = x_i;
        for (int i=1; i<=t; i++) {
            x_iminus1 = x_i;
            x_i = x_iminus1.modPow(two, p);
            
            if (x_i.equals(one)) {
                if ( ! ( x_iminus1.equals(one) || x_iminus1.equals(pMinus1) )) {
                    return false;
                }
            }
        }
        
        if (x_i.equals(one))    
            return true;
        else 
            return false;
    }
    
    
    public static boolean MillerRabin(BigInteger p, int trials, int approxNumBits) {
        Random rnd = null;
        BigInteger a = null;
        
        for (int k=0; k<trials; k++) {  
            rnd = new Random(System.currentTimeMillis());
            a = new BigInteger(approxNumBits, rnd);
            if (!isPrime(a, p)) return false;
        }
        return true;
    }
    
    
    public static BigInteger findPrime(byte[] m) {
        int msgLength = m.length;
        byte[] m00 = new byte[msgLength+2];
        
        for (int i=0; i<msgLength; i++) 
            m00[i] = m[i];
        
    
        m00[msgLength] = 0;
        m00[msgLength+1] =0;
        System.out.println(new BigInteger(m00) + " is the original number.");
        

        byte[] lastTwoBytes = null;
        lastTwoBytes = randomBytePair();
        m00[msgLength] = lastTwoBytes[0];
        m00[msgLength+1] = lastTwoBytes[1];
        BigInteger primeCandidate = new BigInteger(m00);
        
        // this loop is for testing all sensible combinations of the last two bytes
        for (int j=0; j<32000; j++) { 
            if (! isDivisibleBy3or5or7(primeCandidate)) {           
                if ( MillerRabin(primeCandidate, NO_OF_TRIES, msgLength*8) ) {
                    return primeCandidate;
                } 
                
            }
            
            lastTwoBytes = randomBytePair();
            m00[msgLength] = lastTwoBytes[0];
            m00[msgLength+1] = lastTwoBytes[1];
            primeCandidate = new BigInteger(m00);
        }
        return BigInteger.valueOf(0);
    }
    
    
    public static void main(String args[]) {
        if (args.length != 1) {
            System.out.println("Usage: java FindPrime <msg>");
            System.exit(1);
        }
        
        if (args[0].equals("-t")) {
            testCarmichaelNumbers();
            System.exit(0);
        }
                
        String msg = args[0];
        byte[] m   = msg.getBytes();
        BigInteger big = FindPrime.findPrime(m);
        System.out.println(big + " is a likely prime.");
    }
}