public class IntegerPolynomial extends Object implements Polynomial
int
coefficients.add
) change the polynomial, others (like mult
) do
not but return the result as a new polynomial.Modifier and Type | Field and Description |
---|---|
int[] |
coeffs |
Constructor and Description |
---|
IntegerPolynomial(BigIntPolynomial p)
Constructs a
IntegerPolynomial from a BigIntPolynomial . |
IntegerPolynomial(int N)
Constructs a new polynomial with
N coefficients initialized to 0. |
IntegerPolynomial(int[] coeffs)
Constructs a new polynomial with a given set of coefficients.
|
Modifier and Type | Method and Description |
---|---|
void |
add(IntegerPolynomial b)
Adds another polynomial which can have a different number of coefficients.
|
void |
add(IntegerPolynomial b,
int modulus)
Adds another polynomial which can have a different number of coefficients,
and takes the coefficient values mod
modulus . |
void |
center0(int q)
Shifts the values of all coefficients to the interval
[-q/2, q/2] . |
long |
centeredNormSq(int q)
Computes the centered euclidean norm of the polynomial.
|
void |
clear() |
Object |
clone() |
int |
count(int value)
Counts the number of coefficients equal to an integer
|
void |
div(int k)
Divides each coefficient by
k and rounds to the nearest integer. |
void |
ensurePositive(int modulus)
Adds
modulus until all coefficients are above 0. |
boolean |
equals(Object obj) |
boolean |
equalsOne()
Tests if
p(x) = 1 . |
static IntegerPolynomial |
fromBinary(byte[] data,
int N,
int q)
Returns a polynomial with N coefficients between
0 and q-1 .q must be a power of 2.Ignores any excess bytes. |
static IntegerPolynomial |
fromBinary(InputStream is,
int N,
int q)
Returns a polynomial with N coefficients between
0 and q-1 .q must be a power of 2.Ignores any excess bytes. |
static IntegerPolynomial |
fromBinary3Sves(byte[] data,
int N)
Decodes a byte array to a polynomial with
N ternary coefficientsIgnores any excess bytes. |
static IntegerPolynomial |
fromBinary3Tight(byte[] b,
int N)
Converts a byte array produced by
toBinary3Tight() to a polynomial. |
static IntegerPolynomial |
fromBinary3Tight(InputStream is,
int N)
Reads data produced by
toBinary3Tight() from an input stream and converts it to a polynomial. |
IntegerPolynomial |
invertF3()
Computes the inverse mod 3.
|
IntegerPolynomial |
invertFq(int q)
Computes the inverse mod
q; q must be a power of 2.Returns null if the polynomial is not invertible. |
void |
mod(int modulus)
Takes each coefficient modulo
modulus . |
void |
mod3()
Takes each coefficient modulo 3 such that all coefficients are ternary.
|
void |
modPositive(int modulus)
Ensures all coefficients are between 0 and
modulus-1 |
BigIntPolynomial |
mult(BigIntPolynomial poly2)
Multiplies the polynomial by a
BigIntPolynomial , taking the indices mod N. |
void |
mult(int factor)
Multiplies each coefficient by a
int . |
IntegerPolynomial |
mult(IntegerPolynomial poly2)
Multiplies the polynomial with another, taking the indices mod N
|
IntegerPolynomial |
mult(IntegerPolynomial poly2,
int modulus)
Multiplies the polynomial with another, taking the values mod modulus and the indices mod N
|
void |
mult3(int modulus)
Multiplies each coefficient by a 2 and applies a modulus.
|
Resultant |
resultant()
Resultant of this polynomial with
x^n-1 using a probabilistic algorithm. |
ModularResultant |
resultant(int p)
Resultant of this polynomial with
x^n-1 mod p . |
Resultant |
resultantMultiThread()
Multithreaded version of
resultant() . |
void |
rotate1()
Multiplication by
X in Z[X]/Z[X^n-1] . |
void |
sub(IntegerPolynomial b)
Subtracts another polynomial which can have a different number of coefficients.
|
void |
sub(IntegerPolynomial b,
int modulus)
Subtracts another polynomial which can have a different number of coefficients,
and takes the coefficient values mod
modulus . |
int |
sumCoeffs()
Returns the sum of all coefficients, i.e.
|
byte[] |
toBinary(int q)
Encodes a polynomial whose coefficients are between 0 and q, to binary.
|
byte[] |
toBinary3Sves()
Encodes a polynomial with ternary coefficients to binary.
|
byte[] |
toBinary3Tight()
Converts a polynomial with ternary coefficients to binary.
|
IntegerPolynomial |
toIntegerPolynomial()
Returns a polynomial that is equal to this polynomial (in the sense that
Polynomial.mult(IntegerPolynomial, int)
returns equal IntegerPolynomial s). |
public IntegerPolynomial(int N)
N
coefficients initialized to 0.N
- the number of coefficientspublic IntegerPolynomial(int[] coeffs)
coeffs
- the coefficientspublic IntegerPolynomial(BigIntPolynomial p)
IntegerPolynomial
from a BigIntPolynomial
. The two polynomials are independent of each other.p
- the original polynomialpublic static IntegerPolynomial fromBinary3Sves(byte[] data, int N)
N
ternary coefficientsdata
- an encoded ternary polynomialN
- number of coefficientspublic static IntegerPolynomial fromBinary3Tight(byte[] b, int N)
toBinary3Tight()
to a polynomial.b
- a byte arrayN
- number of coefficientspublic static IntegerPolynomial fromBinary3Tight(InputStream is, int N) throws IOException
toBinary3Tight()
from an input stream and converts it to a polynomial.is
- an input streamN
- number of coefficientsIOException
public static IntegerPolynomial fromBinary(byte[] data, int N, int q)
0
and q-1
.q
must be a power of 2.data
- an encoded ternary polynomialN
- number of coefficientsq
- public static IntegerPolynomial fromBinary(InputStream is, int N, int q) throws IOException
0
and q-1
.q
must be a power of 2.is
- an encoded ternary polynomialN
- number of coefficientsq
- IOException
public byte[] toBinary3Sves()
coeffs[2*i]
and coeffs[2*i+1]
must not both equal -1 for any integer i
,
so this method is only safe to use with polynomials produced by fromBinary3Sves()
.public byte[] toBinary3Tight()
public byte[] toBinary(int q)
q
- public IntegerPolynomial mult(IntegerPolynomial poly2, int modulus)
mult
in interface Polynomial
poly2
- a polynomialmodulus
- a modulus to applypublic IntegerPolynomial mult(IntegerPolynomial poly2)
mult
in interface Polynomial
poly2
- a polynomialpublic BigIntPolynomial mult(BigIntPolynomial poly2)
Polynomial
BigIntPolynomial
, taking the indices mod N. Does not
change this polynomial but returns the result as a new polynomial.mult
in interface Polynomial
poly2
- the polynomial to multiply bypublic IntegerPolynomial invertFq(int q)
q; q
must be a power of 2.null
if the polynomial is not invertible.q
- the moduluspublic IntegerPolynomial invertF3()
null
if the polynomial is not invertible.public Resultant resultant()
x^n-1
using a probabilistic algorithm.
Unlike EESS, this implementation does not compute all resultants modulo primes
such that their product exceeds the maximum possible resultant, but rather stops
when NUM_EQUAL_RESULTANTS
consecutive modular resultants are equal.
This means the return value may be incorrect. Experiments show this happens in
about 1 out of 100 cases when N=439
and NUM_EQUAL_RESULTANTS=2
,
so the likelyhood of leaving the loop too early is (1/100)^(NUM_EQUAL_RESULTANTS-1)
.
Because of the above, callers must verify the output and try a different polynomial if necessary.
(rho, res)
satisfying res = rho*this + t*(x^n-1)
for some integer t
.public Resultant resultantMultiThread()
resultant()
.(rho, res)
satisfying res = rho*this + t*(x^n-1)
for some integer t
.public ModularResultant resultant(int p)
x^n-1 mod p
.(rho, res)
satisfying res = rho*this + t*(x^n-1) mod p
for some integer t
.public void add(IntegerPolynomial b, int modulus)
modulus
.b
- another polynomialpublic void add(IntegerPolynomial b)
b
- another polynomialpublic void sub(IntegerPolynomial b, int modulus)
modulus
.b
- another polynomialpublic void sub(IntegerPolynomial b)
b
- another polynomialpublic void mult(int factor)
int
. Does not return a new polynomial but modifies this polynomial.factor
- public void mult3(int modulus)
modulus
- a moduluspublic void div(int k)
k
and rounds to the nearest integer. Does not return a new polynomial but modifies this polynomial.k
- the divisorpublic void mod3()
public void modPositive(int modulus)
modulus-1
modulus
- a moduluspublic void mod(int modulus)
modulus
.public void ensurePositive(int modulus)
modulus
until all coefficients are above 0.modulus
- a moduluspublic long centeredNormSq(int q)
q
- a moduluspublic void center0(int q)
[-q/2, q/2]
.q
- a moduluspublic int sumCoeffs()
public boolean equalsOne()
p(x) = 1
.public int count(int value)
value
- an integervalue
public void rotate1()
X
in Z[X]/Z[X^n-1]
.public void clear()
public IntegerPolynomial toIntegerPolynomial()
Polynomial
Polynomial.mult(IntegerPolynomial, int)
returns equal IntegerPolynomial
s). The new polynomial is guaranteed to be independent of the original.toIntegerPolynomial
in interface Polynomial
IntegerPolynomial
.Copyright © 2020 BouncyCastle.org. All rights reserved.