Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement