Package org.bouncycastle.pqc.math.linearalgebra

## Class GF2Polynomial

- java.lang.Object
- - org.bouncycastle.pqc.math.linearalgebra.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. Note: The algorithm from IEEE P1363, A5.5 can be used to check a polynomial with coefficients in GF(2^r) for irreducibility.
    `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

    - #### GF2Polynomial

          public GF2Polynomial​(int length,
                               int[] bs)

      Creates a new GF2Polynomial of the given length using the given int[]. LSB is contained in bs[0].
      Parameters:
        `length` - the desired number of bits to store
        `bs` - contains the desired value, LSB in bs[0]

    - #### GF2Polynomial

          public GF2Polynomial​(int length,
                               byte[] os)

      Creates a new GF2Polynomial by converting the given byte[] os according to 1363 and using the given length.
      Parameters:
        `length` - the intended length of this polynomial
        `os` - the octet string to assign to this polynomial
      See Also:
        "P1363 5.5.2 p22f, OS2BSP"

    - #### GF2Polynomial

          public 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.
      Parameters:
        `length` - the intended length of this polynomial
        `bi` - the FlexiBigInt to assign to this polynomial
      See Also:
        "P1363 5.5.1 p22, I2BSP"

    - #### GF2Polynomial

          public GF2Polynomial​(GF2Polynomial b)

      Creates a new GF2Polynomial by cloneing the given GF2Polynomial b.
      Parameters:
        `b` - the GF2Polynomial to clone

  - ### 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.