/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package daa;
import java.math.BigInteger;
/**
 *
 * @author student
 */
public class Daa {


    /**
* @param args the command line arguments
*/
//recursively searches for the sqr root of a in interval [left, right]
private static BigInteger NaiveSquareRootSearch(BigInteger a, BigInteger left,BigInteger right)
{
// fix root as the arithmetic mean of left and right
BigInteger root = left.add(right).shiftRight(1);
// if the root is not between [root, root+1],
//is not an integer and root is our best integer approximation
if(!((root.pow(2).compareTo(a) == -1)&&(root.add(BigInteger.ONE).pow(2).compareTo(a) == 1))){
if (root.pow(2).compareTo(a) == -1) root = NaiveSquareRootSearch(a, root,right);
if (root.pow(2).compareTo(a) == 1) root = NaiveSquareRootSearch(a, left,root);
}
return root;
}

public static BigInteger SquareRoot(BigInteger a)
{
return NaiveSquareRootSearch(a, BigInteger.ZERO, a);
}
    public static void main(String[] args) {

        // TODO code application logic here
        BigInteger n= new BigInteger ("5076313634899413540120536350051034312987619378778911504647420938544746517711031490115528420427319479274407389058253897498557110913160302801741874277608327");
        BigInteger e= new BigInteger ("3");
        BigInteger d= new BigInteger ("3384209089932942360080357566700689541991746252519274336431613959029831011807259226655786125050887727921274719751986104162037800807641522348207376583379547");
        BigInteger zero= new BigInteger ("0");
        BigInteger unu= new BigInteger ("1");
        BigInteger doi= new BigInteger ("2");
        BigInteger patru= new BigInteger ("4");
        BigInteger k;
        if(((((d.multiply(e)).subtract(unu)).mod(n)).equals(zero))){
            k = ((((d.multiply(e)).subtract(unu)).divide(n)));
        }
        else{
                k = ((((d.multiply(e)).subtract(unu)).divide(n))).add(unu);
            }
        System.out.println("K = " + k);
        BigInteger sum = ((((n.add(unu)).multiply(k)).add(unu)).subtract(e.multiply(d))).divide(k);
        BigInteger del = (sum.pow(2)).subtract(patru.multiply(n));
        BigInteger radical = SquareRoot(del);
        BigInteger x1 = (sum.add(radical)).divide(doi);
        System.out.println("x1 = " + x1);
        BigInteger x2 = (sum.subtract(radical)).divide(doi);
        System.out.println("x2 = " + x2);
        BigInteger pro = x1.multiply(x2);
        System.out.println("x1*x2 = " + pro);
    }

}