Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  package org.bouncycastle.math.ec;
  
  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 addOne();
     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 int bitLength()
     {
         return toBigInteger().bitLength();
     }
 
     public boolean isOne()
     {
         return bitLength() == 1;
     }
 
     public boolean isZero()
     {
         return 0 == toBigInteger().signum();
     }
 
     {
         return multiply(b).subtract(x.multiply(y));
     }
 
     {
         return multiply(b).add(x.multiply(y));
     }
 
     {
         return square().subtract(x.multiply(y));
     }
 
     {
         return square().add(x.multiply(y));
     }
 
     public boolean testBitZero()
     {
         return toBigInteger().testBit(0);
     }
 
     public String toString()
     {
         return this.toBigInteger().toString(16);
     }
 
     public byte[] getEncoded()
     {
         return BigIntegers.asUnsignedByteArray((getFieldSize() + 7) / 8, toBigInteger());
     }
 
     public static class Fp extends ECFieldElement
     {
         BigInteger qrx;
 
         static BigInteger calculateResidue(BigInteger p)
         {
             int bitLength = p.bitLength();
             if (bitLength >= 96)
             {
                 BigInteger firstWord = p.shiftRight(bitLength - 64);
                 if (firstWord.longValue() == -1L)
                 {
                     return .shiftLeft(bitLength).subtract(p);
                 }
             }
             return null;
         }

        

Deprecated:
Use ECCurve.fromBigInteger to construct field elements
 
         public Fp(BigInteger qBigInteger x)
         {
            this(qcalculateResidue(q), x);
        }
        Fp(BigInteger qBigInteger rBigInteger x)
        {
            if (x == null || x.signum() < 0 || x.compareTo(q) >= 0)
            {
                throw new IllegalArgumentException("x value invalid in Fp field element");
            }
            this. = q;
            this. = r;
            this. = x;
        }
        public BigInteger toBigInteger()
        {
            return ;
        }

        
return the field name for this field.

Returns:
the string "Fp".
        public String getFieldName()
        {
            return "Fp";
        }
        public int getFieldSize()
        {
            return .bitLength();
        }
        public BigInteger getQ()
        {
            return ;
        }
        public ECFieldElement add(ECFieldElement b)
        {
            return new Fp(modAdd(b.toBigInteger()));
        }
        public ECFieldElement addOne()
        {
            BigInteger x2 = .add(.);
            if (x2.compareTo() == 0)
            {
                x2 = .;
            }
            return new Fp(x2);
        }
        public ECFieldElement subtract(ECFieldElement b)
        {
            return new Fp(modSubtract(b.toBigInteger()));
        }
        public ECFieldElement multiply(ECFieldElement b)
        {
            return new Fp(modMult(b.toBigInteger()));
        }
        {
            BigInteger ax = this.bx = b.toBigInteger(), xx = x.toBigInteger(), yx = y.toBigInteger();
            BigInteger ab = ax.multiply(bx);
            BigInteger xy = xx.multiply(yx);
            return new Fp(modReduce(ab.subtract(xy)));
        }
        {
            BigInteger ax = this.bx = b.toBigInteger(), xx = x.toBigInteger(), yx = y.toBigInteger();
            BigInteger ab = ax.multiply(bx);
            BigInteger xy = xx.multiply(yx);
            return new Fp(modReduce(ab.add(xy)));
        }
        public ECFieldElement divide(ECFieldElement b)
        {
            return new Fp(modMult(modInverse(b.toBigInteger())));
        }
        public ECFieldElement negate()
        {
            return .signum() == 0 ? this : new Fp(.subtract());
        }
        public ECFieldElement square()
        {
            return new Fp(modMult());
        }
        {
            BigInteger ax = this.xx = x.toBigInteger(), yx = y.toBigInteger();
            BigInteger aa = ax.multiply(ax);
            BigInteger xy = xx.multiply(yx);
            return new Fp(modReduce(aa.subtract(xy)));
        }
        {
            BigInteger ax = this.xx = x.toBigInteger(), yx = y.toBigInteger();
            BigInteger aa = ax.multiply(ax);
            BigInteger xy = xx.multiply(yx);
            return new Fp(modReduce(aa.add(xy)));
        }
        public ECFieldElement invert()
        {
            // TODO Modular inversion can be faster for a (Generalized) Mersenne Prime.
            return new Fp(modInverse());
        }
        // 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 (this.isZero() || this.isOne()) // earlier JDK compatibility
            {
                return this;
            }
            if (!.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.
            if (.testBit(1)) // q == 4m + 3
            {
                BigInteger e = .shiftRight(2).add(.);
                return checkSqrt(new Fp(.modPow(e)));
            }
            if (.testBit(2)) // q == 8m + 5
            {
                BigInteger t1 = .modPow(.shiftRight(3), );
                BigInteger t2 = modMult(t1);
                BigInteger t3 = modMult(t2t1);
                if (t3.equals(.))
                {
                    return checkSqrt(new Fp(t2));
                }
                // TODO This is constant and could be precomputed
                BigInteger t4 = ..modPow(.shiftRight(2), );
                BigInteger y = modMult(t2t4);
                return checkSqrt(new Fp(y));
            }
            // q == 8m + 1
            BigInteger legendreExponent = .shiftRight(1);
            if (!(.modPow(legendreExponent).equals(.)))
            {
                return null;
            }
            BigInteger X = this.;
            BigInteger fourX = modDouble(modDouble(X));
            BigInteger k = legendreExponent.add(.), qMinusOne = .subtract(.);
            BigInteger UV;
            Random rand = new Random();
            do
            {
                BigInteger P;
                do
                {
                    P = new BigInteger(.bitLength(), rand);
                }
                while (P.compareTo() >= 0
                    || !modReduce(P.multiply(P).subtract(fourX)).modPow(legendreExponent).equals(qMinusOne));
                BigInteger[] result = lucasSequence(PXk);
                U = result[0];
                V = result[1];
                if (modMult(VV).equals(fourX))
                {
                    return new ECFieldElement.Fp(modHalfAbs(V));
                }
            }
            while (U.equals(.) || U.equals(qMinusOne));
            return null;
        }
        private ECFieldElement checkSqrt(ECFieldElement z)
        {
            return z.square().equals(this) ? z : null;
        }
        private BigInteger[] lucasSequence(
            BigInteger  P,
            BigInteger  Q,
            BigInteger  k)
        {
            // TODO Research and apply "common-multiplicand multiplication here"
            int n = k.bitLength();
            int s = k.getLowestSetBit();
            // assert k.testBit(s);
            BigInteger Uh = .;
            BigInteger Vl = .;
            BigInteger Vh = P;
            BigInteger Ql = .;
            BigInteger Qh = .;
            for (int j = n - 1; j >= s + 1; --j)
            {
                Ql = modMult(QlQh);
                if (k.testBit(j))
                {
                    Qh = modMult(QlQ);
                    Uh = modMult(UhVh);
                    Vl = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
                    Vh = modReduce(Vh.multiply(Vh).subtract(Qh.shiftLeft(1)));
                }
                else
                {
                    Qh = Ql;
                    Uh = modReduce(Uh.multiply(Vl).subtract(Ql));
                    Vh = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
                    Vl = modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
                }
            }
            Ql = modMult(QlQh);
            Qh = modMult(QlQ);
            Uh = modReduce(Uh.multiply(Vl).subtract(Ql));
            Vl = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
            Ql = modMult(QlQh);
            for (int j = 1; j <= s; ++j)
            {
                Uh = modMult(UhVl);
                Vl = modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
                Ql = modMult(QlQl);
            }
            return new BigInteger[]{ UhVl };
        }
        protected BigInteger modAdd(BigInteger x1BigInteger x2)
        {
            BigInteger x3 = x1.add(x2);
            if (x3.compareTo() >= 0)
            {
                x3 = x3.subtract();
            }
            return x3;
        }
        protected BigInteger modDouble(BigInteger x)
        {
            BigInteger _2x = x.shiftLeft(1);
            if (_2x.compareTo() >= 0)
            {
                _2x = _2x.subtract();
            }
            return _2x;
        }
        protected BigInteger modHalf(BigInteger x)
        {
            if (x.testBit(0))
            {
                x = .add(x);
            }
            return x.shiftRight(1);
        }
        protected BigInteger modHalfAbs(BigInteger x)
        {
            if (x.testBit(0))
            {
                x = .subtract(x);
            }
            return x.shiftRight(1);
        }
        protected BigInteger modInverse(BigInteger x)
        {
            int bits = getFieldSize();
            int len = (bits + 31) >> 5;
            int[] p = Nat.fromBigInteger(bits);
            int[] n = Nat.fromBigInteger(bitsx);
            int[] z = Nat.create(len);
            Mod.invert(pnz);
            return Nat.toBigInteger(lenz);
        }
        protected BigInteger modMult(BigInteger x1BigInteger x2)
        {
            return modReduce(x1.multiply(x2));
        }
        protected BigInteger modReduce(BigInteger x)
        {
            if ( != null)
            {
                boolean negative = x.signum() < 0;
                if (negative)
                {
                    x = x.abs();
                }
                int qLen = .bitLength();
                boolean rIsOne = .equals(.);
                while (x.bitLength() > (qLen + 1))
                {
                    BigInteger u = x.shiftRight(qLen);
                    BigInteger v = x.subtract(u.shiftLeft(qLen));
                    if (!rIsOne)
                    {
                        u = u.multiply();
                    }
                    x = u.add(v); 
                }
                while (x.compareTo() >= 0)
                {
                    x = x.subtract();
                }
                if (negative && x.signum() != 0)
                {
                    x = .subtract(x);
                }
            }
            else
            {
                x = x.mod();
            }
            return x;
        }
        protected BigInteger modSubtract(BigInteger x1BigInteger x2)
        {
            BigInteger x3 = x1.subtract(x2);
            if (x3.signum() < 0)
            {
                x3 = x3.add();
            }
            return x3;
        }
        public boolean equals(Object other)
        {
            if (other == this)
            {
                return true;
            }
            if (!(other instanceof ECFieldElement.Fp))
            {
                return false;
            }
            
            ECFieldElement.Fp o = (ECFieldElement.Fp)other;
            return .equals(o.q) && .equals(o.x);
        }
        public int hashCode()
        {
            return .hashCode() ^ .hashCode();
        }
    }

    
Class representing the Elements of the finite field F2m 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 m of F2m.
        private int m;
        private int[] ks;

        
The LongArray holding the bits.
        private LongArray x;

        
Constructor for PPB.

Deprecated:
Use ECCurve.fromBigInteger to construct field elements
Parameters:
m The exponent m of F2m.
k1 The integer k1 where xm + xk3 + xk2 + xk1 + 1 represents the reduction polynomial f(z).
k2 The integer k2 where xm + xk3 + xk2 + xk1 + 1 represents the reduction polynomial f(z).
k3 The integer k3 where xm + xk3 + xk2 + xk1 + 1 represents the reduction polynomial f(z).
x The BigInteger representing the value of the field element.
        public F2m(
            int m
            int k1
            int k2
            int k3,
            BigInteger x)
        {
            if ((k2 == 0) && (k3 == 0))
            {
                this. = ;
                this. = new int[]{ k1 }; 
            }
            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. = ;
                this. = new int[]{ k1k2k3 }; 
            }
            this. = m;
            this. = new LongArray(x);
        }

        
Constructor for TPB.

Deprecated:
Use ECCurve.fromBigInteger to construct field elements
Parameters:
m The exponent m of F2m.
k The integer k where xm + xk + 1 represents the reduction polynomial f(z).
x The BigInteger representing the value of the field element.
        public F2m(int mint kBigInteger x)
        {
            // Set k1 to k, and set k2 and k3 to 0
            this(mk, 0, 0, x);
        }
        private F2m(int mint[] ksLongArray x)
        {
            this. = m;
            this. = (ks.length == 1) ?  : ;
            this. = ks;
            this. = x;
        }
        public int bitLength()
        {
            return .degree();
        }
        public boolean isOne()
        {
            return .isOne();
        }
        public boolean isZero()
        {
            return .isZero();
        }
        public boolean testBitZero()
        {
            return .testBitZero();
        }
        public BigInteger toBigInteger()
        {
            return .toBigInteger();
        }
        public String getFieldName()
        {
            return "F2m";
        }
        public int getFieldSize()
        {
            return ;
        }

        
Checks, if the ECFieldElements a and b are elements of the same field F2m (having the same representation).

Parameters:
a field element.
b field element to be compared.
Throws:
java.lang.IllegalArgumentException if a and b are not elements of the same field F2m (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.representation != bF2m.representation)
            {
                // Should never occur
                throw new IllegalArgumentException("One of the F2m field elements has incorrect representation");
            }
            if ((aF2m.m != bF2m.m) || !Arrays.areEqual(aF2m.ksbF2m.ks))
            {
                throw new IllegalArgumentException("Field elements are not elements of the same field F2m");
            }
        }
        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);
            LongArray iarrClone = (LongArray)this..clone();
            F2m bF2m = (F2m)b;
            iarrClone.addShiftedByWords(bF2m.x, 0);
            return new F2m(iarrClone);
        }
        public ECFieldElement addOne()
        {
            return new F2m(.addOne());
        }
        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 LongArray
            // 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);
            return new F2m(.modMultiply(((F2m)b).));
        }
        {
            return multiplyPlusProduct(bxy);
        }
        {
            LongArray ax = this.bx = ((F2m)b).xx = ((F2m)x).yx = ((F2m)y).;
            LongArray ab = ax.multiply(bx);
            LongArray xy = xx.multiply(yx);
            if (ab == ax || ab == bx)
            {
                ab = (LongArray)ab.clone();
            }
            ab.addShiftedByWords(xy, 0);
            ab.reduce();
            return new F2m(ab);
        }
        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()
        {
            return new F2m(.modSquare());
        }
        {
            return squarePlusProduct(xy);
        }
        {
            LongArray ax = this.xx = ((F2m)x).yx = ((F2m)y).;
            LongArray aa = ax.square();
            LongArray xy = xx.multiply(yx);
            if (aa == ax)
            {
                aa = (LongArray)aa.clone();
            }
            aa.addShiftedByWords(xy, 0);
            aa.reduce();
            return new F2m(aa);
        }
        public ECFieldElement invert()
        {
            return new ECFieldElement.F2m(this.this.this..modInverse());
        }
        public ECFieldElement sqrt()
        {
            LongArray x1 = this.;
            if (x1.isOne() || x1.isZero())
            {
                return this;
            }
            LongArray x2 = x1.modSquareN( - 1, );
            return new ECFieldElement.F2m(x2);
        }

        

Returns:
the representation of the field F2m, either of TPB (trinomial basis representation) or PPB (pentanomial basis representation).
        public int getRepresentation()
        {
            return this.;
        }

        

Returns:
the degree m of the reduction polynomial f(z).
        public int getM()
        {
            return this.;
        }

        

Returns:
TPB: The integer k where xm + xk + 1 represents the reduction polynomial f(z).
PPB: The integer k1 where xm + xk3 + xk2 + xk1 + 1 represents the reduction polynomial f(z).
        public int getK1()
        {
            return this.[0];
        }

        

Returns:
TPB: Always returns 0
PPB: The integer k2 where xm + xk3 + xk2 + xk1 + 1 represents the reduction polynomial f(z).
        public int getK2()
        {
            return this..length >= 2 ? this.[1] : 0;
        }

        

Returns:
TPB: Always set to 0
PPB: The integer k3 where xm + xk3 + xk2 + xk1 + 1 represents the reduction polynomial f(z).
        public int getK3()
        {
            return this..length >= 3 ? this.[2] : 0;
        }
        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. == b.m)
                && (this. == b.representation)
                && Arrays.areEqual(this.b.ks)
                && (this..equals(b.x)));
        }
        public int hashCode()
        {
            return .hashCode() ^  ^ Arrays.hashCode();
        }
    }
New to GrepCode? Check out our FAQ X