content: package local.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");
              }
  
              // note: even though this class implements ECConstants don't be tempted to
              // remove the explicit declaration, some J2ME environments don't cope.
              // 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(ECConstants.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
  //            {
  //                if (k2 >= k3)
  //                {
  //                    throw new IllegalArgumentException(
  //                            "k2 must be smaller than k3");
  //                }
  //                if (k2 <= 0)
  //                {
  //                    throw new IllegalArgumentException(
  //                            "k2 must be larger than 0");
  //                }
  //                this.representation = PPB;
  //            }
  //
  //            if (x.signum() < 0)
  //            {
  //                throw new IllegalArgumentException("x value cannot be negative");
  //            }
  //
  //            this.m = m;
  //            this.k1 = k1;
  //            this.k2 = k2;
  //            this.k3 = k3;
  //        }
  //
  //        /**
  //         * Constructor for TPB.
  //         * @param m  The exponent <code>m</code> of
  //         * <code>F<sub>2<sup>m</sup></sub></code>.
  //         * @param k 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>.
  //         * @param x The BigInteger representing the value of the field element.
  //         */
  //        public F2m(int m, int k, BigInteger x)
  //        {
  //            // Set k1 to k, and set k2 and k3 to 0
  //            this(m, k, 0, 0, x);
  //        }
  //
  //        public BigInteger toBigInteger()
  //        {
  //            return x;
  //        }
  //
  //        public String getFieldName()
  //        {
  //            return "F2m";
  //        }
  //
  //        public int getFieldSize()
  //        {
  //            return m;
  //        }
  //
  //        /**
  //         * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
  //         * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
  //         * (having the same representation).
  //         * @param a field element.
  //         * @param b field element to be compared.
  //         * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
  //         * are not elements of the same field
  //         * <code>F<sub>2<sup>m</sup></sub></code> (having the same
  //         * representation). 
  //         */
  //        public static void checkFieldElements(
  //            ECFieldElement a,
  //            ECFieldElement b)
  //        {
  //            if ((!(a instanceof F2m)) || (!(b instanceof F2m)))
  //            {
  //                throw new IllegalArgumentException("Field elements are not "
  //                        + "both instances of ECFieldElement.F2m");
  //            }
  //
  //            if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0))
  //            {
  //                throw new IllegalArgumentException(
  //                        "x value may not be negative");
  //            }
  //
  //            ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a;
  //            ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b;
  //
  //            if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
  //                    || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
  //            {
  //                throw new IllegalArgumentException("Field elements are not "
  //                        + "elements of the same field F2m");
  //            }
  //
  //            if (aF2m.representation != bF2m.representation)
  //            {
  //                // Should never occur
  //                throw new IllegalArgumentException(
  //                        "One of the field "
  //                                + "elements are not elements has incorrect representation");
  //            }
  //        }
  //
  //        /**
  //         * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is
  //         * the reduction polynomial of <code>this</code>.
  //         * @param a The polynomial <code>a(z)</code> to be multiplied by
  //         * <code>z mod f(z)</code>.
  //         * @return <code>z * a(z) mod f(z)</code>
  //         */
  //        private BigInteger multZModF(final BigInteger a)
  //        {
  //            // Left-shift of a(z)
  //            BigInteger az = a.shiftLeft(1);
  //            if (az.testBit(this.m)) 
  //            {
  //                // If the coefficient of z^m in a(z) equals 1, reduction
  //                // modulo f(z) is performed: Add f(z) to to a(z):
  //                // Step 1: Unset mth coeffient of a(z)
  //                az = az.clearBit(this.m);
  //
  //                // Step 2: Add r(z) to a(z), where r(z) is defined as
  //                // f(z) = z^m + r(z), and k1, k2, k3 are the positions of
  //                // the non-zero coefficients in r(z)
  //                az = az.flipBit(0);
  //                az = az.flipBit(this.k1);
  //                if (this.representation == PPB) 
  //                {
  //                    az = az.flipBit(this.k2);
  //                    az = az.flipBit(this.k3);
  //                }
  //            }
  //            return az;
  //        }
  //
  //        public ECFieldElement add(final ECFieldElement b)
  //        {
  //            // No check performed here for performance reasons. Instead the
  //            // elements involved are checked in ECPoint.F2m
  //            // checkFieldElements(this, b);
  //            if (b.toBigInteger().signum() == 0)
  //            {
  //                return this;
  //            }
  //
  //            return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger()));
  //        }
  //
  //        public ECFieldElement subtract(final ECFieldElement b)
  //        {
  //            // Addition and subtraction are the same in F2m
  //            return add(b);
  //        }
  //
  //
  //        public ECFieldElement multiply(final ECFieldElement b)
  //        {
  //            // Left-to-right shift-and-add field multiplication in F2m
  //            // Input: Binary polynomials a(z) and b(z) of degree at most m-1
  //            // Output: c(z) = a(z) * b(z) mod f(z)
  //
  //            // No check performed here for performance reasons. Instead the
  //            // elements involved are checked in ECPoint.F2m
  //            // checkFieldElements(this, b);
  //            final BigInteger az = this.x;
  //            BigInteger bz = b.toBigInteger();
  //            BigInteger cz;
  //
  //            // Compute c(z) = a(z) * b(z) mod f(z)
  //            if (az.testBit(0)) 
  //            {
  //                cz = bz;
  //            } 
  //            else 
  //            {
  //                cz = ECConstants.ZERO;
  //            }
  //
  //            for (int i = 1; i < this.m; i++) 
  //            {
  //                // b(z) := z * b(z) mod f(z)
  //                bz = multZModF(bz);
  //
  //                if (az.testBit(i)) 
  //                {
  //                    // If the coefficient of x^i in a(z) equals 1, b(z) is added
  //                    // to c(z)
  //                    cz = cz.xor(bz);
  //                }
  //            }
  //            return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz);
  //        }
  //
  //
  //        public ECFieldElement divide(final ECFieldElement b)
  //        {
  //            // There may be more efficient implementations
  //            ECFieldElement bInv = b.invert();
  //            return multiply(bInv);
  //        }
  //
  //        public ECFieldElement negate()
  //        {
  //            // -x == x holds for all x in F2m
  //            return this;
  //        }
  //
  //        public ECFieldElement square()
  //        {
  //            // Naive implementation, can probably be speeded up using modular
  //            // reduction
  //            return multiply(this);
  //        }
  //
  //        public ECFieldElement invert()
  //        {
  //            // Inversion in F2m using the extended Euclidean algorithm
  //            // Input: A nonzero polynomial a(z) of degree at most m-1
  //            // Output: a(z)^(-1) mod f(z)
  //
  //            // u(z) := a(z)
  //            BigInteger uz = this.x;
  //            if (uz.signum() <= 0) 
  //            {
  //                throw new ArithmeticException("x is zero or negative, " +
  //                        "inversion is impossible");
  //            }
  //
  //            // v(z) := f(z)
  //            BigInteger vz = ECConstants.ZERO.setBit(m);
  //            vz = vz.setBit(0);
  //            vz = vz.setBit(this.k1);
  //            if (this.representation == PPB) 
  //            {
  //                vz = vz.setBit(this.k2);
  //                vz = vz.setBit(this.k3);
  //            }
  //
  //            // g1(z) := 1, g2(z) := 0
  //            BigInteger g1z = ECConstants.ONE;
  //            BigInteger g2z = ECConstants.ZERO;
  //
  //            // while u != 1
  //            while (!(uz.equals(ECConstants.ZERO))) 
  //            {
  //                // j := deg(u(z)) - deg(v(z))
  //                int j = uz.bitLength() - vz.bitLength();
  //
  //                // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
  //                if (j < 0) 
  //                {
  //                    final BigInteger uzCopy = uz;
  //                    uz = vz;
  //                    vz = uzCopy;
  //
  //                    final BigInteger g1zCopy = g1z;
  //                    g1z = g2z;
  //                    g2z = g1zCopy;
  //
  //                    j = -j;
  //                }
  //
  //                // u(z) := u(z) + z^j * v(z)
  //                // Note, that no reduction modulo f(z) is required, because
  //                // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
  //                // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
  //                // = deg(u(z))
  //                uz = uz.xor(vz.shiftLeft(j));
  //
  //                // g1(z) := g1(z) + z^j * g2(z)
  //                g1z = g1z.xor(g2z.shiftLeft(j));
  ////                if (g1z.bitLength() > this.m) {
  ////                    throw new ArithmeticException(
  ////                            "deg(g1z) >= m, g1z = " + g1z.toString(2));
  ////                }
  //            }
  //            return new ECFieldElement.F2m(
  //                    this.m, this.k1, this.k2, this.k3, g2z);
  //        }
  //
  //        public ECFieldElement sqrt()
  //        {
  //            throw new RuntimeException("Not implemented");
  //        }
  //
  //        /**
  //         * @return the representation of the field
  //         * <code>F<sub>2<sup>m</sup></sub></code>, either of
  //         * TPB (trinomial
  //         * basis representation) or
  //         * PPB (pentanomial
  //         * basis representation).
  //         */
  //        public int getRepresentation()
  //        {
  //            return this.representation;
  //        }
  //
  //        /**
  //         * @return the degree <code>m</code> of the reduction polynomial
  //         * <code>f(z)</code>.
  //         */
  //        public int getM()
  //        {
  //            return this.m;
  //        }
  //
  //        /**
  //         * @return 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>
  //         */
  //        public int getK1()
  //        {
  //            return this.k1;
  //        }
  //
  //        /**
  //         * @return TPB: Always returns <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>
  //         */
  //        public int getK2()
  //        {
  //            return this.k2;
  //        }
  //
  //        /**
  //         * @return 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>
  //         */
  //        public int getK3()
  //        {
  //            return this.k3;
  //        }
  //
  //        public boolean equals(Object anObject)
  //        {
  //            if (anObject == this) 
  //            {
  //                return true;
  //            }
  //
  //            if (!(anObject instanceof ECFieldElement.F2m)) 
  //            {
  //                return false;
  //            }
  //
  //            ECFieldElement.F2m b = (ECFieldElement.F2m)anObject;
  //            
  //            return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2)
  //                && (this.k3 == b.k3)
  //                && (this.representation == b.representation)
  //                && (this.x.equals(b.x)));
  //        }
  //
  //        public int hashCode()
  //        {
  //            return x.hashCode() ^ m ^ k1 ^ k2 ^ k3;
  //        }
  //    }
  
      /**
       * 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
      {
          /**
           * 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;
  
          /**
           * The <code>IntArray</code> holding the bits.
           */
          private IntArray x;
  
          /**
           * The number of <code>int</code>s required to hold <code>m</code> bits.
           */
          private int t;
  
          /**
           * 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)
          {
              // t = m / 32 rounded up to the next integer
              t = (m + 31) >> 5;
              this.x = new IntArray(x, t);
  
              if ((k2 == 0) && (k3 == 0))
              {
                  this.representation = TPB;
              }
              else
              {
                  if (k2 >= k3)
                  {
                      throw new IllegalArgumentException(
                              "k2 must be smaller than k3");
                  }
                  if (k2 <= 0)
                  {
                      throw new IllegalArgumentException(
                              "k2 must be larger than 0");
                  }
                  this.representation = PPB;
              }
  
              if (x.signum() < 0)
              {
                  throw new IllegalArgumentException("x value cannot be negative");
              }
  
              this.m = m;
              this.k1 = k1;
              this.k2 = k2;
              this.k3 = k3;
          }
  
          /**
           * Constructor for TPB.
           * @param m  The exponent <code>m</code> of
           * <code>F<sub>2<sup>m</sup></sub></code>.
           * @param k 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>.
           * @param x The BigInteger representing the value of the field element.
           */
          public F2m(int m, int k, BigInteger x)
          {
              // Set k1 to k, and set k2 and k3 to 0
              this(m, k, 0, 0, x);
          }
  
          private F2m(int m, int k1, int k2, int k3, IntArray x)
          {
              t = (m + 31) >> 5;
              this.x = x;
              this.m = m;
              this.k1 = k1;
              this.k2 = k2;
              this.k3 = k3;
  
              if ((k2 == 0) && (k3 == 0))
              {
                  this.representation = TPB;
              }
              else
              {
                  this.representation = PPB;
              }
  
          }
  
          public BigInteger toBigInteger()
          {
              return x.toBigInteger();
          }
  
          public String getFieldName()
          {
              return "F2m";
          }
  
          public int getFieldSize()
          {
              return m;
          }
  
          /**
           * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
           * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
           * (having the same representation).
           * @param a field element.
           * @param b field element to be compared.
           * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
           * are not elements of the same field
           * <code>F<sub>2<sup>m</sup></sub></code> (having the same
           * representation). 
           */
          public static void checkFieldElements(
              ECFieldElement a,
              ECFieldElement b)
          {
              if ((!(a instanceof F2m)) || (!(b instanceof F2m)))
              {
                  throw new IllegalArgumentException("Field elements are not "
                          + "both instances of ECFieldElement.F2m");
              }
  
              ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a;
              ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b;
  
              if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
                      || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
              {
                  throw new IllegalArgumentException("Field elements are not "
                          + "elements of the same field F2m");
              }
  
              if (aF2m.representation != bF2m.representation)
              {
                  // Should never occur
                  throw new IllegalArgumentException(
                          "One of the field "
                                  + "elements are not elements has incorrect representation");
              }
          }
  
          public ECFieldElement add(final ECFieldElement b)
          {
              // No check performed here for performance reasons. Instead the
              // elements involved are checked in ECPoint.F2m
              // checkFieldElements(this, b);
              IntArray iarrClone = (IntArray)this.x.clone();
              F2m bF2m = (F2m)b;
              iarrClone.addShifted(bF2m.x, 0);
              return new F2m(m, k1, k2, k3, iarrClone);
          }
  
          public ECFieldElement subtract(final ECFieldElement b)
          {
              // Addition and subtraction are the same in F2m
              return add(b);
          }
  
          public ECFieldElement multiply(final ECFieldElement b)
          {
              // Right-to-left comb multiplication in the IntArray
              // Input: Binary polynomials a(z) and b(z) of degree at most m-1
              // Output: c(z) = a(z) * b(z) mod f(z)
  
              // No check performed here for performance reasons. Instead the
              // elements involved are checked in ECPoint.F2m
              // checkFieldElements(this, b);
              F2m bF2m = (F2m)b;
              IntArray mult = x.multiply(bF2m.x, m);
              mult.reduce(m, new int[]{k1, k2, k3});
              return new F2m(m, k1, k2, k3, mult);
          }
  
          public ECFieldElement divide(final ECFieldElement b)
          {
              // There may be more efficient implementations
              ECFieldElement bInv = b.invert();
              return multiply(bInv);
          }
  
          public ECFieldElement negate()
          {
              // -x == x holds for all x in F2m
              return this;
          }
  
          public ECFieldElement square()
          {
              IntArray squared = x.square(m);
              squared.reduce(m, new int[]{k1, k2, k3});
              return new F2m(m, k1, k2, k3, squared);
          }
  
  
          public ECFieldElement invert()
          {
              // Inversion in F2m using the extended Euclidean algorithm
              // Input: A nonzero polynomial a(z) of degree at most m-1
              // Output: a(z)^(-1) mod f(z)
  
              // u(z) := a(z)
              IntArray uz = (IntArray)this.x.clone();
  
              // v(z) := f(z)
              IntArray vz = new IntArray(t);
              vz.setBit(m);
              vz.setBit(0);
              vz.setBit(this.k1);
              if (this.representation == PPB) 
              {
                  vz.setBit(this.k2);
                  vz.setBit(this.k3);
              }
  
              // g1(z) := 1, g2(z) := 0
              IntArray g1z = new IntArray(t);
              g1z.setBit(0);
              IntArray g2z = new IntArray(t);
  
              // while u != 0
              while (!uz.isZero())
  //            while (uz.getUsedLength() > 0)
  //            while (uz.bitLength() > 1)
              {
                  // j := deg(u(z)) - deg(v(z))
                  int j = uz.bitLength() - vz.bitLength();
  
                  // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
                  if (j < 0) 
                  {
                      final IntArray uzCopy = uz;
                      uz = vz;
                      vz = uzCopy;
  
                      final IntArray g1zCopy = g1z;
                      g1z = g2z;
                      g2z = g1zCopy;
  
                      j = -j;
                  }
  
                  // u(z) := u(z) + z^j * v(z)
                  // Note, that no reduction modulo f(z) is required, because
                  // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
                  // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
                  // = deg(u(z))
                  // uz = uz.xor(vz.shiftLeft(j));
                  // jInt = n / 32
                  int jInt = j >> 5;
                  // jInt = n % 32
                  int jBit = j & 0x1F;
                  IntArray vzShift = vz.shiftLeft(jBit);
                  uz.addShifted(vzShift, jInt);
  
                  // g1(z) := g1(z) + z^j * g2(z)
  //                g1z = g1z.xor(g2z.shiftLeft(j));
                  IntArray g2zShift = g2z.shiftLeft(jBit);
                  g1z.addShifted(g2zShift, jInt);
                  
              }
              return new ECFieldElement.F2m(
                      this.m, this.k1, this.k2, this.k3, g2z);
          }
  
          public ECFieldElement sqrt()
          {
              throw new RuntimeException("Not implemented");
          }
  
          /**
           * @return the representation of the field
           * <code>F<sub>2<sup>m</sup></sub></code>, either of
           * TPB (trinomial
           * basis representation) or
           * PPB (pentanomial
           * basis representation).
           */
          public int getRepresentation()
          {
              return this.representation;
          }
  
          /**
           * @return the degree <code>m</code> of the reduction polynomial
           * <code>f(z)</code>.
           */
          public int getM()
          {
              return this.m;
          }
  
          /**
           * @return 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>
           */
          public int getK1()
          {
              return this.k1;
          }
  
          /**
           * @return TPB: Always returns <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>
           */
          public int getK2()
          {
              return this.k2;
          }
  
          /**
           * @return 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>
           */
          public int getK3()
          {
              return this.k3;
          }
  
          public boolean equals(Object anObject)
          {
              if (anObject == this) 
              {
                  return true;
              }
  
              if (!(anObject instanceof ECFieldElement.F2m)) 
              {
                  return false;
              }
  
              ECFieldElement.F2m b = (ECFieldElement.F2m)anObject;
              
              return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2)
                  && (this.k3 == b.k3)
                  && (this.representation == b.representation)
                  && (this.x.equals(b.x)));
          }
  
          public int hashCode()
          {
              return x.hashCode() ^ m ^ k1 ^ k2 ^ k3;
          }
      }
  }
  