ackage week8ex1;

import java.math.BigInteger;

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

    private static BigInteger NaiveCubicRootSearch(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(3).compareTo(a) == -1)&&(root.add(BigInteger.ONE).pow(3).compareTo(a) == 1))){
            if (root.pow(3).compareTo(a) == -1) root =
                    NaiveCubicRootSearch(a, root, right);
            if (root.pow(3).compareTo(a) == 1)
                root = NaiveCubicRootSearch(a, left, root);
        }
        return root;
    }

    public static BigInteger CubicRoot(BigInteger a){
        return NaiveCubicRootSearch(a, BigInteger.ZERO, a);
    }
    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 ex1(){
        BigInteger c = new BigInteger("1375865583010982618632308529423371271821438577980922927124130396877925863587827122886875024570556859122064458153631");
        System.out.println("Message:\n" + CubicRoot(c));
    }

    public static void ex2(){
        BigInteger four = new BigInteger("4");
        BigInteger two = new BigInteger("2");

        BigInteger n = new BigInteger("5076313634899413540120536350051034312987619378778911504647420938544746517711031490115528420427319479274407389058253897498557110913160302801741874277608327");
        BigInteger e = new BigInteger("3");
        BigInteger d = new BigInteger("3384209089932942360080357566700689541991746252519274336431613959029831011807259226655786125050887727921274719751986104162037800807641522348207376583379547");
        //k = (d*e - 1) / n
        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);
        //s = (k*(n+1)+1-de)/k
        BigInteger S = (((k.multiply(n.add(BigInteger.ONE))).add(BigInteger.ONE)).subtract(de)).divide(k);
        //x^2 - S*x + n = 0
        //delta = S^2 - 4 * n
        BigInteger delta = (S.pow(2)).subtract(n.multiply(four));
        //fact1,2 = (S +- sqr(delta)/2
        BigInteger fact1 = (S.add(SquareRoot(delta))).divide(two);
        BigInteger fact2 = (S.subtract(SquareRoot(delta))).divide(two);

        System.out.println("The factors of the modulus are:\n" + fact1 + "\nand\n" + fact2);
    }

    public static void ex3(){
        BigInteger n = new BigInteger("10700646585680885848520503735299852478865837438709815138992859883249955498916287857233627498606657866763592788339595921943627412052904161935201780928478603");
        BigInteger x = new BigInteger("7133764390453923899013669156866568319243891625806543425995239922166636999277387253194048505767340924598064169304136210581809906511216168762318630818311867");
        System.out.println(x.mod(n));
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ex1();
        //ex2();
        //p*q = n
        //x^(p+q) mod (p*q)
        // x ^ (p+q) = x mod (p+q)
    }

}