/*
 * 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 javaapplication7;
import java.lang.Math;
import java.math.BigInteger;

/**
 *
 * @author student
 */
public class JavaApplication7 {


//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);
}





    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

       BigInteger four = new BigInteger("4");
        BigInteger two = new BigInteger("2");

        BigInteger n = new BigInteger("837210799");
        BigInteger e = new BigInteger("7");
        BigInteger d = new BigInteger("478341751");
        BigInteger e2 = new BigInteger("17");

        BigInteger de = d.multiply(e);
        BigInteger k = (de.subtract(BigInteger.ONE)).divide(n);

        BigInteger mymod = (de.subtract(BigInteger.ONE)).mod(n);
        if(mymod.compareTo(BigInteger.ZERO) != 0)
            k = k.add(BigInteger.ONE);

        BigInteger S = (((k.multiply(n.add(BigInteger.ONE))).add(BigInteger.ONE)).subtract(de)).divide(k);
        BigInteger delta = (S.pow(2)).subtract(n.multiply(four));
        BigInteger x1 = (S.add(SquareRoot(delta))).divide(two);
        BigInteger x2 = (S.subtract(SquareRoot(delta))).divide(two);

        System.out.println("S\n" + S+ "\ndelta\n"+delta +"\nx1\n" + x1 +"\nx2\n" + x2);

        BigInteger d2=(e2.modInverse(BigInteger.ONE)).mod(n);
        System.out.println("sal " + SquareRoot(new BigInteger("100")));
        System.out.println(d2);

}
}