/vqc/ - Virtual Quantum Computer

Java code that will be useful later:

public static int legendreSymbol(BigInteger a, BigInteger p) {
        BigInteger pm1 = p.subtract(BigInteger.ONE);
        BigInteger ls;

        ls = a.modPow(pm1.divide(BigInteger.valueOf(2)), p);

        if (ls.equals(pm1)) {
            return -1;
        } else {
            return ls.intValueExact();
        }
    }

    public static BigInteger modSqrt(BigInteger a, BigInteger p) {
        a = a.mod(p);

        if (legendreSymbol(a, p) != 1) {
            return zero;
        } else if (a.equals(zero)) {
            return zero;
        } else if (p.equals(two)) {
            return p;
        } else if (p.mod(four).equals(three)) {
            return a.modPow(p.add(one).divide(four), p);
        }

        BigInteger s = p.subtract(one);
        int e = 0;

        while (s.mod(two).equals(zero)) {
            s = s.divide(two);
            e += 1;
        }

        BigInteger n = two;
        while (legendreSymbol(n, p) != -1) {
            n = n.add(one);
        }

        BigInteger x = a.modPow(s.add(one).divide(two), p);
        BigInteger b = a.modPow(s, p);
        BigInteger g = n.modPow(s, p);
        int r = e;

        BigInteger gs, t;
        int m;
        while (true) {
            t = b;
            m = 0;

            for (; m < r; m++) {
                if (t.equals(one)) {
                    break;
                }

                t = t.modPow(two, p);
            }

            if (m == 0) {
                return x;
            }

            gs = g.modPow(two.pow(r - m - 1), p);
            g = gs.pow(2).mod(p);
            x = x.multiply(gs).mod(p);
            b = b.multiply(g).mod(p);
            r = m;
        }
    }

nistp256 {

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951

#G = 115792089210356248762697446949407573529996955224135760342422259061068512044369

a = -3

b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286

Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109

}

secp256k1 (Bitcoin Curve) {

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

#G = 115792089237316195423570985008687907852837564279074904382605163141518161494337

a = 0

b = 7

Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240

Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424

}