ecfieldelement.java

kmlnjlkj nlkjlkjkljl okopokipoipo oipipipo i

package org.bouncycastle.math.ec;

import java.math.BigInteger;
import java.util.Random;

public abstract class ECFieldElement
    implements ECConstants
{

    public abstract BigInteger     toBigInteger();
    public abstract String         getFieldName();
    public abstract int            getFieldSize();
    public abstract ECFieldElement add(ECFieldElement b);
    public abstract ECFieldElement subtract(ECFieldElement b);
    public abstract ECFieldElement multiply(ECFieldElement b);
    public abstract ECFieldElement divide(ECFieldElement b);
    public abstract ECFieldElement negate();
    public abstract ECFieldElement square();
    public abstract ECFieldElement invert();
    public abstract ECFieldElement sqrt();

    public String toString()
    {
        return this.toBigInteger().toString(2);
    }

    public static class Fp extends ECFieldElement
    {
        BigInteger x;

        BigInteger q;
        
        public Fp(BigInteger q, BigInteger x)
        {
            this.x = x;
            
            if (x.compareTo(q) >= 0)
            {
                throw new IllegalArgumentException("x value too large in field element");
            }

            this.q = q;
        }

        public BigInteger toBigInteger()
        {
            return x;
        }

        /**
         * return the field name for this field.
         *
         * @return the string "Fp".
         */
        public String getFieldName()
        {
            return "Fp";
        }

        public int getFieldSize()
        {
            return q.bitLength();
        }

        public BigInteger getQ()
        {
            return q;
        }
        
        public ECFieldElement add(ECFieldElement b)
        {
            return new Fp(q, x.add(b.toBigInteger()).mod(q));
        }

        public ECFieldElement subtract(ECFieldElement b)
        {
            return new Fp(q, x.subtract(b.toBigInteger()).mod(q));
        }

        public ECFieldElement multiply(ECFieldElement b)
        {
            return new Fp(q, x.multiply(b.toBigInteger()).mod(q));
        }

        public ECFieldElement divide(ECFieldElement b)
        {
            return new Fp(q, x.multiply(b.toBigInteger().modInverse(q)).mod(q));
        }

        public ECFieldElement negate()
        {
            return new Fp(q, x.negate().mod(q));
        }

        public ECFieldElement square()
        {
            return new Fp(q, x.multiply(x).mod(q));
        }

        public ECFieldElement invert()
        {
            return new Fp(q, x.modInverse(q));
        }

        // D.1.4 91
        /**
         * return a sqrt root - the routine verifies that the calculation
         * returns the right value - if none exists it returns null.
         */
        public ECFieldElement sqrt()
        {
            if (!q.testBit(0))
            {
                throw new RuntimeException("not done yet");
            }

            // p mod 4 == 3
            if (q.testBit(1))
            {
                // z = g^(u+1) + p, p = 4u + 3
                ECFieldElement z = new Fp(q, x.modPow(q.shiftRight(2).add(ONE), q));

                return z.square().equals(this) ? z : null;
            }

            // p mod 4 == 1
            BigInteger qMinusOne = q.subtract(ECConstants.ONE);

            BigInteger legendreExponent = qMinusOne.shiftRight(1);
            if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
            {
                return null;
            }

            BigInteger u = qMinusOne.shiftRight(2);
            BigInteger k = u.shiftLeft(1).add(ECConstants.ONE);

            BigInteger Q = this.x;
            BigInteger fourQ = Q.shiftLeft(2).mod(q);

            BigInteger U, V;
            Random rand = new Random();
            do
            {
                BigInteger P;
                do
                {
                    P = new BigInteger(q.bitLength(), rand);
                }
                while (P.compareTo(q) >= 0
                    || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne)));

                BigInteger[] result = lucasSequence(q, P, Q, k);
                U = result[0];
                V = result[1];

                if (V.multiply(V).mod(q).equals(fourQ))
                {
                    // Integer division by 2, mod q
                    if (V.testBit(0))
                    {
                        V = V.add(q);
                    }

                    V = V.shiftRight(1);

                    //assert V.multiply(V).mod(q).equals(x);

                    return new ECFieldElement.Fp(q, V);
                }
            }
            while (U.equals(ECConstants.ONE) || U.equals(qMinusOne));

            return null;

//            BigInteger qMinusOne = q.subtract(ECConstants.ONE);
//            BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO);
//            if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
//            {
//                return null;
//            }
//
//            Random rand = new Random();
//            BigInteger fourX = x.shiftLeft(2);
//
//            BigInteger r;
//            do
//            {
//                r = new BigInteger(q.bitLength(), rand);
//            }
//            while (r.compareTo(q) >= 0
//                || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne)));
//
//            BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR);
//            BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR);
//
//            BigInteger wOne = WOne(r, x, q);
//            BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q);
//            BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r);
//
//            BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q)
//                .multiply(x).mod(q)
//                .multiply(wSum).mod(q);
//
//            return new Fp(q, root);
        }

//        private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p)
//        {
//            if (n.equals(ECConstants.ONE))
//            {
//                return wOne;
//            }
//            boolean isEven = !n.testBit(0);
//            n = n.shiftRight(1);//divide(ECConstants.TWO);
//            if (isEven)
//            {
//                BigInteger w = W(n, wOne, p);
//                return w.multiply(w).subtract(ECConstants.TWO).mod(p);
//            }
//            BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p);
//            BigInteger w2 = W(n, wOne, p);
//            return w1.multiply(w2).subtract(wOne).mod(p);
//        }
//
//        private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p)
//        {
//            return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p);
//        }

        private static BigInteger[] lucasSequence(
            BigInteger  p,
            BigInteger  P,
            BigInteger  Q,
            BigInteger  k)
        {
            int n = k.bitLength();
            int s = k.getLowestSetBit();

            BigInteger Uh = ECConstants.ONE;
            BigInteger Vl = ECConstants.TWO;
            BigInteger Vh = P;
            BigInteger Ql = ECConstants.ONE;
            BigInteger Qh = ECConstants.ONE;

            for (int j = n - 1; j >= s + 1; --j)
            {
                Ql = Ql.multiply(Qh).mod(p);

                if (k.testBit(j))
                {
                    Qh = Ql.multiply(Q).mod(p);
                    Uh = Uh.multiply(Vh).mod(p);
                    Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
                    Vh = Vh.multiply(Vh).subtract(Qh.shiftLeft(1)).mod(p);
                }
                else
                {
                    Qh = Ql;
                    Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
                    Vh = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
                    Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p);
                }
            }

            Ql = Ql.multiply(Qh).mod(p);
            Qh = Ql.multiply(Q).mod(p);
            Uh = Uh.multiply(Vl).subtract(Ql).mod(p);
            Vl = Vh.multiply(Vl).subtract(P.multiply(Ql)).mod(p);
            Ql = Ql.multiply(Qh).mod(p);

            for (int j = 1; j <= s; ++j)
            {
                Uh = Uh.multiply(Vl).mod(p);
                Vl = Vl.multiply(Vl).subtract(Ql.shiftLeft(1)).mod(p);
                Ql = Ql.multiply(Ql).mod(p);
            }

            return new BigInteger[]{ Uh, Vl };
        }
        
        public boolean equals(Object other)
        {
            if (other == this)
            {
                return true;
            }

            if (!(other instanceof ECFieldElement.Fp))
            {
                return false;
            }
            
            ECFieldElement.Fp o = (ECFieldElement.Fp)other;
            return q.equals(o.q) && x.equals(o.x);
        }

        public int hashCode()
        {
            return q.hashCode() ^ x.hashCode();
        }
    }

//    /**
//     * Class representing the Elements of the finite field
//     * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
//     * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
//     * basis representations are supported. Gaussian normal basis (GNB)
//     * representation is not supported.
//     */
//    public static class F2m extends ECFieldElement
//    {
//        BigInteger x;
//
//        /**
//         * Indicates gaussian normal basis representation (GNB). Number chosen
//         * according to X9.62. GNB is not implemented at present.
//         */
//        public static final int GNB = 1;
//
//        /**
//         * Indicates trinomial basis representation (TPB). Number chosen
//         * according to X9.62.
//         */
//        public static final int TPB = 2;
//
//        /**
//         * Indicates pentanomial basis representation (PPB). Number chosen
//         * according to X9.62.
//         */
//        public static final int PPB = 3;
//
//        /**
//         * TPB or PPB.
//         */
//        private int representation;
//
//        /**
//         * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
//         */
//        private int m;
//
//        /**
//         * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
//         * x<sup>k</sup> + 1</code> represents the reduction polynomial
//         * <code>f(z)</code>.<br>
//         * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
//         * represents the reduction polynomial <code>f(z)</code>.<br>
//         */
//        private int k1;
//
//        /**
//         * TPB: Always set to <code>0</code><br>
//         * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
//         * represents the reduction polynomial <code>f(z)</code>.<br>
//         */
//        private int k2;
//
//        /**
//         * TPB: Always set to <code>0</code><br>
//         * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
//         * represents the reduction polynomial <code>f(z)</code>.<br>
//         */
//        private int k3;
//        
//        /**
//         * Constructor for PPB.
//         * @param m  The exponent <code>m</code> of
//         * <code>F<sub>2<sup>m</sup></sub></code>.
//         * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
//         * represents the reduction polynomial <code>f(z)</code>.
//         * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
//         * represents the reduction polynomial <code>f(z)</code>.
//         * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
//         * represents the reduction polynomial <code>f(z)</code>.
//         * @param x The BigInteger representing the value of the field element.
//         */
//        public F2m(
//            int m, 
//            int k1, 
//            int k2, 
//            int k3,
//            BigInteger x)
//        {
////            super(x);
//            this.x = x;
//
//            if ((k2 == 0) && (k3 == 0))
//            {
//                this.representation = TPB;
//            }
//            else
//            {