SHARE
TWEET

VQC

a guest Apr 24th, 2019 115 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package rsa.release;
  2.  
  3. import java.math.BigInteger;
  4. import java.util.*;
  5.  
  6. import static rsa.release.unseeIt.Lib.*;
  7.  
  8. public class unseeIt {
  9.     public static void main(String[] args) throws InterruptedException {
  10.         VQC vqc = new VQC();
  11.         Scanner s = new Scanner(System.in);
  12.  
  13.         outer:
  14.         for (;;) {
  15.             BigInteger c = s.nextBigInteger();
  16.             BigInteger d = sqrt(c);
  17.             BigInteger e = c.subtract(d.multiply(d));
  18.             BigInteger f = two.multiply(d).add(one).subtract(e);
  19.             BigInteger I = c.add(one).divide(two);
  20.             BigInteger i = zero;
  21.  
  22.             /* calculating elements d is between */
  23.             System.out.println("D:");
  24.             VQCElement D  = vqc.getElementBelowRoot(e, one, d);
  25.             BigInteger j_D = D.j;
  26.  
  27.             VQCElement D2 = vqc.getElement(e, one, D.t.add(one));
  28.             BigInteger j_D2 = D2.j;
  29.  
  30.             System.out.println(D);
  31.             System.out.println(D2);
  32.             System.out.println();
  33.  
  34.             System.out.println("D_f:");
  35.             VQCElement D_f  = vqc.getElementBelowRoot(f.negate(), one, d);
  36.             BigInteger j_D_f = D_f.j;
  37.  
  38.             VQCElement D_f2 = vqc.getElement(f.negate(), one, D_f.t.add(one));
  39.             BigInteger j_D_f2 = D_f2.j;
  40.  
  41.             System.out.println(D_f);
  42.             System.out.println(D_f2);
  43.  
  44.             /* calculating offset between e and -f */
  45.             BigInteger d1 = D.d;
  46.             BigInteger d2 = vqc.getElement(f.negate(), one, D2.t).d;
  47.             BigInteger delta = d2.subtract(d1);
  48.  
  49.             BigInteger d3 = D2.d;
  50.             BigInteger d4 = vqc.getElement(f.negate(), one, D2.t.add(one)).d;
  51.             BigInteger delta2 = d4.subtract(d3);
  52.  
  53.             BigInteger offset = delta.subtract(delta2).abs();
  54.             System.out.println("offset = " + offset);
  55.  
  56.             /* tree set for subsequent rows */
  57.             TreeSet<BigInteger> rows = new TreeSet<BigInteger>();
  58.             BigInteger nextRow = one;
  59.  
  60.             long calculations = 0;
  61.             long iterations = 1;
  62.             long increment = 0;
  63.             boolean started = true;
  64.             for (;;) {
  65.                 if (calculations > 10000 || gt(i, I)) {
  66.                     System.out.println("not");
  67.                     System.out.println();
  68.                     continue outer;
  69.                 }
  70.  
  71.                 calculations += 1;
  72.                 i = D.i;
  73.                 if (isCorrectRoot(i, c)) break;
  74.  
  75.                 calculations += 1;
  76.                 i = vqc.getElement(e, one, D.t.add(one)).i;
  77.                 if (isCorrectRoot(i, c)) break;
  78.  
  79.                 calculations += increment;
  80.                 i = D2.i;
  81.                 if (isCorrectRoot(i, c)) break;
  82.  
  83.                 calculations += 1;
  84.                 i = vqc.getElement(e, one, D2.t.add(one)).i;
  85.                 if (isCorrectRoot(i, c)) break;
  86.  
  87.                 calculations += 1;
  88.                 i = D_f.i;
  89.                 if (isCorrectRoot(i, c)) break;
  90.  
  91.                 calculations += increment;
  92.                 i = vqc.getElement(f.negate(), one, D_f.t.add(one)).i;
  93.                 if (isCorrectRoot(i, c)) break;
  94.  
  95.                 calculations += 1;
  96.                 i = D_f2.i;
  97.                 if (isCorrectRoot(i, c)) break;
  98.  
  99.                 calculations += increment;
  100.                 i = vqc.getElement(f.negate(), one, D_f2.t.add(one)).i;
  101.                 if (isCorrectRoot(i, c)) break;
  102.  
  103.                 //because of the loop structure, some calculations are repeated, those are not counted as part of the complexity
  104.                 if (!started) {
  105.                     increment = 1;
  106.                 }
  107.  
  108.                 /* recursive row calculations */
  109.                 VQCElement queryElement = vqc.getElement(e, one, BigInteger.valueOf(iterations));
  110.                 rows.add(queryElement.a);
  111.                 rows.add(queryElement.b);
  112.  
  113.                 VQCElement A = AlgorithmLib.seeIt(queryElement.a);
  114.                 VQCElement B = AlgorithmLib.seeIt(queryElement.b);
  115.                 rows.add(A.a);
  116.                 rows.add(A.b);
  117.                 rows.add(B.a);
  118.                 rows.add(B.b);
  119.  
  120.                 Iterator<BigInteger> iterator = rows.descendingIterator();
  121.                 if (iterator.hasNext()) {
  122.                     nextRow = iterator.next();
  123.                 } else {
  124.                     i = I;
  125.                     break;
  126.                 }
  127.  
  128.                 D = vqc.getElement(e, nextRow, j_D);
  129.                 D2 = vqc.getElement(e, nextRow, j_D2);
  130.                 D_f = vqc.getElement(f.negate(), nextRow.subtract(one), j_D_f);
  131.                 D_f2 = vqc.getElement(f.negate(), nextRow.subtract(one), j_D_f2);
  132.  
  133.                 iterations++;
  134.  
  135.                 /*
  136.                 can also be done backwards
  137.                 D = vqc.getElement(e, one, D.j.negate());
  138.                 D2 = vqc.getElement(e, one, D2.j.negate());
  139.                 D_f = vqc.getElement(e, one, D_f.j.negate());
  140.                 D_f2 = vqc.getElement(e, one, D_f2.j.negate());
  141.                 */
  142.             }
  143.  
  144.             System.out.println("calculations = " + calculations);
  145.             System.out.println("nextRow = " + nextRow);
  146.             System.out.println("D = " + D);
  147.             System.out.println("D_f = " + D_f);
  148.             BigInteger i2 = i.multiply(i);
  149.             BigInteger j2 = i2.subtract(c);
  150.             BigInteger j = sqrt(j2);
  151.             BigInteger b = i.add(j);
  152.             BigInteger a = i.subtract(j);
  153.             System.out.println("c = " + a + " * " + b);
  154.             System.out.println();
  155.         }
  156.     }
  157.  
  158.     private static boolean isCorrectRoot(BigInteger i, BigInteger c) {
  159.         BigInteger i2 = i.multiply(i);
  160.         BigInteger j2 = i2.subtract(c);
  161.  
  162.         if (!lt(j2, one)) {
  163.             if (isSquare(j2)) {
  164.                 System.out.println("match");
  165.                 return true;
  166.             } else {
  167.                 return false;
  168.             }
  169.         } else {
  170.             return false;
  171.         }
  172.     }
  173.  
  174.     private static class AlgorithmLib {
  175.         private static VQC vqc = new VQC();
  176.  
  177.         public static VQCElement seeIt(BigInteger c) {
  178.             BigInteger d = sqrt(c);
  179.             BigInteger e = c.subtract(d.multiply(d));
  180.             BigInteger f = two.multiply(d).add(one).subtract(e);
  181.             BigInteger i = zero;
  182.             BigInteger I = c.add(one).divide(two);
  183.  
  184.             VQCElement D = vqc.getElementBelowRoot(e, one, d);
  185.             VQCElement D2 = vqc.getElement(e, one, D.t.add(one));
  186.  
  187.             VQCElement D_f = vqc.getElementBelowRoot(f.negate(), one, d);
  188.             VQCElement D_f2 = vqc.getElement(f.negate(), one, D_f.t.add(one));
  189.  
  190.             TreeSet<BigInteger> rows = new TreeSet<BigInteger>();
  191.  
  192.             long iterations = 0;
  193.             for (; ; ) {
  194.                 if (gt(i, I)) {
  195.                     i = I;
  196.                     break;
  197.                 }
  198.  
  199.                 i = D.i;
  200.                 if (seeItImpl(i, c)) break;
  201.  
  202.                 i = vqc.getElement(e, D.n, D.t.add(one)).i;
  203.                 if (seeItImpl(i, c)) break;
  204.  
  205.                 i = D2.i;
  206.                 if (seeItImpl(i, c)) break;
  207.  
  208.                 i = vqc.getElement(e, D2.n, D2.t.add(one)).i;
  209.                 if (seeItImpl(i, c)) break;
  210.  
  211.                 i = D_f.i;
  212.                 if (seeItImpl(i, c)) break;
  213.  
  214.                 i = vqc.getElement(f.negate(), D_f.n, D_f.t.add(one)).i;
  215.                 if (seeItImpl(i, c)) break;
  216.  
  217.                 i = D_f2.i;
  218.                 if (seeItImpl(i, c)) break;
  219.  
  220.                 i = vqc.getElement(f.negate(), D_f2.n, D_f2.t.add(one)).i;
  221.                 if (seeItImpl(i, c)) break;
  222.  
  223.                 iterations++;
  224.  
  225.                 VQCElement queryElement = vqc.getElement(e, one, BigInteger.valueOf(iterations));
  226.                 rows.add(queryElement.a);
  227.                 rows.add(queryElement.b);
  228.  
  229.                 if (queryElement.a.equals(zero)) {
  230.                     i = I;
  231.                     break;
  232.                 } else if (queryElement.a.equals(one)) {
  233.                     i = I;
  234.                     break;
  235.                 }
  236.  
  237.                 if (!queryElement.a.mod(four).equals(two)) {
  238.                     VQCElement A = AlgorithmLib.seeIt(queryElement.a);
  239.                     rows.add(A.a);
  240.                     rows.add(A.b);
  241.                 }
  242.  
  243.                 if (!queryElement.b.mod(four).equals(two)) {
  244.                     VQCElement B = AlgorithmLib.seeIt(queryElement.b);
  245.                     rows.add(B.a);
  246.                     rows.add(B.b);
  247.                 }
  248.  
  249.                 BigInteger nextRow;
  250.                 Iterator<BigInteger> iterator = rows.iterator();
  251.                 if (iterator.hasNext()) {
  252.                     nextRow = iterator.next();
  253.                 } else {
  254.                     i = I;
  255.                     break;
  256.                 }
  257.  
  258.                 D = vqc.getElement(e, one, D.j);
  259.                 D2 = vqc.getElement(e, one, D2.j);
  260.                 D_f = vqc.getElement(e, one, D_f.j);
  261.                 D_f2 = vqc.getElement(e, one, D_f2.j);
  262.             }
  263.  
  264.             BigInteger n = i.subtract(d);
  265.             BigInteger x = sqrt(i.multiply(i).subtract(c)).subtract(d);
  266.             BigInteger t = vqc.getT(e, x);
  267.  
  268.             return vqc.getElement(e, n, t);
  269.         }
  270.  
  271.         private static boolean seeItImpl(BigInteger i, BigInteger c) {
  272.             BigInteger i2 = i.multiply(i);
  273.             BigInteger j2 = i2.subtract(c);
  274.  
  275.             if (!lt(j2, one)) {
  276.                 return isSquare(j2);
  277.             } else {
  278.                 return false;
  279.             }
  280.         }
  281.  
  282.         public static VQCElement iterateCell(BigInteger e, BigInteger n, BigInteger t, BigInteger c, BigInteger increment) {
  283.             VQC vqc = new VQC();
  284.  
  285.             long iterations = 0;
  286.             for (; ; ) {
  287.                 iterations++;
  288.  
  289.                 t = t.add(increment);
  290.                 VQCElement test = vqc.getElement(e, n, t);
  291.  
  292.                 BigInteger a = test.a.gcd(c);
  293.  
  294.                 if (!a.equals(one)) {
  295.                     System.out.println("iterations = " + iterations);
  296.  
  297.                     BigInteger d = sqrt(c);
  298.                     BigInteger x = d.subtract(a);
  299.  
  300.                     return test;
  301.                     //return vqc.getElement(e, n, vqc.getT(e, x));
  302.                 }
  303.             }
  304.         }
  305.     }
  306.  
  307.     private static class VQC {
  308.         public VQC() {
  309.         }
  310.  
  311.         public VQCElement getElement(BigInteger e, BigInteger n, BigInteger t) {
  312.             VQCElement v = new VQCElement();
  313.             v.e = e;
  314.             v.n = n;
  315.             v.t = t;
  316.  
  317.             if (e.equals(zero) || n.equals(zero)) {
  318.                 v.x = zero;
  319.                 v.a = v.t;
  320.                 v.d = v.a;
  321.                 v.b = v.a;
  322.                 v.c = t.multiply(t);
  323.                 v.f = two.multiply(v.d).add(one).subtract(v.e);
  324.                 v.i = v.d;
  325.                 v.j = zero;
  326.  
  327.                 return v;
  328.             }
  329.  
  330.             v.x = getX(e, t);
  331.  
  332.             /* define a(x) = ((x^2 + e) / (2*n)) // 1 */
  333.             v.a = (v.x.pow(2)).add(e).divide(two.multiply(v.n));
  334.  
  335.             /* define define d(x) = ((x^2 + e) / (2*n) + x) // 1 */
  336.             v.d = v.a.add(v.x);
  337.             v.f = two.multiply(v.d).add(one).subtract(v.e);
  338.             v.b = v.a.add(two.multiply(v.x)).add(two.multiply(v.n));
  339.             v.c = v.a.multiply(v.b);
  340.             v.i = v.d.add(v.n);
  341.             v.j = v.x.add(v.n);
  342.  
  343.             return v;
  344.         }
  345.  
  346.         /* Get closest element with d value below input d in (e, n)
  347.          * The element above it can be calculated to give the two elements whose d values d is between */
  348.         public VQCElement getElementBelowRoot(BigInteger e, BigInteger n, BigInteger d) {
  349.             BigInteger c = d.multiply(d).add(e);
  350.             BigInteger xpn = sqrt(d.add(n).pow(2).subtract(c));
  351.             BigInteger x = xpn.subtract(n);
  352.             boolean eIsEven = isEven(e);
  353.             boolean xIsEven = isEven(x);
  354.  
  355.             if (!(eIsEven == xIsEven)) {
  356.                 x = x.subtract(one);
  357.             }
  358.  
  359.             return getElement(e, n, getT(e, x));
  360.         }
  361.  
  362.         public VQCElement getEntryElement(BigInteger c) {
  363.             BigInteger d = sqrt(c);
  364.             BigInteger e = c.subtract(d.multiply(d));
  365.             BigInteger N = c.add(one).divide(two).subtract(d);
  366.             BigInteger X = d.subtract(one);
  367.             BigInteger T = getT(e, X);
  368.  
  369.             return getElement(e, N, T);
  370.         }
  371.  
  372.         public BigInteger getEvenColumn(BigInteger e, BigInteger negative_f) {
  373.             if (!isEven(e)) {
  374.                 return negative_f;
  375.             } else {
  376.                 return e;
  377.             }
  378.         }
  379.  
  380.         public VQCElement getFactorizationElement(VQCElement c1, BigInteger n) {
  381.             VQCElement ab = c1.clone();
  382.  
  383.             ab.n = n;
  384.             ab.i = ab.d.add(ab.n);
  385.  
  386.             BigInteger i2 = ab.i.pow(2);
  387.             BigInteger j2 = i2.subtract(ab.c);
  388.  
  389.             ab.j = sqrt(j2);
  390.             ab.x = ab.j.subtract(n);
  391.             ab.a = ab.d.subtract(ab.x);
  392.             ab.b = ab.c.divide(ab.a);
  393.             ab.t = getT(ab.e, ab.x);
  394.  
  395.             return ab;
  396.         }
  397.  
  398.         public BigInteger getOddColumn(BigInteger e, BigInteger negative_f) {
  399.             if (isEven(e)) {
  400.                 return negative_f;
  401.             } else {
  402.                 return e;
  403.             }
  404.         }
  405.  
  406.         /**
  407.          * Returns Object[]{BigInteger[] qPrimes, BigInteger q}
  408.          */
  409.         public Object[] getPrimeSeries(BigInteger d) {
  410.             BigInteger q = five;
  411.  
  412.             BigInteger nextPrime = five;
  413.             ArrayList<BigInteger> primeList = new ArrayList<>();
  414.             primeList.add(q);
  415.             while (lt(q, d)) {
  416.                 nextPrime = nextPrime.nextProbablePrime();
  417.  
  418.                 /** End in 01 constraint */
  419.                 if (nextPrime.toString(2).endsWith("01")) {
  420.                     q = q.multiply(nextPrime);
  421.                     primeList.add(nextPrime);
  422.                 }
  423.             }
  424.  
  425.             BigInteger[] qPrimes = primeList.toArray(new BigInteger[0]);
  426.             return new Object[]{qPrimes, q};
  427.         }
  428.  
  429.         public BigInteger getT(BigInteger e, BigInteger x) {
  430.             BigInteger addend = one;
  431.  
  432.             if (isEven(e)) {
  433.                 addend = two;
  434.             }
  435.  
  436.             return x.add(addend).divide(two);
  437.         }
  438.  
  439.         public BigInteger getX(BigInteger e, BigInteger t) {
  440.             BigInteger subtrahend = one;
  441.  
  442.             if (isEven(e)) {
  443.                 subtrahend = two;
  444.             }
  445.  
  446.             return two.multiply(t).subtract(subtrahend);
  447.         }
  448.  
  449.         public VQCElement mirror(VQCElement el, BigInteger neg_f) {
  450.             BigInteger e = neg_f;
  451.             BigInteger n = el.n.subtract(one);
  452.  
  453.             if (n.equals(zero)) n = one;
  454.  
  455.             BigInteger x = el.x.add(one);
  456.  
  457.             return getElement(e, n, getT(e, x));
  458.         }
  459.     }
  460.  
  461.     public static class VQCElement {
  462.         public BigInteger a;
  463.         public BigInteger b;
  464.         public BigInteger c;
  465.         public BigInteger d;
  466.         public BigInteger e;
  467.         public BigInteger f;
  468.         public BigInteger i;
  469.         public BigInteger j;
  470.         public BigInteger n;
  471.         public BigInteger x;
  472.         public BigInteger t;
  473.  
  474.         public VQCElement clone() {
  475.             VQCElement c = new VQCElement();
  476.             c.a = a;
  477.             c.b = b;
  478.             c.c = this.c;
  479.             c.d = d;
  480.             c.e = e;
  481.             c.f = f;
  482.             c.i = i;
  483.             c.j = j;
  484.             c.n = n;
  485.             c.x = x;
  486.             c.t = t;
  487.  
  488.             return c;
  489.         }
  490.  
  491.         public String getCoordinates() {
  492.             return "(" + e + ", " + n + ", " + t + ")";
  493.         }
  494.  
  495.         /**
  496.          * Without the coordinates
  497.          */
  498.         public String toElementString() {
  499.             return "{" + e + ":" + n + ":" + d + ":" + x + ":" + a + ":" + b + "} ";
  500.         }
  501.  
  502.         public String toString() {
  503.             return toElementString() + getCoordinates();
  504.         }
  505.     }
  506.  
  507.     static class Lib {
  508.         /** Constants */
  509.         public static BigInteger zero = BigInteger.ZERO;
  510.         public static BigInteger one = BigInteger.ONE;
  511.         public static BigInteger two = BigInteger.valueOf(2);
  512.         public static BigInteger three = BigInteger.valueOf(3);
  513.         public static BigInteger four = BigInteger.valueOf(4);
  514.         public static BigInteger five = BigInteger.valueOf(5);
  515.         public static BigInteger eight = BigInteger.valueOf(8);
  516.         public static BigInteger nine = BigInteger.valueOf(9);
  517.         public static BigInteger sixteen = BigInteger.valueOf(16);
  518.         public static BigInteger twenty = BigInteger.valueOf(20);
  519.  
  520.         /* Boolean methods */
  521.         public static boolean isEven(BigInteger e) { return (e.and(one)).equals(zero); }
  522.         public static boolean isMultiple(int a, int b) { return a % b == 0; }
  523.         public static boolean isMultiple(BigInteger a, BigInteger b) { return a.mod(b).equals(zero); }
  524.         public static boolean isSquare(BigInteger value) { return sqrt(value).pow(2).equals(value); }
  525.  
  526.         public static boolean isSqrt(BigInteger n, BigInteger root) {
  527.             BigInteger lowerBound = root.multiply(root);
  528.  
  529.             /* Bitcode compiler will optimize this statement */
  530.             BigInteger upperBound = root.add(one).multiply(root.add(one));
  531.  
  532.             return gteq(n, lowerBound) && lt(n, upperBound);
  533.         }
  534.  
  535.         /* Comparison methods for readability */
  536.         public static boolean gt(BigInteger i, BigInteger i2) { return i.compareTo(i2) > 0; }
  537.         public static boolean gteq(BigInteger i, BigInteger i2) { return i.compareTo(i2) >= 0; }
  538.         public static boolean lt(BigInteger i, BigInteger i2) { return i.compareTo(i2) < 0; }
  539.         public static boolean lteq(BigInteger i, BigInteger i2) { return i.compareTo(i2) <= 0; }
  540.  
  541.         /** For very large exponents; this probably will never be necessary before the system runs out of RAM. */
  542.         public static BigInteger pow(BigInteger base, BigInteger exponent) {
  543.             BigInteger result = BigInteger.ONE;
  544.  
  545.             while (exponent.signum() > 0) {
  546.                 if (exponent.testBit(0)) {
  547.                     result = result.multiply(base);
  548.                 }
  549.  
  550.                 base = base.multiply(base);
  551.                 exponent = exponent.shiftRight(1);
  552.             }
  553.  
  554.             return result;
  555.         }
  556.  
  557.         /**
  558.          * Efficient Newton square root method
  559.          * @return square root of i
  560.          * define d(n) = sqrt(n)//1
  561.          */
  562.         public static BigInteger sqrt(BigInteger n) {
  563.             if (n.equals(zero)) return zero;
  564.  
  565.             if (gt(n, zero)) {
  566.                 int bitLength = n.bitLength(); //ceil(log(n, 2))
  567.                 BigInteger root = one.shiftLeft(bitLength >> 1); //right-shifting by one equals dividing by two
  568.  
  569.                 while (!isSqrt(n, root)) {
  570.                     root = root.add(n.divide(root));
  571.                     root = root.shiftRight(1);
  572.                 }
  573.  
  574.                 return root;
  575.             }
  576.  
  577.             throw new ArithmeticException("Complex result");
  578.         }
  579.     }
  580. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top