de.flexiprovider.common.math.polynomials
Class ModQConvolutionPolynomial

java.lang.Object
  |
  +--de.flexiprovider.common.math.polynomials.ModQConvolutionPolynomial

All Implemented Interfaces:

ConvolutionPolynomial

public class ModQConvolutionPolynomial

extends java.lang.Object

implements ConvolutionPolynomial

This class implements convolution polynomials in the ring (Z/qZ)/(X^N-1) and their arithmetic , where q and N lie in the interval [2, Integer.MAX_VALUE].

Author:

Martin Döring

Constructor Summary

ModQConvolutionPolynomial(int N, int q)
Construct the default polynomial (the zero polynomial f(x) = 0).

ModQConvolutionPolynomial(int N, int q, int[] coefficients)
Construct a polynomial out of the given coefficient array.

ModQConvolutionPolynomial(int N, int q, int degree, int headCoef)
Construct a polynomial of the given degree.

ModQConvolutionPolynomial(ModQConvolutionPolynomial other)
Copy constructor

ModQConvolutionPolynomial(SparseBinaryConvolutionPolynomial other, int q, int p)
Construct a full form polynomial out of the given sparse binary polynomial, setting the non-zero coefficients to an integer p.

Method Summary

ModQConvolutionPolynomial	add(ModQConvolutionPolynomial addend) Add the addend to this polynomial.
void	addThis(ModQConvolutionPolynomial addend) Add the addend to this polynomial (overwriting this polynomial).
byte[]	BRE2OSP() Encode a binary ring element as a byte array.
boolean	equals(java.lang.Object other) Compare this polynomial with the given object.
int	evaluateAtOne() Evaluate this polynomial at value 1.
int	hashCode()
ModQConvolutionPolynomial	invert() Compute the inverse of this polynomial in the ring (Z/qZ)[X]/(X^N-1).
ModQConvolutionPolynomial	multiply(ConvolutionPolynomial factor) Adapter method: multiply this polynomial with the factor.
ModQConvolutionPolynomial	multiply(ModQConvolutionPolynomial factor) Multiply this polynomial with the factor.
ModQConvolutionPolynomial	multiply(ProductFormConvolutionPolynomial factor) Multiply this polynomial with the factor and reduce the result modulo X^N-1.
ModQConvolutionPolynomial	multiply(SparseBinaryConvolutionPolynomial factor) Multiply this polynomial with the factor and reduce the result modulo X^N-1.
ModQConvolutionPolynomial	multiplyInteger(int a) Multiply this polynomial with an integer.
void	multiplyIntegerThis(int a) Multiply this polynomial with an integer.
ModQConvolutionPolynomial	multiplyPatterns(ProductFormConvolutionPolynomial factor) Multiply this polynomial with a ProductFormConvolutionPolynomial making use of bit patterns of the three binary polynomials constituting the product form polynomial.
ModQConvolutionPolynomial	multiplyPatterns(SparseBinaryConvolutionPolynomial factor) Multiply this polynomial with a SparseBinaryConvolutionPolynomial making use of bit patterns of the binary polynomial.
ModQConvolutionPolynomial	multiplySlidingWindow(BinaryConvolutionPolynomial factor) Multiply this polynomial with the factor according to Algorithm 3 of M.-K.
ModQConvolutionPolynomial	multiplySlidingWindow(SparseBinaryConvolutionPolynomial factor) Multiply this polynomial with the factor according to Algorithm 3 of M.-K.
void	multiplyThis(ModQConvolutionPolynomial factor) Multiply this polynomial with the factor (overwriting this polynomial).
static ModQConvolutionPolynomial	OS2BREP(int N, int q, byte[] encoded) Decode a byte array into a binary polynomial.
static ModQConvolutionPolynomial	OS2REP(int N, int q, byte[] encoded) Decode a byte array into a polynomial.
byte[]	RE2OSP() Encode this polynomial as a byte array if it is an element of (Z/qZ)/(X^N-1).
ModQConvolutionPolynomial	reduceCoeffModP(int p) Reduce the coefficients of this polynomial modulo an integer p into the interval [0, p).
void	reduceCoeffModPThis(int p) Reduce the coefficients of this polynomial modulo an integer p into the interval [0, p), overwriting this polynomial.
void	shiftCoeffThis(int A) Shift the coefficients of this polynomial by an integer A.
ModQConvolutionPolynomial	subtract(ModQConvolutionPolynomial minuend) Subtract the minuend from this polynomial.
void	subtractThis(ModQConvolutionPolynomial minuend) Subtract the minuend from this polynomial (overwriting this polynomial).
java.lang.String	toString()

Methods inherited from class java.lang.Object

, clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

ModQConvolutionPolynomial

public ModQConvolutionPolynomial(int N,
                                 int q)
                          throws java.lang.IllegalArgumentException

Construct the default polynomial (the zero polynomial f(x) = 0).

Parameters:

N - the degree of the reduction polynomial

q - the modulus

Throws:

java.lang.IllegalArgumentException - if the parameters are invalid.

ModQConvolutionPolynomial

public ModQConvolutionPolynomial(int N,
                                 int q,
                                 int degree,
                                 int headCoef)
                          throws java.lang.IllegalArgumentException

Construct a polynomial of the given degree. The only non-zero coefficient will be the head coefficient which is set to headCoef.

Parameters:

N - the degree of the reduction polynomial

q - the modulus

degree - the degree

headCoef - the head coefficient

Throws:

java.lang.IllegalArgumentException - if the parameters are invalid.

ModQConvolutionPolynomial

public ModQConvolutionPolynomial(int N,
                                 int q,
                                 int[] coefficients)
                          throws java.lang.IllegalArgumentException

Construct a polynomial out of the given coefficient array. The coefficients are reduced modulo q into the interval [0, q)..

Parameters:

N - the degree of the reduction polynomial

q - the modulus

coefficients - the coefficient array

Throws:

java.lang.IllegalArgumentException - if the parameters are invalid.

ModQConvolutionPolynomial

public ModQConvolutionPolynomial(SparseBinaryConvolutionPolynomial other,
                                 int q,
                                 int p)

Construct a full form polynomial out of the given sparse binary polynomial, setting the non-zero coefficients to an integer p.

Parameters:

other - the sparse binary polynomial

q - the modulus

p - the value of the non-zero coefficients

ModQConvolutionPolynomial

public ModQConvolutionPolynomial(ModQConvolutionPolynomial other)

Copy constructor

Parameters:

other - another ModQPolynomial

Method Detail

add

public ModQConvolutionPolynomial add(ModQConvolutionPolynomial addend)

Add the addend to this polynomial.

Parameters:

addend - the addend

Returns:

this + addend (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

addThis

public void addThis(ModQConvolutionPolynomial addend)

Add the addend to this polynomial (overwriting this polynomial).

Parameters:

addend - the addend

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

subtract

public ModQConvolutionPolynomial subtract(ModQConvolutionPolynomial minuend)

Subtract the minuend from this polynomial.

Parameters:

minuend - the minuend

Returns:

this - minuend (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

subtractThis

public void subtractThis(ModQConvolutionPolynomial minuend)

Subtract the minuend from this polynomial (overwriting this polynomial).

Parameters:

minuend - the minuend

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiplyInteger

public ModQConvolutionPolynomial multiplyInteger(int a)

Multiply this polynomial with an integer.

Parameters:

a - the integer

Returns:

this * a (newly created)

multiplyIntegerThis

public void multiplyIntegerThis(int a)

Multiply this polynomial with an integer.

Parameters:

a - the integer

multiply

public ModQConvolutionPolynomial multiply(ConvolutionPolynomial factor)
                                   throws java.lang.ArithmeticException

Adapter method: multiply this polynomial with the factor.

Parameters:

factor - the factor

Returns:

this * factor (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring or if the type of the factor is unknown.

multiply

public ModQConvolutionPolynomial multiply(SparseBinaryConvolutionPolynomial factor)

Multiply this polynomial with the factor and reduce the result modulo X^N-1. This algorithm is described in IEEE P1363.1-D9, Section 6.2.5, Algorithm 1.

Parameters:

factor - the factor

Returns:

this * factor mod X^N-1 (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiply

public ModQConvolutionPolynomial multiply(ProductFormConvolutionPolynomial factor)

Multiply this polynomial with the factor and reduce the result modulo X^N-1. This algorithm is described in IEEE P1363.1-D9, Section 6.2.6, Algorithm 2.

Parameters:

factor - the factor

Returns:

this * factor mod X^N-1 (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiply

public ModQConvolutionPolynomial multiply(ModQConvolutionPolynomial factor)
                                   throws java.lang.ArithmeticException

Multiply this polynomial with the factor.

Parameters:

factor - the factor

Returns:

this * factor (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiplyThis

public void multiplyThis(ModQConvolutionPolynomial factor)
                  throws java.lang.ArithmeticException

Multiply this polynomial with the factor (overwriting this polynomial).

Parameters:

factor - the factor

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiplySlidingWindow

public ModQConvolutionPolynomial multiplySlidingWindow(BinaryConvolutionPolynomial factor)
                                                throws java.lang.ArithmeticException

Multiply this polynomial with the factor according to Algorithm 3 of M.-K. Lee, J. W. Kim, J. E. Song, and K. Park, "Sliding Window Method for NTRU", LNCS 4521.

Parameters:

factor - the factor

Returns:

this * factor (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiplySlidingWindow

public ModQConvolutionPolynomial multiplySlidingWindow(SparseBinaryConvolutionPolynomial factor)
                                                throws java.lang.ArithmeticException

Multiply this polynomial with the factor according to Algorithm 3 of M.-K. Lee, J. W. Kim, J. E. Song, and K. Park, "Sliding Window Method for NTRU", LNCS 4521.

Parameters:

factor - the factor

Returns:

this * factor (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiplyPatterns

public ModQConvolutionPolynomial multiplyPatterns(SparseBinaryConvolutionPolynomial factor)
                                           throws java.lang.ArithmeticException

Multiply this polynomial with a SparseBinaryConvolutionPolynomial making use of bit patterns of the binary polynomial.

Parameters:

factor - the factor

Returns:

this * factor (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

multiplyPatterns

public ModQConvolutionPolynomial multiplyPatterns(ProductFormConvolutionPolynomial factor)
                                           throws java.lang.ArithmeticException

Multiply this polynomial with a ProductFormConvolutionPolynomial making use of bit patterns of the three binary polynomials constituting the product form polynomial.

Parameters:

factor - the factor

Returns:

this * factor (newly created)

Throws:

java.lang.ArithmeticException - if this polynomial and the factor are not elements of the same ring.

invert

public ModQConvolutionPolynomial invert()

Compute the inverse of this polynomial in the ring (Z/qZ)[X]/(X^N-1).

Returns:

the inverse of this polynomial if it is invertible, null otherwise.

reduceCoeffModP

public ModQConvolutionPolynomial reduceCoeffModP(int p)

Reduce the coefficients of this polynomial modulo an integer p into the interval [0, p).

Parameters:

p - the modulus

Returns:

this polynomial with reduced coefficients (newly created)

reduceCoeffModPThis

public void reduceCoeffModPThis(int p)

Reduce the coefficients of this polynomial modulo an integer p into the interval [0, p), overwriting this polynomial.

Parameters:

p - the modulus

shiftCoeffThis

public void shiftCoeffThis(int A)

Shift the coefficients of this polynomial by an integer A.

Parameters:

A - the shift

evaluateAtOne

public int evaluateAtOne()

Evaluate this polynomial at value 1.

Returns:

this(1) mod q

RE2OSP

public byte[] RE2OSP()

Encode this polynomial as a byte array if it is an element of (Z/qZ)/(X^N-1). This method corresponds to the RE2OSP primitive of IEEE P1363.1-D9.

Returns:

the encoded polynomial

OS2REP

public static ModQConvolutionPolynomial OS2REP(int N,
                                               int q,
                                               byte[] encoded)
                                        throws java.lang.IllegalArgumentException

Decode a byte array into a polynomial. This method corresponds to the OS2REP primitive of IEEE P1363.1-D9.

Parameters:

N - the degree of the reduction polynomial

q - the modulus

encoded - the encoded polynomial

Returns:

the decoded polynomial

Throws:

java.lang.IllegalArgumentException - if the encoded polynomial has the wrong length.

BRE2OSP

public byte[] BRE2OSP()
               throws java.lang.ArithmeticException

Encode a binary ring element as a byte array.

Returns:

the encoded polynomial

Throws:

java.lang.ArithmeticException - if this polynomial is not a binary polynomial.

OS2BREP

public static ModQConvolutionPolynomial OS2BREP(int N,
                                                int q,
                                                byte[] encoded)
                                         throws java.lang.IllegalArgumentException

Decode a byte array into a binary polynomial. This method corresponds to the OS2BREP primitive of IEEE P1363.1-D9.

Parameters:

N - the degree of the reduction polynomial

q - the modulus

encoded - the encoded binary polynomial

Returns:

the decoded polynomial

Throws:

java.lang.IllegalArgumentException - if the encoded polynomial has the wrong length.

equals

public boolean equals(java.lang.Object other)

Compare this polynomial with the given object.

Overrides:

equals in class java.lang.Object

Parameters:

other - the other object

Returns:

the result of the comparison

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

Returns:

the hash code of this polynomial

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

Returns:

a human readable form of the polynomial