import java.math.BigInteger;

/**
 * Created by Bogdanel on 25.04.2017.
 */
public class Wiener {

    private BigInteger e;
    private BigInteger N;
    private BigInteger p;
    private BigInteger q;



    public Wiener(BigInteger e, BigInteger N){
        this.e = e;
        this.N = N;
        p = new BigInteger("0");
        q = new BigInteger("0");
    }


    void function(){

        BigInteger qi1, qi2, qi3;
        BigInteger alphai1, alphai2, alphai3;
        BigInteger betai1, betai2, betai3;
        BigInteger rem, rem1, rem2;
        rem1 = e;
        rem2 = N;

        BigInteger aRez[] = rem1.divideAndRemainder(rem2);
        qi1 = aRez[0];
        rem1 = rem2;
        rem = aRez[1];
        rem2 = aRez[1];

        BigInteger bRez[] = rem1.divideAndRemainder(rem2);
        qi2 = bRez[0];
        rem1 = rem2;
        rem = bRez[1];
        rem2 = bRez[1];

        alphai1 = aRez[0];
        alphai2 = qi1.multiply(qi2).add(BigInteger.ONE);

        betai1 = BigInteger.ONE;
        betai2 = qi2;

        if(criterion(alphai2, betai2)){
            System.out.println("found");
            return;
        }

        while(rem.intValue() != 0){
            BigInteger[] div = rem1.divideAndRemainder(rem2);
            rem1 = rem2;
            rem = div[1];
            rem2 = rem;
            qi3 = div[0];

            alphai3 = qi3.multiply(alphai2).add(alphai1);
            alphai1 = alphai2;
            alphai2 = alphai3;

            betai3 = qi3.multiply(betai2).add(betai1);
            betai1 = betai2;
            betai2 = betai3;

            System.out.println("Alpha : " + alphai3 + "    BETa : " + betai3);

            if(criterion(alphai3, betai3)){
                System.out.println("Succes");
                BigInteger phi = p.subtract(BigInteger.ONE).multiply(p.subtract(BigInteger.ONE));
                BigInteger d = e.modInverse(phi);

                System.out.println("Cheia privata este : " + d);
                return;
            }

        }

    }


    //x*y = N   (x-1)*(y-1) = (E * D - 1)/L trebuie sa aiba solutii intregi
    //echivalent y = ((+-)sqrt(delta)-b)/2 -> prima sol e Q cealalta P

    //delta = b*b - 4*N
    //b=(e*d-1)/L) - N - 1

    boolean criterion(BigInteger L, BigInteger D){

        BigInteger b;
        BigInteger delta;

        BigInteger first = e.multiply(D);
        first = first.subtract(BigInteger.ONE);
        if(L.intValue() == 0)
            return false;
        //check if first L divides b\
        //
        if(!first.mod(L).equals(BigInteger.ZERO))
            return false;
        first = first.divide(L);


        //
       // b=first-n-1
        b = first.subtract(N).subtract(BigInteger.ONE);

        b = N.subtract(first).add(BigInteger.ONE);

        //formam delta: b*b
        delta = b.multiply(b);

        //-4*N
        delta  = delta.subtract(N.multiply(new BigInteger("4")));
        if(delta.compareTo(BigInteger.valueOf(0)) < 1){
            return false;
        }
        BigInteger y;

        BigInteger sqrtDelta = bigIntSqRootFloor(delta);


        if(sqrtDelta.multiply(sqrtDelta).equals(delta) == false)
            return false;
        //p = sqrt(delta)-b

        p = sqrtDelta.subtract(b);

        if(sqrtDelta.mod(new BigInteger("2")).intValue() == 1) {
            p = BigInteger.ZERO;
            return false;
        }

        p = p.divide(new BigInteger("2"));
        System.out.println("P" + p);

        //q = (-sqrtdelta - b)/2

        q = sqrtDelta.multiply(new BigInteger("-1"));
        q = q.subtract(b);
        q = q.divide(new BigInteger("2"));

        return true;


    }


    public static BigInteger bigIntSqRootFloor(BigInteger x)
            throws IllegalArgumentException {
        if (x.compareTo(BigInteger.ZERO) < 0) {
            throw new IllegalArgumentException("Negative argument.");
        }
        if (x .equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
            return x;
        }
        BigInteger two = BigInteger.valueOf(2L);
        BigInteger y;

        for (y = x.divide(two);
             y.compareTo(x.divide(y)) > 0;
             y = ((x.divide(y)).add(y)).divide(two));
        return y;
    }


    public BigInteger getP(){
        return p;
    }
    public BigInteger getQ(){
        return q;
    }

    public static void main(String[] args) {
       // GenerateKeys generator = GenerateKeys.getInstance();

        BigInteger N = new BigInteger("64741");
        BigInteger e = new BigInteger("42667");
        Wiener wiener = new Wiener(e, N);

        BigInteger a = new BigInteger("2");
        BigInteger b = new BigInteger("3");

        wiener.function();

    }

}