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


public class Lab6 {



    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 ap proximation
        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;
    }
    /**
n=
5076313634899413540120536350051034312987619378778911504647420938544
7465177110314901155284204273194792744073890582538974985571109131603
02801741874277608327,
e=3
d=
3384209089932942360080357566700689541991746252519274336431613959029
8310118072592266557861250508877279212747197519861041620378008076415
22348207376583379547

* below find the factorization of the modulus
     */
    public static void main(String[] args) {

        BigInteger n = new BigInteger("837210799");

        BigInteger d = new BigInteger("478341751");
        BigInteger e = new BigInteger("7");
        BigInteger e2 = new BigInteger("17");
        BigInteger one = new BigInteger("1");
        BigInteger two = new BigInteger("2");
        BigInteger four = new BigInteger("4");

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


         k = k.add(one);
        System.out.println("K ii " +k);


        BigInteger s = (k.multiply((n.add(one))).add(one).subtract(((d.multiply(e)).subtract(one))).divide(k));

        System.out.println("S = " +s);





        BigInteger delta = s.multiply(s).subtract(four.multiply(n));

        System.out.println("Delta = " +delta);

        BigInteger root1, root2;
        BigInteger sqrt = SRoot(delta);

        System.out.println("RadicalDelta = " +sqrt);

        root1 = s.add(sqrt).divide(two);
        root2 = s.subtract(sqrt).divide(two);

        System.out.println("ROOT1 = " +root1 + "\n" + "ROOT2 = " +root2);


       BigInteger d1=e2.modInverse((root1.subtract(one)).multiply(root2.subtract(one)));
       System.out.println("d1: " + d1);
}

    public static BigInteger SRoot(BigInteger a){
         return NaiveSquareRootSearch(a, BigInteger.ZERO, a);
    }}