import java.math.BigInteger;
import java.util.Random;
import javax.swing.JOptionPane;
/*
 * BigCoinFlipping.java
 *
 * Created on January 13, 2005, 8:39 PM
 */

/**
 *
 * @author kraynek
 */
public class BigCoinFlipping {
    BigInteger two = new BigInteger("2");
    int bits;
    
    /** Creates a new instance of BigCoinFlipping */
    public BigCoinFlipping() {
        bits = Integer.parseInt(JOptionPane.showInputDialog("Enter the number of bits for the primes","128"));
        BigInteger p = getBlumPrime(bits);
        BigInteger q = getBlumPrime(bits);
        while( q.equals(p) ) q = getBlumPrime(bits);
        BigInteger n = p.multiply(q);
        System.out.println("p= " + p + " q = " + q + " and n = " +n);
        while( true ) {
            BigInteger x = getX(n);
            BigInteger y = getY(x,n);
            String guess = JOptionPane.showInputDialog("y = " + y + ". Enter your guess, heads or tails");
            if( guess == null ) break;
            String flipResult = flip(x,n);
            String result = "Result: Correct! ";
            if( !flipResult.equals(guess) ) result = "Result: Wrong! ";
            result += "x = " + x + " and Jacobi = " + bigJacobi(x,n) + "\n";
            JOptionPane.showMessageDialog(null,"y = " + y + "\n"+ result);
        } // end while
        
    } // end CoinFlipping
    
    BigInteger getBlumPrime(int bits) {
        Random rnd = new Random();
        BigInteger blum = BigInteger.probablePrime(bits,rnd);
        while( blum.mod(new BigInteger("4")).intValue() != 3 ) {
            blum = BigInteger.probablePrime(bits,rnd);
        } // end while
        return blum;
    } // end getBlumPrime
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        new BigCoinFlipping();
    } // end main
    
    int bigJacobi(BigInteger x, BigInteger n) {
        if( x.equals(BigInteger.ONE) ) return 1;
        if( x.mod(two).equals(BigInteger.ZERO) ) {
            int r = bigJacobi(x.divide(two),n);
            if( (((n.multiply(n).subtract(BigInteger.ONE)).divide(new BigInteger("8"))).mod(two)).equals(BigInteger.ZERO) ) return r;
            else return -r;
        } // end for
        int r = bigJacobi(n.mod(x),x);
        if( (((x.subtract(BigInteger.ONE)).multiply((n.subtract(BigInteger.ONE))).divide(new BigInteger("4"))).mod(two)).equals(BigInteger.ZERO) ) return r;
        return -r;
    } // end jacobi
    
    BigInteger getX(BigInteger n) {
        Random rnd = new Random();
        BigInteger randomInt = new BigInteger(bits,rnd);
        while( randomInt.gcd(n).intValue() != 1 ) {
            randomInt = new BigInteger(bits,rnd);
        } // end while
        return randomInt;
    } // end getX
    
    BigInteger getY(BigInteger x, BigInteger n) {
        return x.modPow(two,n);
    } // end getY
    
    String flip(BigInteger x, BigInteger n) {
        int i = bigJacobi(x,n);
        if( i == 1 ) return "heads";
        return "tails";
    } // end flip
    
}