Class GF2Polynomial
java.lang.Object
org.bouncycastle.pqc.legacy.math.linearalgebra.GF2Polynomial
This class stores very long strings of bits and does some basic arithmetics.
It is used by GF2nField, GF2nPolynomialField and
GFnPolynomialElement.
- See Also:
-
Constructor Summary
ConstructorDescriptionGF2Polynomial
(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, String value) Creates a new GF2Polynomial of the given length and value selected by value: ZERO ONE RANDOM X ALLGF2Polynomial
(int length, BigInteger bi) Creates a new GF2Polynomial by converting the given FlexiBigInt bi according to 1363 and using the given length.GF2Polynomial
(int length, Random rand) Creates a new GF2Polynomial of the given length and random value.Creates a new GF2Polynomial by cloneing the given GF2Polynomial b. -
Method Summary
Modifier and TypeMethodDescriptionadd
(GF2Polynomial b) Adds two GF2Polynomials, this and b, and returns the result.void
Adds b to this GF2Polynomial and assigns the result to this GF2Polynomial.void
Sets all Bits to 1.void
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
Resets all bits to zero.clone()
Divides this by g and returns the quotient and remainder in a new GF2Polynomial[2], quotient in [0], remainder in [1].boolean
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.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
Returns the length of this GF2Polynomial.int
hashCode()
increase()
Toggles the LSB of this GF2Polynomial, increasing the value by 'one' and returns the result in a new GF2Polynomial.void
Toggles the LSB of this GF2Polynomial, increasing its value by 'one'.boolean
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.Multiplies this GF2Polynomial with b and returns the result in a new GF2Polynomial.Multiplies this GF2Polynomial with b and returns the result in a new GF2Polynomial.Returns the absolute quotient of this divided by g in a new GF2Polynomial.void
Fills all len bits of this GF2Polynomial with random values.void
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.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.Returns this GF2Polynomial shift-left by 1 in a new 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
Shifts-left this by one and enlarges the size of value if necesary.Returns this GF2Polynomial shift-right by 1 in a new GF2Polynomial.void
Shifts-right this GF2Polynomial by 1.void
Squares this GF2Polynomial and expands it accordingly.void
Squares this GF2Polynomial by using precomputed values of squaringTable.Subtracts two GF2Polynomials, this and b, and returns the result in a new GF2Polynomial.void
Subtracts b from this GF2Polynomial and assigns the result to this GF2Polynomial.boolean
testBit
(int i) Tests the bit at position i.byte[]
Converts this polynomial to a byte[] (octet string) according to 1363.Converts this polynomial to an integer according to 1363.int[]
Returns the value of this GF2Polynomial in an int[].toString
(int radix) Returns a string representing this GF2Polynomials value using hexadecimal or binary radix in MSB-first order.boolean
Does a vector-multiplication modulo 2 and returns the result as boolean.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
Computes the bitwise exclusive-or of this GF2Polynomial and b and stores the result in this GF2Polynomial.
-
Constructor Details
-
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
Creates a new GF2Polynomial of the given length and random value.- Parameters:
length
- the desired number of bits to storerand
- SecureRandom to use for randomization
-
GF2Polynomial
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 storevalue
- 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 storebs
- 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 polynomialos
- the octet string to assign to this polynomial- See Also:
-
GF2Polynomial
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 polynomialbi
- the FlexiBigInt to assign to this polynomial- See Also:
-
GF2Polynomial
Creates a new GF2Polynomial by cloneing the given GF2Polynomial b.- Parameters:
b
- the GF2Polynomial to clone
-
-
Method Details
-
clone
-
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
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:
-
toFlexiBigInt
Converts this polynomial to an integer according to 1363.- Returns:
- a FlexiBigInt representing the value of this polynomial
- See Also:
-
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
Fills all len bits of this GF2Polynomial with random values using the specified source of randomness.- Parameters:
rand
- the source of randomness
-
equals
Returns true if two GF2Polynomials have the same size and value and thus are equal. -
hashCode
public int hashCode() -
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
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
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
Subtracts b from this GF2Polynomial and assigns the result to this GF2Polynomial. b can be of different size.- Parameters:
b
- a GF2Polynomial
-
subtract
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
Toggles the LSB of this GF2Polynomial, increasing the value by 'one' and returns the result in a new GF2Polynomial.- Returns:
- this + 1
-
multiplyClassic
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
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
Returns the remainder of this divided by g in a new GF2Polynomial.- Parameters:
g
- GF2Polynomial != 0- Returns:
- a new GF2Polynomial (this % g)
- Throws:
RuntimeException
-
quotient
Returns the absolute quotient of this divided by g in a new GF2Polynomial.- Parameters:
g
- GF2Polynomial != 0- Returns:
- a new GF2Polynomial |_ this / g _|
- Throws:
RuntimeException
-
divide
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:
RuntimeException
-
gcd
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:
ArithmeticException
- if this and g both are equal to zeroRuntimeException
-
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:
-
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:
-
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
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:
RuntimeException
-
xor
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
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
Sets the bit at position i.- Parameters:
i
- int- Throws:
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
Resets the bit at position i.- Parameters:
i
- int- Throws:
RuntimeException
- if (i < 0) || (i > (len - 1))
-
xorBit
Xors the bit at position i.- Parameters:
i
- int- Throws:
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
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
Returns this GF2Polynomial shift-left by k in a new GF2Polynomial.- Parameters:
k
- int- Returns:
- a new GF2Polynomial (this << k)
-
shiftLeftAddThis
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 thisk
- the amount to shift- See Also:
-
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.
-