public class IntegerPolynomial extends java.lang.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() |
java.lang.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(java.lang.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(java.io.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(java.io.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(java.io.InputStream is, int N) throws java.io.IOException
toBinary3Tight()
from an input stream and converts it to a polynomial.is
- an input streamN
- number of coefficientsjava.io.IOException
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(java.io.InputStream is, int N, int q) throws java.io.IOException
0
and q-1
.q
must be a power of 2.is
- an encoded ternary polynomialN
- number of coefficientsq
- java.io.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
.public java.lang.Object clone()
clone
in class java.lang.Object
public boolean equals(java.lang.Object obj)
equals
in class java.lang.Object