Package org.bouncycastle.pqc.legacy.math.linearalgebra

Class GF2Polynomial

  • public class GF2Polynomial
extends java.lang.Object
    This class stores very long strings of bits and does some basic arithmetics. It is used by GF2nField, GF2nPolynomialField and GFnPolynomialElement.
    See Also:
    GF2nPolynomialElement, GF2nField

    • Constructor Summary

      Constructors 
      Constructor Description
      GF2Polynomial​(int length)
      Creates a new GF2Polynomial of the given length and value zero.
      GF2Polynomial​(int length, byte[] os)
      Creates a new GF2Polynomial by converting the given byte[] os according to 1363 and using the given length.
      GF2Polynomial​(int length, int[] bs)
      Creates a new GF2Polynomial of the given length using the given int[].
      GF2Polynomial​(int length, java.lang.String value)
      Creates a new GF2Polynomial of the given length and value selected by value: ZERO ONE RANDOM X ALL
      GF2Polynomial​(int length, java.math.BigInteger bi)
      Creates a new GF2Polynomial by converting the given FlexiBigInt bi according to 1363 and using the given length.
      GF2Polynomial​(int length, java.util.Random rand)
      Creates a new GF2Polynomial of the given length and random value.
      GF2Polynomial​(GF2Polynomial b)
      Creates a new GF2Polynomial by cloneing the given GF2Polynomial b.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      GF2Polynomial add​(GF2Polynomial b)
      Adds two GF2Polynomials, this and b, and returns the result.
      void addToThis​(GF2Polynomial b)
      Adds b to this GF2Polynomial and assigns the result to this GF2Polynomial.
      void assignAll()
      Sets all Bits to 1.
      void assignOne()
      Sets the LSB to 1 and all other to 0, assigning 'one' to this GF2Polynomial.
      void assignX()
      Sets Bit 1 to 1 and all other to 0, assigning 'x' to this GF2Polynomial.
      void assignZero()
      Resets all bits to zero.
      java.lang.Object clone()  
      GF2Polynomial[] divide​(GF2Polynomial g)
      Divides this by g and returns the quotient and remainder in a new GF2Polynomial[2], quotient in [0], remainder in [1].
      boolean equals​(java.lang.Object other)
      Returns true if two GF2Polynomials have the same size and value and thus are equal.
      void expandN​(int i)
      Expands len and int[] value to i.
      GF2Polynomial gcd​(GF2Polynomial g)
      Returns the greatest common divisor of this and g in a new GF2Polynomial.
      int getBit​(int i)
      Returns the bit at position i.
      int getLength()
      Returns the length of this GF2Polynomial.
      int hashCode()  
      GF2Polynomial increase()
      Toggles the LSB of this GF2Polynomial, increasing the value by 'one' and returns the result in a new GF2Polynomial.
      void increaseThis()
      Toggles the LSB of this GF2Polynomial, increasing its value by 'one'.
      boolean isIrreducible()
      Checks if this is irreducible, according to IEEE P1363, A.5.5, p103.
      boolean isOne()
      Tests if all bits are reset to 0 and LSB is set to 1.
      boolean isZero()
      Tests if all bits equal zero.
      GF2Polynomial multiply​(GF2Polynomial b)
      Multiplies this GF2Polynomial with b and returns the result in a new GF2Polynomial.
      GF2Polynomial multiplyClassic​(GF2Polynomial b)
      Multiplies this GF2Polynomial with b and returns the result in a new GF2Polynomial.
      GF2Polynomial quotient​(GF2Polynomial g)
      Returns the absolute quotient of this divided by g in a new GF2Polynomial.
      void randomize()
      Fills all len bits of this GF2Polynomial with random values.
      void randomize​(java.util.Random rand)
      Fills all len bits of this GF2Polynomial with random values using the specified source of randomness.
      void reduceN()
      Reduces len by finding the most significant bit set to one and reducing len and blocks.
      GF2Polynomial remainder​(GF2Polynomial g)
      Returns the remainder of this divided by g in a new GF2Polynomial.
      void resetBit​(int i)
      Resets the bit at position i.
      void setBit​(int i)
      Sets the bit at position i.
      GF2Polynomial shiftLeft()
      Returns this GF2Polynomial shift-left by 1 in a new GF2Polynomial.
      GF2Polynomial shiftLeft​(int k)
      Returns this GF2Polynomial shift-left by k in a new GF2Polynomial.
      void shiftLeftAddThis​(GF2Polynomial b, int k)
      Shifts left b and adds the result to Its a fast version of this = add(b.shl(k));
      void shiftLeftThis()
      Shifts-left this by one and enlarges the size of value if necesary.
      GF2Polynomial shiftRight()
      Returns this GF2Polynomial shift-right by 1 in a new GF2Polynomial.
      void shiftRightThis()
      Shifts-right this GF2Polynomial by 1.
      void squareThisBitwise()
      Squares this GF2Polynomial and expands it accordingly.
      void squareThisPreCalc()
      Squares this GF2Polynomial by using precomputed values of squaringTable.
      GF2Polynomial subtract​(GF2Polynomial b)
      Subtracts two GF2Polynomials, this and b, and returns the result in a new GF2Polynomial.
      void subtractFromThis​(GF2Polynomial b)
      Subtracts b from this GF2Polynomial and assigns the result to this GF2Polynomial.
      boolean testBit​(int i)
      Tests the bit at position i.
      byte[] toByteArray()
      Converts this polynomial to a byte[] (octet string) according to 1363.
      java.math.BigInteger toFlexiBigInt()
      Converts this polynomial to an integer according to 1363.
      int[] toIntegerArray()
      Returns the value of this GF2Polynomial in an int[].
      java.lang.String toString​(int radix)
      Returns a string representing this GF2Polynomials value using hexadecimal or binary radix in MSB-first order.
      boolean vectorMult​(GF2Polynomial b)
      Does a vector-multiplication modulo 2 and returns the result as boolean.
      GF2Polynomial xor​(GF2Polynomial b)
      Returns the bitwise exclusive-or of this and b in a new GF2Polynomial.
      void xorBit​(int i)
      Xors the bit at position i.
      void xorThisBy​(GF2Polynomial b)
      Computes the bitwise exclusive-or of this GF2Polynomial and b and stores the result in this GF2Polynomial.

      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • GF2Polynomial

        public GF2Polynomial​(int length)
        Creates a new GF2Polynomial of the given length and value zero.
        Parameters:
        length - the desired number of bits to store

      • GF2Polynomial

        public GF2Polynomial​(int length,
                     java.util.Random rand)
        Creates a new GF2Polynomial of the given length and random value.
        Parameters:
        length - the desired number of bits to store
        rand - SecureRandom to use for randomization

      • GF2Polynomial

        public GF2Polynomial​(int length,
                     java.lang.String value)
        Creates a new GF2Polynomial of the given length and value selected by value: ZERO
        • ONE RANDOM X ALL
Parameters:
length - the desired number of bits to store
value - the value described by a String

  • Method Detail

    • clone

      public java.lang.Object clone()
      Overrides:
      clone in class java.lang.Object
      Returns:
      a copy of this GF2Polynomial

    • getLength

      public int getLength()
      Returns the length of this GF2Polynomial. The length can be greater than the degree. To get the degree call reduceN() before calling getLength().
      Returns:
      the length of this GF2Polynomial

    • toIntegerArray

      public int[] toIntegerArray()
      Returns the value of this GF2Polynomial in an int[].
      Returns:
      the value of this GF2Polynomial in a new int[], LSB in int[0]

    • toString

      public java.lang.String toString​(int radix)
      Returns a string representing this GF2Polynomials value using hexadecimal or binary radix in MSB-first order.
      Parameters:
      radix - the radix to use (2 or 16, otherwise 2 is used)
      Returns:
      a String representing this GF2Polynomials value.

    • toByteArray

      public byte[] toByteArray()
      Converts this polynomial to a byte[] (octet string) according to 1363.
      Returns:
      a byte[] representing the value of this polynomial
      See Also:
      "P1363 5.5.2 p22f, BS2OSP"

    • toFlexiBigInt

      public java.math.BigInteger toFlexiBigInt()
      Converts this polynomial to an integer according to 1363.
      Returns:
      a FlexiBigInt representing the value of this polynomial
      See Also:
      "P1363 5.5.1 p22, BS2IP"

    • assignOne

      public void assignOne()
      Sets the LSB to 1 and all other to 0, assigning 'one' to this GF2Polynomial.

    • assignX

      public void assignX()
      Sets Bit 1 to 1 and all other to 0, assigning 'x' to this GF2Polynomial.

    • assignAll

      public void assignAll()
      Sets all Bits to 1.

    • assignZero

      public void assignZero()
      Resets all bits to zero.

    • randomize

      public void randomize()
      Fills all len bits of this GF2Polynomial with random values.

    • randomize

      public void randomize​(java.util.Random rand)
      Fills all len bits of this GF2Polynomial with random values using the specified source of randomness.
      Parameters:
      rand - the source of randomness

    • equals

      public boolean equals​(java.lang.Object other)
      Returns true if two GF2Polynomials have the same size and value and thus are equal.
      Overrides:
      equals in class java.lang.Object
      Parameters:
      other - the other GF2Polynomial
      Returns:
      true if this GF2Polynomial equals b (this == b)

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class java.lang.Object
      Returns:
      the hash code of this polynomial

    • isZero

      public boolean isZero()
      Tests if all bits equal zero.
      Returns:
      true if this GF2Polynomial equals 'zero' (this == 0)

    • isOne

      public boolean isOne()
      Tests if all bits are reset to 0 and LSB is set to 1.
      Returns:
      true if this GF2Polynomial equals 'one' (this == 1)

    • addToThis

      public void addToThis​(GF2Polynomial b)
      Adds b to this GF2Polynomial and assigns the result to this GF2Polynomial. b can be of different size.
      Parameters:
      b - GF2Polynomial to add to this GF2Polynomial

    • add

      public GF2Polynomial add​(GF2Polynomial b)
      Adds two GF2Polynomials, this and b, and returns the result. this and b can be of different size.
      Parameters:
      b - a GF2Polynomial
      Returns:
      a new GF2Polynomial (this + b)

    • subtractFromThis

      public void subtractFromThis​(GF2Polynomial b)
      Subtracts b from this GF2Polynomial and assigns the result to this GF2Polynomial. b can be of different size.
      Parameters:
      b - a GF2Polynomial

    • subtract

      public GF2Polynomial subtract​(GF2Polynomial b)
      Subtracts two GF2Polynomials, this and b, and returns the result in a new GF2Polynomial. this and b can be of different size.
      Parameters:
      b - a GF2Polynomial
      Returns:
      a new GF2Polynomial (this - b)

    • increaseThis

      public void increaseThis()
      Toggles the LSB of this GF2Polynomial, increasing its value by 'one'.

    • increase

      public GF2Polynomial increase()
      Toggles the LSB of this GF2Polynomial, increasing the value by 'one' and returns the result in a new GF2Polynomial.
      Returns:
      this + 1

    • multiplyClassic

      public GF2Polynomial multiplyClassic​(GF2Polynomial b)
      Multiplies this GF2Polynomial with b and returns the result in a new GF2Polynomial. This method does not reduce the result in GF(2^N). This method uses classic multiplication (schoolbook).
      Parameters:
      b - a GF2Polynomial
      Returns:
      a new GF2Polynomial (this * b)

    • multiply

      public GF2Polynomial multiply​(GF2Polynomial b)
      Multiplies this GF2Polynomial with b and returns the result in a new GF2Polynomial. This method does not reduce the result in GF(2^N). This method uses Karatzuba multiplication.
      Parameters:
      b - a GF2Polynomial
      Returns:
      a new GF2Polynomial (this * b)

    • remainder

      public GF2Polynomial remainder​(GF2Polynomial g)
                        throws java.lang.RuntimeException
      Returns the remainder of this divided by g in a new GF2Polynomial.
      Parameters:
      g - GF2Polynomial != 0
      Returns:
      a new GF2Polynomial (this % g)
      Throws:
      java.lang.RuntimeException

    • quotient

      public GF2Polynomial quotient​(GF2Polynomial g)
                       throws java.lang.RuntimeException
      Returns the absolute quotient of this divided by g in a new GF2Polynomial.
      Parameters:
      g - GF2Polynomial != 0
      Returns:
      a new GF2Polynomial |_ this / g _|
      Throws:
      java.lang.RuntimeException

    • divide

      public GF2Polynomial[] divide​(GF2Polynomial g)
                       throws java.lang.RuntimeException
      Divides this by g and returns the quotient and remainder in a new GF2Polynomial[2], quotient in [0], remainder in [1].
      Parameters:
      g - GF2Polynomial != 0
      Returns:
      a new GF2Polynomial[2] containing quotient and remainder
      Throws:
      java.lang.RuntimeException

    • gcd

      public GF2Polynomial gcd​(GF2Polynomial g)
                  throws java.lang.RuntimeException
      Returns the greatest common divisor of this and g in a new GF2Polynomial.
      Parameters:
      g - GF2Polynomial != 0
      Returns:
      a new GF2Polynomial gcd(this,g)
      Throws:
      java.lang.ArithmeticException - if this and g both are equal to zero
      java.lang.RuntimeException

    • isIrreducible

      public boolean isIrreducible()
      Checks if this is irreducible, according to IEEE P1363, A.5.5, p103. Note: The algorithm from IEEE P1363, A5.5 can be used to check a polynomial with coefficients in GF(2^r) for irreducibility. As this class only represents polynomials with coefficients in GF(2), the algorithm is adapted to the case r=1.
      Returns:
      true if this is irreducible
      See Also:
      "P1363, A.5.5, p103"

    • reduceN

      public void reduceN()
      Reduces len by finding the most significant bit set to one and reducing len and blocks.

    • expandN

      public void expandN​(int i)
      Expands len and int[] value to i. This is useful before adding two GF2Polynomials of different size.
      Parameters:
      i - the intended length

    • squareThisBitwise

      public void squareThisBitwise()
      Squares this GF2Polynomial and expands it accordingly. This method does not reduce the result in GF(2^N). There exists a faster method for squaring in GF(2^N).
      See Also:
      GF2nPolynomialElement.square()

    • squareThisPreCalc

      public void squareThisPreCalc()
      Squares this GF2Polynomial by using precomputed values of squaringTable. This method does not reduce the result in GF(2^N).

    • vectorMult

      public boolean vectorMult​(GF2Polynomial b)
                   throws java.lang.RuntimeException
      Does a vector-multiplication modulo 2 and returns the result as boolean.
      Parameters:
      b - GF2Polynomial
      Returns:
      this x b as boolean (1->true, 0->false)
      Throws:
      java.lang.RuntimeException

    • xor

      public GF2Polynomial xor​(GF2Polynomial b)
      Returns the bitwise exclusive-or of this and b in a new GF2Polynomial. this and b can be of different size.
      Parameters:
      b - GF2Polynomial
      Returns:
      a new GF2Polynomial (this ^ b)

    • xorThisBy

      public void xorThisBy​(GF2Polynomial b)
      Computes the bitwise exclusive-or of this GF2Polynomial and b and stores the result in this GF2Polynomial. b can be of different size.
      Parameters:
      b - GF2Polynomial

    • setBit

      public void setBit​(int i)
            throws java.lang.RuntimeException
      Sets the bit at position i.
      Parameters:
      i - int
      Throws:
      java.lang.RuntimeException - if (i < 0) || (i > (len - 1))

    • getBit

      public int getBit​(int i)
      Returns the bit at position i.
      Parameters:
      i - int
      Returns:
      the bit at position i if i is a valid position, 0 otherwise.

    • resetBit

      public void resetBit​(int i)
              throws java.lang.RuntimeException
      Resets the bit at position i.
      Parameters:
      i - int
      Throws:
      java.lang.RuntimeException - if (i < 0) || (i > (len - 1))

    • xorBit

      public void xorBit​(int i)
            throws java.lang.RuntimeException
      Xors the bit at position i.
      Parameters:
      i - int
      Throws:
      java.lang.RuntimeException - if (i < 0) || (i > (len - 1))

    • testBit

      public boolean testBit​(int i)
      Tests the bit at position i.
      Parameters:
      i - the position of the bit to be tested
      Returns:
      true if the bit at position i is set (a(i) == 1). False if (i < 0) || (i > (len - 1))

    • shiftLeft

      public GF2Polynomial shiftLeft()
      Returns this GF2Polynomial shift-left by 1 in a new GF2Polynomial.
      Returns:
      a new GF2Polynomial (this << 1)

    • shiftLeftThis

      public void shiftLeftThis()
      Shifts-left this by one and enlarges the size of value if necesary.

    • shiftLeft

      public GF2Polynomial shiftLeft​(int k)
      Returns this GF2Polynomial shift-left by k in a new GF2Polynomial.
      Parameters:
      k - int
      Returns:
      a new GF2Polynomial (this << k)

    • shiftLeftAddThis

      public void shiftLeftAddThis​(GF2Polynomial b,
                             int k)
      Shifts left b and adds the result to Its a fast version of this = add(b.shl(k));
      Parameters:
      b - GF2Polynomial to shift and add to this
      k - the amount to shift
      See Also:
      GF2nPolynomialElement.invertEEA()

    • shiftRight

      public GF2Polynomial shiftRight()
      Returns this GF2Polynomial shift-right by 1 in a new GF2Polynomial.
      Returns:
      a new GF2Polynomial (this << 1)

    • shiftRightThis

      public void shiftRightThis()
      Shifts-right this GF2Polynomial by 1.