import javax.swing.JOptionPane;
import java.math.BigInteger;
import java.util.Random;
import java.util.TreeSet;
import java.util.Set;
import java.util.Iterator;
import javax.swing.JTextArea;
import javax.swing.JScrollPane;
import java.util.Random;

public class CoinFlipping {
    BigInteger two = new BigInteger("2");
    
    public CoinFlipping() {
        
        String pString = JOptionPane.showInputDialog("Enter a prime p satisfying p = 3mod4","11");
        if(pString == null) return;
        String qString = JOptionPane.showInputDialog("Enter a prime q satisfying q = 3mod4","3");
        if(qString == null) return;
        int bits = 0;
        BigInteger p = new BigInteger(pString);
        BigInteger q = new BigInteger(qString);
        /*
        int bits = 8;
        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);
        Set<BigInteger> Z = new TreeSet<BigInteger>();
        for( int i = 1; i < n.intValue(); i++ ) {
            BigInteger bigI = new BigInteger(i+"");
            if( bigI.gcd(n).intValue() == 1 ) Z.add(bigI);
        } // end for
        String out = "";
        Iterator itr = Z.iterator();
        while( itr.hasNext() ) {
            BigInteger next = (BigInteger)itr.next();
            //if(next.modPow(two,n).intValue() == 1 )
                out += "x = " + next + "  , y = " + next.modPow(two,n) + " and  (x/n) = " + bigJacobi(next,n) + "\n";
        } // end while
        String outString = out;
        JTextArea outArea = new JTextArea(outString,20,50);
        JOptionPane.showMessageDialog(null,new JScrollPane(outArea));
        String pad = "";
        for(int i = 0; i < bits; i++) pad+= " ";
        outString = "x  " + pad + "      y            Guess   Flip Result\n";
        for( int i = 0; i < 10; i++ ) {
            BigInteger x = getX(Z,n);
            BigInteger y = getY(x,n);
            String flipResult = flip(x,n);
            outString += x + "    " + y + "         heads    " + flipResult  + "\n";
        } // end for
        JOptionPane.showMessageDialog(null,outString);
        while( true ) {
            BigInteger x = getX(Z,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,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
    
    public static void main(String[] a) {
        new CoinFlipping();
    } // 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(Set Z, BigInteger n) {
        Random rnd = new Random();
        BigInteger randomInt = new BigInteger("-1");
        while( !Z.contains(randomInt) ) {
            randomInt = new BigInteger(rnd.nextInt(n.intValue())+"");
        } // 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
    
} // CoinFlipping