org.bouncycastle.pqc.legacy.math.linearalgebra
Class GF2Polynomial

java.lang.Object
  |
  +--org.bouncycastle.pqc.legacy.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

GF2Polynomial(GF2Polynomial b)
Creates a new GF2Polynomial by cloneing the given GF2Polynomial b.

GF2Polynomial(int length)
Creates a new GF2Polynomial of the given length and value zero.

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, 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.util.Random rand)
Creates a new GF2Polynomial of the given length and random value.

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

Method Summary

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

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)

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 _|

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

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

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)

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.