VQC

package rsa.release;

import java.math.BigInteger;
import java.util.*;

import static rsa.release.unseeIt.Lib.*;

public class unseeIt {
    public static void main(String[] args) throws InterruptedException {
        VQC vqc = new VQC();
        Scanner s = new Scanner(System.in);

        outer:
        for (;;) {
            BigInteger c = s.nextBigInteger();
            BigInteger d = sqrt(c);
            BigInteger e = c.subtract(d.multiply(d));
            BigInteger f = two.multiply(d).add(one).subtract(e);
            BigInteger I = c.add(one).divide(two);
            BigInteger i = zero;

            /* calculating elements d is between */
            System.out.println("D:");
            VQCElement D  = vqc.getElementBelowRoot(e, one, d);
            BigInteger j_D = D.j;

            VQCElement D2 = vqc.getElement(e, one, D.t.add(one));
            BigInteger j_D2 = D2.j;

            System.out.println(D);
            System.out.println(D2);
            System.out.println();

            System.out.println("D_f:");
            VQCElement D_f  = vqc.getElementBelowRoot(f.negate(), one, d);
            BigInteger j_D_f = D_f.j;

            VQCElement D_f2 = vqc.getElement(f.negate(), one, D_f.t.add(one));
            BigInteger j_D_f2 = D_f2.j;

            System.out.println(D_f);
            System.out.println(D_f2);

            /* calculating offset between e and -f */
            BigInteger d1 = D.d;
            BigInteger d2 = vqc.getElement(f.negate(), one, D2.t).d;
            BigInteger delta = d2.subtract(d1);

            BigInteger d3 = D2.d;
            BigInteger d4 = vqc.getElement(f.negate(), one, D2.t.add(one)).d;
            BigInteger delta2 = d4.subtract(d3);

            BigInteger offset = delta.subtract(delta2).abs();
            System.out.println("offset = " + offset);

            /* tree set for subsequent rows */
            TreeSet<BigInteger> rows = new TreeSet<BigInteger>();
            BigInteger nextRow = one;

            long calculations = 0;
            long iterations = 1;
            long increment = 0;
            boolean started = true;
            for (;;) {
                if (calculations > 10000 || gt(i, I)) {
                    System.out.println("not");
                    System.out.println();
                    continue outer;
                }

                calculations += 1;
                i = D.i;
                if (isCorrectRoot(i, c)) break;

                calculations += 1;
                i = vqc.getElement(e, one, D.t.add(one)).i;
                if (isCorrectRoot(i, c)) break;

                calculations += increment;
                i = D2.i;
                if (isCorrectRoot(i, c)) break;

                calculations += 1;
                i = vqc.getElement(e, one, D2.t.add(one)).i;
                if (isCorrectRoot(i, c)) break;

                calculations += 1;
                i = D_f.i;
                if (isCorrectRoot(i, c)) break;

                calculations += increment;
                i = vqc.getElement(f.negate(), one, D_f.t.add(one)).i;
                if (isCorrectRoot(i, c)) break;

                calculations += 1;
                i = D_f2.i;
                if (isCorrectRoot(i, c)) break;

                calculations += increment;
                i = vqc.getElement(f.negate(), one, D_f2.t.add(one)).i;
                if (isCorrectRoot(i, c)) break;

                //because of the loop structure, some calculations are repeated, those are not counted as part of the complexity
                if (!started) {
                    increment = 1;
                }

                /* recursive row calculations */
                VQCElement queryElement = vqc.getElement(e, one, BigInteger.valueOf(iterations));
                rows.add(queryElement.a);
                rows.add(queryElement.b);

                VQCElement A = AlgorithmLib.seeIt(queryElement.a);
                VQCElement B = AlgorithmLib.seeIt(queryElement.b);
                rows.add(A.a);
                rows.add(A.b);
                rows.add(B.a);
                rows.add(B.b);

                Iterator<BigInteger> iterator = rows.descendingIterator();
                if (iterator.hasNext()) {
                    nextRow = iterator.next();
                } else {
                    i = I;
                    break;
                }

                D = vqc.getElement(e, nextRow, j_D);
                D2 = vqc.getElement(e, nextRow, j_D2);
                D_f = vqc.getElement(f.negate(), nextRow.subtract(one), j_D_f);
                D_f2 = vqc.getElement(f.negate(), nextRow.subtract(one), j_D_f2);

                iterations++;

                /*
                can also be done backwards
                D = vqc.getElement(e, one, D.j.negate());
                D2 = vqc.getElement(e, one, D2.j.negate());
                D_f = vqc.getElement(e, one, D_f.j.negate());
                D_f2 = vqc.getElement(e, one, D_f2.j.negate());
                */
            }

            System.out.println("calculations = " + calculations);
            System.out.println("nextRow = " + nextRow);
            System.out.println("D = " + D);
            System.out.println("D_f = " + D_f);
            BigInteger i2 = i.multiply(i);
            BigInteger j2 = i2.subtract(c);
            BigInteger j = sqrt(j2);
            BigInteger b = i.add(j);
            BigInteger a = i.subtract(j);
            System.out.println("c = " + a + " * " + b);
            System.out.println();
        }
    }

    private static boolean isCorrectRoot(BigInteger i, BigInteger c) {
        BigInteger i2 = i.multiply(i);
        BigInteger j2 = i2.subtract(c);

        if (!lt(j2, one)) {
            if (isSquare(j2)) {
                System.out.println("match");
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    private static class AlgorithmLib {
        private static VQC vqc = new VQC();

        public static VQCElement seeIt(BigInteger c) {
            BigInteger d = sqrt(c);
            BigInteger e = c.subtract(d.multiply(d));
            BigInteger f = two.multiply(d).add(one).subtract(e);
            BigInteger i = zero;
            BigInteger I = c.add(one).divide(two);

            VQCElement D = vqc.getElementBelowRoot(e, one, d);
            VQCElement D2 = vqc.getElement(e, one, D.t.add(one));

            VQCElement D_f = vqc.getElementBelowRoot(f.negate(), one, d);
            VQCElement D_f2 = vqc.getElement(f.negate(), one, D_f.t.add(one));

            TreeSet<BigInteger> rows = new TreeSet<BigInteger>();

            long iterations = 0;
            for (; ; ) {
                if (gt(i, I)) {
                    i = I;
                    break;
                }

                i = D.i;
                if (seeItImpl(i, c)) break;

                i = vqc.getElement(e, D.n, D.t.add(one)).i;
                if (seeItImpl(i, c)) break;

                i = D2.i;
                if (seeItImpl(i, c)) break;

                i = vqc.getElement(e, D2.n, D2.t.add(one)).i;
                if (seeItImpl(i, c)) break;

                i = D_f.i;
                if (seeItImpl(i, c)) break;

                i = vqc.getElement(f.negate(), D_f.n, D_f.t.add(one)).i;
                if (seeItImpl(i, c)) break;

                i = D_f2.i;
                if (seeItImpl(i, c)) break;

                i = vqc.getElement(f.negate(), D_f2.n, D_f2.t.add(one)).i;
                if (seeItImpl(i, c)) break;

                iterations++;

                VQCElement queryElement = vqc.getElement(e, one, BigInteger.valueOf(iterations));
                rows.add(queryElement.a);
                rows.add(queryElement.b);

                if (queryElement.a.equals(zero)) {
                    i = I;
                    break;
                } else if (queryElement.a.equals(one)) {
                    i = I;
                    break;
                }

                if (!queryElement.a.mod(four).equals(two)) {
                    VQCElement A = AlgorithmLib.seeIt(queryElement.a);
                    rows.add(A.a);
                    rows.add(A.b);
                }

                if (!queryElement.b.mod(four).equals(two)) {
                    VQCElement B = AlgorithmLib.seeIt(queryElement.b);
                    rows.add(B.a);
                    rows.add(B.b);
                }

                BigInteger nextRow;
                Iterator<BigInteger> iterator = rows.iterator();
                if (iterator.hasNext()) {
                    nextRow = iterator.next();
                } else {
                    i = I;
                    break;
                }

                D = vqc.getElement(e, one, D.j);
                D2 = vqc.getElement(e, one, D2.j);
                D_f = vqc.getElement(e, one, D_f.j);
                D_f2 = vqc.getElement(e, one, D_f2.j);
            }

            BigInteger n = i.subtract(d);
            BigInteger x = sqrt(i.multiply(i).subtract(c)).subtract(d);
            BigInteger t = vqc.getT(e, x);

            return vqc.getElement(e, n, t);
        }

        private static boolean seeItImpl(BigInteger i, BigInteger c) {
            BigInteger i2 = i.multiply(i);
            BigInteger j2 = i2.subtract(c);

            if (!lt(j2, one)) {
                return isSquare(j2);
            } else {
                return false;
            }
        }

        public static VQCElement iterateCell(BigInteger e, BigInteger n, BigInteger t, BigInteger c, BigInteger increment) {
            VQC vqc = new VQC();

            long iterations = 0;
            for (; ; ) {
                iterations++;

                t = t.add(increment);
                VQCElement test = vqc.getElement(e, n, t);

                BigInteger a = test.a.gcd(c);

                if (!a.equals(one)) {
                    System.out.println("iterations = " + iterations);

                    BigInteger d = sqrt(c);
                    BigInteger x = d.subtract(a);

                    return test;
                    //return vqc.getElement(e, n, vqc.getT(e, x));
                }
            }
        }
    }

    private static class VQC {
        public VQC() {
        }

        public VQCElement getElement(BigInteger e, BigInteger n, BigInteger t) {
            VQCElement v = new VQCElement();
            v.e = e;
            v.n = n;
            v.t = t;

            if (e.equals(zero) || n.equals(zero)) {
                v.x = zero;
                v.a = v.t;
                v.d = v.a;
                v.b = v.a;
                v.c = t.multiply(t);
                v.f = two.multiply(v.d).add(one).subtract(v.e);
                v.i = v.d;
                v.j = zero;

                return v;
            }

            v.x = getX(e, t);

            /* define a(x) = ((x^2 + e) / (2*n)) // 1 */
            v.a = (v.x.pow(2)).add(e).divide(two.multiply(v.n));

            /* define define d(x) = ((x^2 + e) / (2*n) + x) // 1 */
            v.d = v.a.add(v.x);
            v.f = two.multiply(v.d).add(one).subtract(v.e);
            v.b = v.a.add(two.multiply(v.x)).add(two.multiply(v.n));
            v.c = v.a.multiply(v.b);
            v.i = v.d.add(v.n);
            v.j = v.x.add(v.n);

            return v;
        }

        /* Get closest element with d value below input d in (e, n)
         * The element above it can be calculated to give the two elements whose d values d is between */
        public VQCElement getElementBelowRoot(BigInteger e, BigInteger n, BigInteger d) {
            BigInteger c = d.multiply(d).add(e);
            BigInteger xpn = sqrt(d.add(n).pow(2).subtract(c));
            BigInteger x = xpn.subtract(n);
            boolean eIsEven = isEven(e);
            boolean xIsEven = isEven(x);

            if (!(eIsEven == xIsEven)) {
                x = x.subtract(one);
            }

            return getElement(e, n, getT(e, x));
        }

        public VQCElement getEntryElement(BigInteger c) {
            BigInteger d = sqrt(c);
            BigInteger e = c.subtract(d.multiply(d));
            BigInteger N = c.add(one).divide(two).subtract(d);
            BigInteger X = d.subtract(one);
            BigInteger T = getT(e, X);

            return getElement(e, N, T);
        }

        public BigInteger getEvenColumn(BigInteger e, BigInteger negative_f) {
            if (!isEven(e)) {
                return negative_f;
            } else {
                return e;
            }
        }

        public VQCElement getFactorizationElement(VQCElement c1, BigInteger n) {
            VQCElement ab = c1.clone();

            ab.n = n;
            ab.i = ab.d.add(ab.n);

            BigInteger i2 = ab.i.pow(2);
            BigInteger j2 = i2.subtract(ab.c);

            ab.j = sqrt(j2);
            ab.x = ab.j.subtract(n);
            ab.a = ab.d.subtract(ab.x);
            ab.b = ab.c.divide(ab.a);
            ab.t = getT(ab.e, ab.x);

            return ab;
        }

        public BigInteger getOddColumn(BigInteger e, BigInteger negative_f) {
            if (isEven(e)) {
                return negative_f;
            } else {
                return e;
            }
        }

        /**
         * Returns Object[]{BigInteger[] qPrimes, BigInteger q}
         */
        public Object[] getPrimeSeries(BigInteger d) {
            BigInteger q = five;

            BigInteger nextPrime = five;
            ArrayList<BigInteger> primeList = new ArrayList<>();
            primeList.add(q);
            while (lt(q, d)) {
                nextPrime = nextPrime.nextProbablePrime();

                /** End in 01 constraint */
                if (nextPrime.toString(2).endsWith("01")) {
                    q = q.multiply(nextPrime);
                    primeList.add(nextPrime);
                }
            }

            BigInteger[] qPrimes = primeList.toArray(new BigInteger[0]);
            return new Object[]{qPrimes, q};
        }

        public BigInteger getT(BigInteger e, BigInteger x) {
            BigInteger addend = one;

            if (isEven(e)) {
                addend = two;
            }

            return x.add(addend).divide(two);
        }

        public BigInteger getX(BigInteger e, BigInteger t) {
            BigInteger subtrahend = one;

            if (isEven(e)) {
                subtrahend = two;
            }

            return two.multiply(t).subtract(subtrahend);
        }

        public VQCElement mirror(VQCElement el, BigInteger neg_f) {
            BigInteger e = neg_f;
            BigInteger n = el.n.subtract(one);

            if (n.equals(zero)) n = one;

            BigInteger x = el.x.add(one);

            return getElement(e, n, getT(e, x));
        }
    }

    public static class VQCElement {
        public BigInteger a;
        public BigInteger b;
        public BigInteger c;
        public BigInteger d;
        public BigInteger e;
        public BigInteger f;
        public BigInteger i;
        public BigInteger j;
        public BigInteger n;
        public BigInteger x;
        public BigInteger t;

        public VQCElement clone() {
            VQCElement c = new VQCElement();
            c.a = a;
            c.b = b;
            c.c = this.c;
            c.d = d;
            c.e = e;
            c.f = f;
            c.i = i;
            c.j = j;
            c.n = n;
            c.x = x;
            c.t = t;

            return c;
        }

        public String getCoordinates() {
            return "(" + e + ", " + n + ", " + t + ")";
        }

        /**
         * Without the coordinates
         */
        public String toElementString() {
            return "{" + e + ":" + n + ":" + d + ":" + x + ":" + a + ":" + b + "} ";
        }

        public String toString() {
            return toElementString() + getCoordinates();
        }
    }

    static class Lib {
        /** Constants */
        public static BigInteger zero = BigInteger.ZERO;
        public static BigInteger one = BigInteger.ONE;
        public static BigInteger two = BigInteger.valueOf(2);
        public static BigInteger three = BigInteger.valueOf(3);
        public static BigInteger four = BigInteger.valueOf(4);
        public static BigInteger five = BigInteger.valueOf(5);
        public static BigInteger eight = BigInteger.valueOf(8);
        public static BigInteger nine = BigInteger.valueOf(9);
        public static BigInteger sixteen = BigInteger.valueOf(16);
        public static BigInteger twenty = BigInteger.valueOf(20);

        /* Boolean methods */
        public static boolean isEven(BigInteger e) { return (e.and(one)).equals(zero); }
        public static boolean isMultiple(int a, int b) { return a % b == 0; }
        public static boolean isMultiple(BigInteger a, BigInteger b) { return a.mod(b).equals(zero); }
        public static boolean isSquare(BigInteger value) { return sqrt(value).pow(2).equals(value); }

        public static boolean isSqrt(BigInteger n, BigInteger root) {
            BigInteger lowerBound = root.multiply(root);

            /* Bitcode compiler will optimize this statement */
            BigInteger upperBound = root.add(one).multiply(root.add(one));

            return gteq(n, lowerBound) && lt(n, upperBound);
        }

        /* Comparison methods for readability */
        public static boolean gt(BigInteger i, BigInteger i2) { return i.compareTo(i2) > 0; }
        public static boolean gteq(BigInteger i, BigInteger i2) { return i.compareTo(i2) >= 0; }
        public static boolean lt(BigInteger i, BigInteger i2) { return i.compareTo(i2) < 0; }
        public static boolean lteq(BigInteger i, BigInteger i2) { return i.compareTo(i2) <= 0; }

        /** For very large exponents; this probably will never be necessary before the system runs out of RAM. */
        public static BigInteger pow(BigInteger base, BigInteger exponent) {
            BigInteger result = BigInteger.ONE;

            while (exponent.signum() > 0) {
                if (exponent.testBit(0)) {
                    result = result.multiply(base);
                }

                base = base.multiply(base);
                exponent = exponent.shiftRight(1);
            }

            return result;
        }

        /**
         * Efficient Newton square root method
         * @return square root of i
         * define d(n) = sqrt(n)//1
         */
        public static BigInteger sqrt(BigInteger n) {
            if (n.equals(zero)) return zero;

            if (gt(n, zero)) {
                int bitLength = n.bitLength(); //ceil(log(n, 2))
                BigInteger root = one.shiftLeft(bitLength >> 1); //right-shifting by one equals dividing by two

                while (!isSqrt(n, root)) {
                    root = root.add(n.divide(root));
                    root = root.shiftRight(1);
                }

                return root;
            }

            throw new ArithmeticException("Complex result");
        }
    }
}