<commit_before>package org.bouncycastle.math.ec.tools;

import java.math.BigInteger;
import java.security.SecureRandom;

import org.bouncycastle.asn1.x9.ECNamedCurveTable;
import org.bouncycastle.asn1.x9.X9ECParameters;
import org.bouncycastle.math.ec.ECAlgorithms;
import org.bouncycastle.math.ec.ECConstants;
import org.bouncycastle.math.ec.ECCurve;
import org.bouncycastle.math.ec.ECFieldElement;
import org.bouncycastle.math.ec.ECPoint;
import org.bouncycastle.util.BigIntegers;

public class DiscoverEndomorphisms
{
    private static final int radix = 16;

    public static void main(String[] args)
    {
        if (args.length < 1)
        {
            System.err.println("Expected a list of curve names as arguments");
            return;
        }

        for (int i = 0; i < args.length; ++i)
        {
            discoverEndomorphism(args[i]);
        }
    }

    private static void discoverEndomorphism(String curveName)
    {
        X9ECParameters x9 = ECNamedCurveTable.getByName(curveName);
        if (x9 == null)
        {
            System.err.println("Unknown curve: " + curveName);
            return;
        }

        ECCurve c = x9.getCurve();
        if (ECAlgorithms.isFpCurve(c))
        {
            BigInteger characteristic = c.getField().getCharacteristic();

            if (c.getA().isZero() && characteristic.mod(ECConstants.THREE).equals(ECConstants.ONE))
            {
                System.out.println("Curve '" + curveName + "' has a 'GLV Type B' endomorphism with these parameters: ");
                printGLVTypeBParameters(x9);
            }
            else
            {
                System.out.println("No endomorphisms discovered for: " + curveName);
            }
        }
    }

    private static void printGLVTypeBParameters(X9ECParameters x9)
    {
        BigInteger n = x9.getN();
        BigInteger[] v1 = null;
        BigInteger[] v2 = null;

        // x^2 + x + 1 = 0 mod n
        BigInteger lambda = solveQuadraticEquation(n, ECConstants.ONE, ECConstants.ONE);

        BigInteger[] rt = extEuclidGLV(n, lambda);
        v1 = new BigInteger[]{ rt[2], rt[3].negate() };
        v2 = chooseShortest(new BigInteger[]{ rt[0], rt[1].negate() }, new BigInteger[]{ rt[4], rt[5].negate() });

        /*
         * If elements of v2 are not bounded by sqrt(n), then if r1/t1 are relatively prime there
         * _may_ yet be a GLV generator, so search for it. See
         * "Integer Decomposition for Fast Scalar Multiplication on Elliptic Curves", <NAME>, <NAME>
         * (SAC 2002)
         */
        if (!isVectorBoundedBySqrt(v2, n) && areRelativelyPrime(v1[0], v1[1]))
        {
            BigInteger r = v1[0], t = v1[1], s = r.add(t.multiply(lambda)).divide(n);

            BigInteger[] vw = extEuclidBezout(new BigInteger[]{ s.abs(), t.abs() });
            BigInteger v = vw[0], w = vw[1];

            if (s.signum() < 0)
            {
                v = v.negate();
            }
            if (t.signum() > 0)
            {
                w = w.negate();
            }

            BigInteger check = s.multiply(v).subtract(t.multiply(w));
            if (!check.equals(ECConstants.ONE))
            {
                throw new IllegalStateException();
            }

            BigInteger x = w.multiply(n).subtract(v.multiply(lambda));

            BigInteger base1 = v.negate();
            BigInteger base2 = x.negate();

            /*
             * We calculate the range(s) conservatively large to avoid messy rounding issues, so
             * there may be spurious candidate generators, but we won't miss any.
             */
            BigInteger sqrtN = isqrt(n.subtract(ECConstants.ONE)).add(ECConstants.ONE);

            BigInteger[] I1 = calculateRange(base1, sqrtN, t);
            BigInteger[] I2 = calculateRange(base2, sqrtN, r);

            BigInteger[] range = intersect(I1, I2);
            if (range != null)
            {
                for (BigInteger alpha = range[0]; alpha.compareTo(range[1]) <= 0; alpha = alpha.add(ECConstants.ONE))
                {
                    BigInteger[] candidate = new BigInteger[]{ x.add(alpha.multiply(r)), v.add(alpha.multiply(t)) };
                    if (isShorter(candidate, v2))
                    {
                        v2 = candidate;
                    }
                }
            }
        }

        /*
         * 'Beta' is a field element of order 3. There are only two such values besides 1; determine which of them
         * corresponds to our choice for 'Lambda'.
         */
        ECFieldElement beta;
        {
            ECPoint G = x9.getG().normalize();
            ECPoint mapG = G.multiply(lambda).normalize();
            if (!G.getYCoord().equals(mapG.getYCoord()))
            {
                throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly");
            }
    
            BigInteger q = x9.getCurve().getField().getCharacteristic();
            BigInteger e = q.divide(ECConstants.THREE);

            SecureRandom random = new SecureRandom();
            BigInteger b;
            do
            {
                BigInteger r = BigIntegers.createRandomInRange(ECConstants.TWO, q.subtract(ECConstants.TWO), random);
                b = r.modPow(e, q);
            }
            while (b.equals(ECConstants.ONE));

            beta = x9.getCurve().fromBigInteger(ECConstants.TWO.modPow(e, q));

            if (!G.getXCoord().multiply(beta).equals(mapG.getXCoord()))
            {
                beta = beta.square();
                if (!G.getXCoord().multiply(beta).equals(mapG.getXCoord()))
                {
                    throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly");
                }
            }
        }

        /*
         * These parameters are used to avoid division when decomposing the scalar in a GLV point multiplication
         */
        BigInteger d = (v1[0].multiply(v2[1])).subtract(v1[1].multiply(v2[0]));

        int bits = n.bitLength() + 2;
        BigInteger g1 = roundQuotient(v2[1].shiftLeft(bits), d);
        BigInteger g2 = roundQuotient(v1[1].shiftLeft(bits), d).negate();

        printProperty("Beta", beta.toBigInteger().toString(radix));
        printProperty("Lambda", lambda.toString(radix));
        printProperty("v1", "{ " + v1[0].toString(radix) + ", " + v1[1].toString(radix) + " }");
        printProperty("v2", "{ " + v2[0].toString(radix) + ", " + v2[1].toString(radix) + " }");
        printProperty("(OPT) bits", bits);
        printProperty("(OPT) g1", g1.toString(radix));
        printProperty("(OPT) g2", g2.toString(radix));<commit_msg>Minor change to order of output<commit_after>package org.bouncycastle.math.ec.tools;

import java.math.BigInteger;
import java.security.SecureRandom;

import org.bouncycastle.asn1.x9.ECNamedCurveTable;
import org.bouncycastle.asn1.x9.X9ECParameters;
import org.bouncycastle.math.ec.ECAlgorithms;
import org.bouncycastle.math.ec.ECConstants;
import org.bouncycastle.math.ec.ECCurve;
import org.bouncycastle.math.ec.ECFieldElement;
import org.bouncycastle.math.ec.ECPoint;
import org.bouncycastle.util.BigIntegers;

public class DiscoverEndomorphisms
{
    private static final int radix = 16;

    public static void main(String[] args)
    {
        if (args.length < 1)
        {
            System.err.println("Expected a list of curve names as arguments");
            return;
        }

        for (int i = 0; i < args.length; ++i)
        {
            discoverEndomorphism(args[i]);
        }
    }

    private static void discoverEndomorphism(String curveName)
    {
        X9ECParameters x9 = ECNamedCurveTable.getByName(curveName);
        if (x9 == null)
        {
            System.err.println("Unknown curve: " + curveName);
            return;
        }

        ECCurve c = x9.getCurve();
        if (ECAlgorithms.isFpCurve(c))
        {
            BigInteger characteristic = c.getField().getCharacteristic();

            if (c.getA().isZero() && characteristic.mod(ECConstants.THREE).equals(ECConstants.ONE))
            {
                System.out.println("Curve '" + curveName + "' has a 'GLV Type B' endomorphism with these parameters: ");
                printGLVTypeBParameters(x9);
            }
            else
            {
                System.out.println("No endomorphisms discovered for: " + curveName);
            }
        }
    }

    private static void printGLVTypeBParameters(X9ECParameters x9)
    {
        BigInteger n = x9.getN();
        BigInteger[] v1 = null;
        BigInteger[] v2 = null;

        // x^2 + x + 1 = 0 mod n
        BigInteger lambda = solveQuadraticEquation(n, ECConstants.ONE, ECConstants.ONE);

        BigInteger[] rt = extEuclidGLV(n, lambda);
        v1 = new BigInteger[]{ rt[2], rt[3].negate() };
        v2 = chooseShortest(new BigInteger[]{ rt[0], rt[1].negate() }, new BigInteger[]{ rt[4], rt[5].negate() });

        /*
         * If elements of v2 are not bounded by sqrt(n), then if r1/t1 are relatively prime there
         * _may_ yet be a GLV generator, so search for it. See
         * "Integer Decomposition for Fast Scalar Multiplication on Elliptic Curves", <NAME>, <NAME>
         * (SAC 2002)
         */
        if (!isVectorBoundedBySqrt(v2, n) && areRelativelyPrime(v1[0], v1[1]))
        {
            BigInteger r = v1[0], t = v1[1], s = r.add(t.multiply(lambda)).divide(n);

            BigInteger[] vw = extEuclidBezout(new BigInteger[]{ s.abs(), t.abs() });
            BigInteger v = vw[0], w = vw[1];

            if (s.signum() < 0)
            {
                v = v.negate();
            }
            if (t.signum() > 0)
            {
                w = w.negate();
            }

            BigInteger check = s.multiply(v).subtract(t.multiply(w));
            if (!check.equals(ECConstants.ONE))
            {
                throw new IllegalStateException();
            }

            BigInteger x = w.multiply(n).subtract(v.multiply(lambda));

            BigInteger base1 = v.negate();
            BigInteger base2 = x.negate();

            /*
             * We calculate the range(s) conservatively large to avoid messy rounding issues, so
             * there may be spurious candidate generators, but we won't miss any.
             */
            BigInteger sqrtN = isqrt(n.subtract(ECConstants.ONE)).add(ECConstants.ONE);

            BigInteger[] I1 = calculateRange(base1, sqrtN, t);
            BigInteger[] I2 = calculateRange(base2, sqrtN, r);

            BigInteger[] range = intersect(I1, I2);
            if (range != null)
            {
                for (BigInteger alpha = range[0]; alpha.compareTo(range[1]) <= 0; alpha = alpha.add(ECConstants.ONE))
                {
                    BigInteger[] candidate = new BigInteger[]{ x.add(alpha.multiply(r)), v.add(alpha.multiply(t)) };
                    if (isShorter(candidate, v2))
                    {
                        v2 = candidate;
                    }
                }
            }
        }

        /*
         * 'Beta' is a field element of order 3. There are only two such values besides 1; determine which of them
         * corresponds to our choice for 'Lambda'.
         */
        ECFieldElement beta;
        {
            ECPoint G = x9.getG().normalize();
            ECPoint mapG = G.multiply(lambda).normalize();
            if (!G.getYCoord().equals(mapG.getYCoord()))
            {
                throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly");
            }
    
            BigInteger q = x9.getCurve().getField().getCharacteristic();
            BigInteger e = q.divide(ECConstants.THREE);

            SecureRandom random = new SecureRandom();
            BigInteger b;
            do
            {
                BigInteger r = BigIntegers.createRandomInRange(ECConstants.TWO, q.subtract(ECConstants.TWO), random);
                b = r.modPow(e, q);
            }
            while (b.equals(ECConstants.ONE));

            beta = x9.getCurve().fromBigInteger(ECConstants.TWO.modPow(e, q));

            if (!G.getXCoord().multiply(beta).equals(mapG.getXCoord()))
            {
                beta = beta.square();
                if (!G.getXCoord().multiply(beta).equals(mapG.getXCoord()))
                {
                    throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly");
                }
            }
        }

        /*
         * These parameters are used to avoid division when decomposing the scalar in a GLV point multiplication
         */
        BigInteger d = (v1[0].multiply(v2[1])).subtract(v1[1].multiply(v2[0]));

        int bits = n.bitLength() + 2;
        BigInteger g1 = roundQuotient(v2[1].shiftLeft(bits), d);
        BigInteger g2 = roundQuotient(v1[1].shiftLeft(bits), d).negate();

        printProperty("Beta", beta.toBigInteger().toString(radix));
        printProperty("Lambda", lambda.toString(radix));
        printProperty("v1", "{ " + v1[0].toString(radix) + ", " + v1[1].toString(radix) + " }");
        printProperty("v2", "{ " + v2[0].toString(radix) + ", " + v2[1].toString(radix) + " }");
        printProperty("(OPT) g1", g1.toString(radix));
        printProperty("(OPT) g2", g2.toString(radix));
        printProperty("(OPT) bits", bits);
{'fraction_non_alphanumeric': 0.12649342891278376, 'fraction_numerical': 0.01448626045400239, 'mean_word_length': 1.9178649237472767, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1091495', 'n_tokens_mistral': 4109, 'n_tokens_neox': 3932, 'n_words': 870}