// 
// Decompiled by Procyon v0.6.0
// 

package org.bouncycastle.math.ec.tools;

import org.bouncycastle.util.BigIntegers;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;
import java.util.Enumeration;
import org.bouncycastle.math.ec.ECPoint;
import org.bouncycastle.math.ec.ECFieldElement;
import java.math.BigInteger;
import org.bouncycastle.math.ec.ECCurve;
import org.bouncycastle.math.ec.ECConstants;
import org.bouncycastle.math.ec.ECAlgorithms;
import org.bouncycastle.asn1.x9.X9ECParameters;
import java.util.Iterator;
import org.bouncycastle.crypto.ec.CustomNamedCurves;
import java.util.Collection;
import java.util.TreeSet;
import org.bouncycastle.asn1.x9.ECNamedCurveTable;

public class DiscoverEndomorphisms
{
    private static final int radix = 16;
    
    public static void main(final String[] array) {
        if (array.length > 0) {
            for (int i = 0; i < array.length; ++i) {
                discoverEndomorphisms(array[i]);
            }
        }
        else {
            final TreeSet set = new TreeSet(enumToList(ECNamedCurveTable.getNames()));
            set.addAll(enumToList(CustomNamedCurves.getNames()));
            final Iterator iterator = set.iterator();
            while (iterator.hasNext()) {
                discoverEndomorphisms((String)iterator.next());
            }
        }
    }
    
    public static void discoverEndomorphisms(final X9ECParameters x9ECParameters) {
        if (x9ECParameters == null) {
            throw new NullPointerException("x9");
        }
        discoverEndomorphisms(x9ECParameters, "<UNKNOWN>");
    }
    
    private static void discoverEndomorphisms(final String str) {
        X9ECParameters x9ECParameters = CustomNamedCurves.getByName(str);
        if (x9ECParameters == null) {
            x9ECParameters = ECNamedCurveTable.getByName(str);
            if (x9ECParameters == null) {
                System.err.println("Unknown curve: " + str);
                return;
            }
        }
        discoverEndomorphisms(x9ECParameters, str);
    }
    
    private static void discoverEndomorphisms(final X9ECParameters x9ECParameters, final String s) {
        final ECCurve curve = x9ECParameters.getCurve();
        if (ECAlgorithms.isFpCurve(curve)) {
            final BigInteger characteristic = curve.getField().getCharacteristic();
            if (curve.getB().isZero() && characteristic.mod(ECConstants.FOUR).equals(ECConstants.ONE)) {
                System.out.println("Curve '" + s + "' has a 'GLV Type A' endomorphism with these parameters:");
                printGLVTypeAParameters(x9ECParameters);
            }
            if (curve.getA().isZero() && characteristic.mod(ECConstants.THREE).equals(ECConstants.ONE)) {
                System.out.println("Curve '" + s + "' has a 'GLV Type B' endomorphism with these parameters:");
                printGLVTypeBParameters(x9ECParameters);
            }
        }
    }
    
    private static void printGLVTypeAParameters(final X9ECParameters x9ECParameters) {
        final BigInteger[] solveQuadraticEquation = solveQuadraticEquation(x9ECParameters.getN(), ECConstants.ONE, ECConstants.ZERO, ECConstants.ONE);
        final ECFieldElement[] nonTrivialOrder4FieldElements = findNonTrivialOrder4FieldElements(x9ECParameters.getCurve());
        printGLVTypeAParameters(x9ECParameters, solveQuadraticEquation[0], nonTrivialOrder4FieldElements);
        System.out.println("OR");
        printGLVTypeAParameters(x9ECParameters, solveQuadraticEquation[1], nonTrivialOrder4FieldElements);
    }
    
    private static void printGLVTypeAParameters(final X9ECParameters x9ECParameters, final BigInteger bigInteger, final ECFieldElement[] array) {
        final ECPoint normalize = x9ECParameters.getG().normalize();
        final ECPoint normalize2 = normalize.multiply(bigInteger).normalize();
        if (!normalize.getXCoord().negate().equals(normalize2.getXCoord())) {
            throw new IllegalStateException("Derivation of GLV Type A parameters failed unexpectedly");
        }
        ECFieldElement ecFieldElement = array[0];
        if (!normalize.getYCoord().multiply(ecFieldElement).equals(normalize2.getYCoord())) {
            ecFieldElement = array[1];
            if (!normalize.getYCoord().multiply(ecFieldElement).equals(normalize2.getYCoord())) {
                throw new IllegalStateException("Derivation of GLV Type A parameters failed unexpectedly");
            }
        }
        printProperty("Point map", "lambda * (x, y) = (-x, i * y)");
        printProperty("i", ecFieldElement.toBigInteger().toString(16));
        printProperty("lambda", bigInteger.toString(16));
        printScalarDecompositionParameters(x9ECParameters.getN(), bigInteger);
    }
    
    private static void printGLVTypeBParameters(final X9ECParameters x9ECParameters) {
        final BigInteger[] solveQuadraticEquation = solveQuadraticEquation(x9ECParameters.getN(), ECConstants.ONE, ECConstants.ONE, ECConstants.ONE);
        final ECFieldElement[] nonTrivialOrder3FieldElements = findNonTrivialOrder3FieldElements(x9ECParameters.getCurve());
        printGLVTypeBParameters(x9ECParameters, solveQuadraticEquation[0], nonTrivialOrder3FieldElements);
        System.out.println("OR");
        printGLVTypeBParameters(x9ECParameters, solveQuadraticEquation[1], nonTrivialOrder3FieldElements);
    }
    
    private static void printGLVTypeBParameters(final X9ECParameters x9ECParameters, final BigInteger bigInteger, final ECFieldElement[] array) {
        final ECPoint normalize = x9ECParameters.getG().normalize();
        final ECPoint normalize2 = normalize.multiply(bigInteger).normalize();
        if (!normalize.getYCoord().equals(normalize2.getYCoord())) {
            throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly");
        }
        ECFieldElement ecFieldElement = array[0];
        if (!normalize.getXCoord().multiply(ecFieldElement).equals(normalize2.getXCoord())) {
            ecFieldElement = array[1];
            if (!normalize.getXCoord().multiply(ecFieldElement).equals(normalize2.getXCoord())) {
                throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly");
            }
        }
        printProperty("Point map", "lambda * (x, y) = (beta * x, y)");
        printProperty("beta", ecFieldElement.toBigInteger().toString(16));
        printProperty("lambda", bigInteger.toString(16));
        printScalarDecompositionParameters(x9ECParameters.getN(), bigInteger);
    }
    
    private static void printProperty(final String str, final Object o) {
        final StringBuilder sb = new StringBuilder("  ");
        sb.append(str);
        while (sb.length() < 20) {
            sb.append(' ');
        }
        sb.append(": ");
        sb.append(o.toString());
        System.out.println(sb.toString());
    }
    
    private static void printScalarDecompositionParameters(final BigInteger bigInteger, final BigInteger bigInteger2) {
        final BigInteger[] extEuclidGLV = extEuclidGLV(bigInteger, bigInteger2);
        final BigInteger[] array = { extEuclidGLV[2], extEuclidGLV[3].negate() };
        BigInteger[] chooseShortest = chooseShortest(new BigInteger[] { extEuclidGLV[0], extEuclidGLV[1].negate() }, new BigInteger[] { extEuclidGLV[4], extEuclidGLV[5].negate() });
        if (!isVectorBoundedBySqrt(chooseShortest, bigInteger) && areRelativelyPrime(array[0], array[1])) {
            final BigInteger val = array[0];
            final BigInteger val2 = array[1];
            final BigInteger divide = val.add(val2.multiply(bigInteger2)).divide(bigInteger);
            final BigInteger[] extEuclidBezout = extEuclidBezout(new BigInteger[] { divide.abs(), val2.abs() });
            if (extEuclidBezout != null) {
                BigInteger negate = extEuclidBezout[0];
                BigInteger negate2 = extEuclidBezout[1];
                if (divide.signum() < 0) {
                    negate = negate.negate();
                }
                if (val2.signum() > 0) {
                    negate2 = negate2.negate();
                }
                if (!divide.multiply(negate).subtract(val2.multiply(negate2)).equals(ECConstants.ONE)) {
                    throw new IllegalStateException();
                }
                final BigInteger subtract = negate2.multiply(bigInteger).subtract(negate.multiply(bigInteger2));
                final BigInteger negate3 = negate.negate();
                final BigInteger negate4 = subtract.negate();
                final BigInteger add = isqrt(bigInteger.subtract(ECConstants.ONE)).add(ECConstants.ONE);
                final BigInteger[] intersect = intersect(calculateRange(negate3, add, val2), calculateRange(negate4, add, val));
                if (intersect != null) {
                    for (BigInteger add2 = intersect[0]; add2.compareTo(intersect[1]) <= 0; add2 = add2.add(ECConstants.ONE)) {
                        final BigInteger[] array2 = { subtract.add(add2.multiply(val)), negate.add(add2.multiply(val2)) };
                        if (isShorter(array2, chooseShortest)) {
                            chooseShortest = array2;
                        }
                    }
                }
            }
        }
        final BigInteger subtract2 = array[0].multiply(chooseShortest[1]).subtract(array[1].multiply(chooseShortest[0]));
        final int i = bigInteger.bitLength() + 16 - (bigInteger.bitLength() & 0x7);
        final BigInteger roundQuotient = roundQuotient(chooseShortest[1].shiftLeft(i), subtract2);
        final BigInteger negate5 = roundQuotient(array[1].shiftLeft(i), subtract2).negate();
        printProperty("v1", "{ " + array[0].toString(16) + ", " + array[1].toString(16) + " }");
        printProperty("v2", "{ " + chooseShortest[0].toString(16) + ", " + chooseShortest[1].toString(16) + " }");
        printProperty("d", subtract2.toString(16));
        printProperty("(OPT) g1", roundQuotient.toString(16));
        printProperty("(OPT) g2", negate5.toString(16));
        printProperty("(OPT) bits", Integer.toString(i));
    }
    
    private static boolean areRelativelyPrime(final BigInteger bigInteger, final BigInteger val) {
        return bigInteger.gcd(val).equals(ECConstants.ONE);
    }
    
    private static BigInteger[] calculateRange(final BigInteger bigInteger, final BigInteger bigInteger2, final BigInteger bigInteger3) {
        return order(bigInteger.subtract(bigInteger2).divide(bigInteger3), bigInteger.add(bigInteger2).divide(bigInteger3));
    }
    
    private static List enumToList(final Enumeration enumeration) {
        final ArrayList list = new ArrayList();
        while (enumeration.hasMoreElements()) {
            list.add(enumeration.nextElement());
        }
        return list;
    }
    
    private static BigInteger[] extEuclidBezout(final BigInteger[] array) {
        final boolean b = array[0].compareTo(array[1]) < 0;
        if (b) {
            swap(array);
        }
        BigInteger bigInteger = array[0];
        BigInteger val = array[1];
        BigInteger one = ECConstants.ONE;
        BigInteger zero = ECConstants.ZERO;
        BigInteger zero2 = ECConstants.ZERO;
        BigInteger one2;
        BigInteger bigInteger3;
        BigInteger subtract;
        BigInteger subtract2;
        for (one2 = ECConstants.ONE; val.compareTo(ECConstants.ONE) > 0; val = bigInteger3, one = zero, zero = subtract, zero2 = one2, one2 = subtract2) {
            final BigInteger[] divideAndRemainder = bigInteger.divideAndRemainder(val);
            final BigInteger bigInteger2 = divideAndRemainder[0];
            bigInteger3 = divideAndRemainder[1];
            subtract = one.subtract(bigInteger2.multiply(zero));
            subtract2 = zero2.subtract(bigInteger2.multiply(one2));
            bigInteger = val;
        }
        if (val.signum() <= 0) {
            return null;
        }
        final BigInteger[] array2 = { zero, one2 };
        if (b) {
            swap(array2);
        }
        return array2;
    }
    
    private static BigInteger[] extEuclidGLV(final BigInteger bigInteger, final BigInteger bigInteger2) {
        BigInteger bigInteger3 = bigInteger;
        BigInteger val = bigInteger2;
        BigInteger zero = ECConstants.ZERO;
        BigInteger one = ECConstants.ONE;
        BigInteger bigInteger5;
        BigInteger subtract;
        while (true) {
            final BigInteger[] divideAndRemainder = bigInteger3.divideAndRemainder(val);
            final BigInteger bigInteger4 = divideAndRemainder[0];
            bigInteger5 = divideAndRemainder[1];
            subtract = zero.subtract(bigInteger4.multiply(one));
            if (isLessThanSqrt(val, bigInteger)) {
                break;
            }
            bigInteger3 = val;
            val = bigInteger5;
            zero = one;
            one = subtract;
        }
        return new BigInteger[] { bigInteger3, zero, val, one, bigInteger5, subtract };
    }
    
    private static BigInteger[] chooseShortest(final BigInteger[] array, final BigInteger[] array2) {
        return isShorter(array, array2) ? array : array2;
    }
    
    private static BigInteger[] intersect(final BigInteger[] array, final BigInteger[] array2) {
        final BigInteger max = array[0].max(array2[0]);
        final BigInteger min = array[1].min(array2[1]);
        if (max.compareTo(min) > 0) {
            return null;
        }
        return new BigInteger[] { max, min };
    }
    
    private static boolean isLessThanSqrt(BigInteger abs, BigInteger abs2) {
        abs = abs.abs();
        abs2 = abs2.abs();
        final int bitLength = abs2.bitLength();
        final int n = abs.bitLength() * 2;
        return n - 1 <= bitLength && (n < bitLength || abs.multiply(abs).compareTo(abs2) < 0);
    }
    
    private static boolean isShorter(final BigInteger[] array, final BigInteger[] array2) {
        final BigInteger abs = array[0].abs();
        final BigInteger abs2 = array[1].abs();
        final BigInteger abs3 = array2[0].abs();
        final BigInteger abs4 = array2[1].abs();
        final boolean b = abs.compareTo(abs3) < 0;
        if (b == abs2.compareTo(abs4) < 0) {
            return b;
        }
        return abs.multiply(abs).add(abs2.multiply(abs2)).compareTo(abs3.multiply(abs3).add(abs4.multiply(abs4))) < 0;
    }
    
    private static boolean isVectorBoundedBySqrt(final BigInteger[] array, final BigInteger bigInteger) {
        return isLessThanSqrt(array[0].abs().max(array[1].abs()), bigInteger);
    }
    
    private static BigInteger[] order(final BigInteger bigInteger, final BigInteger val) {
        if (bigInteger.compareTo(val) <= 0) {
            return new BigInteger[] { bigInteger, val };
        }
        return new BigInteger[] { val, bigInteger };
    }
    
    private static BigInteger roundQuotient(BigInteger abs, BigInteger abs2) {
        final boolean b = abs.signum() != abs2.signum();
        abs = abs.abs();
        abs2 = abs2.abs();
        final BigInteger divide = abs.add(abs2.shiftRight(1)).divide(abs2);
        return b ? divide.negate() : divide;
    }
    
    private static BigInteger[] solveQuadraticEquation(final BigInteger bigInteger, final BigInteger bigInteger2, final BigInteger val, final BigInteger val2) {
        final BigInteger modSqrt = modSqrt(val.multiply(val).subtract(bigInteger2.multiply(val2).shiftLeft(2)).mod(bigInteger), bigInteger);
        if (modSqrt == null) {
            throw new IllegalStateException("Solving quadratic equation failed unexpectedly");
        }
        final BigInteger modInverse = bigInteger2.shiftLeft(1).modInverse(bigInteger);
        return new BigInteger[] { modSqrt.subtract(val).multiply(modInverse).mod(bigInteger), modSqrt.negate().subtract(val).multiply(modInverse).mod(bigInteger) };
    }
    
    private static ECFieldElement[] findNonTrivialOrder3FieldElements(final ECCurve ecCurve) {
        final BigInteger characteristic = ecCurve.getField().getCharacteristic();
        final BigInteger divide = characteristic.divide(ECConstants.THREE);
        final SecureRandom secureRandom = new SecureRandom();
        BigInteger modPow;
        do {
            modPow = BigIntegers.createRandomInRange(ECConstants.TWO, characteristic.subtract(ECConstants.TWO), secureRandom).modPow(divide, characteristic);
        } while (modPow.equals(ECConstants.ONE));
        final ECFieldElement fromBigInteger = ecCurve.fromBigInteger(modPow);
        return new ECFieldElement[] { fromBigInteger, fromBigInteger.square() };
    }
    
    private static ECFieldElement[] findNonTrivialOrder4FieldElements(final ECCurve ecCurve) {
        final ECFieldElement sqrt = ecCurve.fromBigInteger(ECConstants.ONE).negate().sqrt();
        if (sqrt == null) {
            throw new IllegalStateException("Calculation of non-trivial order-4  field elements failed unexpectedly");
        }
        return new ECFieldElement[] { sqrt, sqrt.negate() };
    }
    
    private static BigInteger isqrt(final BigInteger bigInteger) {
        BigInteger shiftRight = bigInteger.shiftRight(bigInteger.bitLength() / 2);
        BigInteger shiftRight2;
        while (true) {
            shiftRight2 = shiftRight.add(bigInteger.divide(shiftRight)).shiftRight(1);
            if (shiftRight2.equals(shiftRight)) {
                break;
            }
            shiftRight = shiftRight2;
        }
        return shiftRight2;
    }
    
    private static void swap(final BigInteger[] array) {
        final BigInteger bigInteger = array[0];
        array[0] = array[1];
        array[1] = bigInteger;
    }
    
    private static BigInteger modSqrt(final BigInteger bigInteger, final BigInteger m) {
        if (!m.testBit(0)) {
            throw new IllegalStateException();
        }
        BigInteger bigInteger3;
        final BigInteger bigInteger2 = bigInteger3 = m.subtract(ECConstants.ONE).shiftRight(1);
        if (!bigInteger.modPow(bigInteger3, m).equals(ECConstants.ONE)) {
            return null;
        }
        while (!bigInteger3.testBit(0)) {
            bigInteger3 = bigInteger3.shiftRight(1);
            if (!bigInteger.modPow(bigInteger3, m).equals(ECConstants.ONE)) {
                return modSqrtComplex(bigInteger, bigInteger3, m, bigInteger2);
            }
        }
        return bigInteger.modPow(bigInteger3.add(ECConstants.ONE).shiftRight(1), m);
    }
    
    private static BigInteger modSqrtComplex(final BigInteger bigInteger, BigInteger bigInteger2, final BigInteger bigInteger3, final BigInteger bigInteger4) {
        final BigInteger firstNonResidue = firstNonResidue(bigInteger3, bigInteger4);
        final BigInteger val;
        BigInteger exponent = val = bigInteger4;
        while (!bigInteger2.testBit(0)) {
            bigInteger2 = bigInteger2.shiftRight(1);
            exponent = exponent.shiftRight(1);
            if (!bigInteger.modPow(bigInteger2, bigInteger3).equals(firstNonResidue.modPow(exponent, bigInteger3))) {
                exponent = exponent.add(val);
            }
        }
        bigInteger2 = bigInteger2.subtract(ECConstants.ONE).shiftRight(1);
        return bigInteger.modInverse(bigInteger3).modPow(bigInteger2, bigInteger3).multiply(firstNonResidue.modPow(exponent.shiftRight(1), bigInteger3)).mod(bigInteger3);
    }
    
    private static BigInteger firstNonResidue(final BigInteger m, final BigInteger exponent) {
        for (int i = 2; i < 1000; ++i) {
            final BigInteger value = BigInteger.valueOf(i);
            if (!value.modPow(exponent, m).equals(ECConstants.ONE)) {
                return value;
            }
        }
        throw new IllegalStateException();
    }
}