Polynomial module

Class for integer polynomial ring

pqlattice.polynomial.ModIntPolyRing

ModIntPolyRing(modulus: int)

Construct the polynomial ring over coefficients from integer quotient ring with given modulus.

Parameters:

Name	Type	Description	Default
modulus	int	integer quotient ring modulus	required

Raises:

Type	Description
ValueError	If the modulus is less than 2

add

add(polynomial_a: Vector, polynomial_b: Vector) -> Vector

Adds two polynomials

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

coprime

coprime(polynomial_a: Vector, polynomial_b: Vector) -> bool

Checks if two polynomials are coprime, that is if their gcd == 1

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
bool	True if coprime, False otherwise

deg

deg(polynomial: Vector) -> int

Returns degree of the given polynomial

Parameters:

Name	Type	Description	Default
polynomial	Vector		required

Returns:

Type	Description
int	degree

eea

eea(
    polynomial_a: Vector, polynomial_b: Vector
) -> tuple[Vector, Vector, Vector]

Extended Euclidean algorithm for the polynomials.

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
tuple[Vector, Vector, Vector]	tuple[s, t, gcd] such that polynomial_a * s + polynomial_b * t == gcd

euclidean_div

euclidean_div(
    polynomial_a: Vector, polynomial_b: Vector
) -> tuple[Vector, Vector]

Performs the euclidean division for the polynomials

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
tuple[Vector, Vector]	tuple[q, r] such that polynomial_a == q * polynomial_b + r

Raises:

Type	Description
ZeroDivisionError	If the polynomial_b is the zero polynomial

gcd

gcd(polynomial_a: Vector, polynomial_b: Vector) -> Vector

Computes the polynomial that is the greates common divisor of the given polynomials

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

is_zero

is_zero(polynomial: Vector) -> bool

Checks if the polynomial is the zero polynomial in the ring.

Parameters:

Name	Type	Description	Default
polynomial	Vector		required

Returns:

Type	Description
bool	True if it is zero polynomial, False otherwise

mul

mul(polynomial_a: Vector, polynomial_b: Vector) -> Vector

multiplies two polynomials

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

reduce

reduce(polynomial: Vector) -> Vector

Reduces the polynomials coefficients according to the ring, that is modulo self.modulus

Parameters:

Name	Type	Description	Default
polynomial	Vector		required

Returns:

Type	Description
Vector	polynomial with coefficients from range [0, self.modulus)

rem

rem(polynomial_a: Vector, polynomial_b: Vector) -> Vector

Returns remainder of the euclidean division

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

sub

sub(polynomial_a: Vector, polynomial_b: Vector) -> Vector

Subtract one polynomial from the other

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

to_monic

to_monic(polynomial: Vector) -> Vector

Transformt the given polynomial to its monic form, that is multiplies the polynomial by the modular inverse of the leading coefficient.

Parameters:

Name	Type	Description	Default
polynomial	Vector		required

Returns:

Type	Description
Vector	polynomial with leading coefficient equal to one.

---

Class for integer polynomial quotient ring

pqlattice.polynomial.ModIntPolyQuotientRing

ModIntPolyQuotientRing(
    poly_modulus: Vector, int_modulus: int
)

Creates the polynomial quotient ring of coefficient from the integer quotien ring

Parameters:

Name	Type	Description	Default
poly_modulus	Vector	modulus of the polynomial quotient ring	required
int_modulus	int	modulus of the integer quotient ring	required

quotient property

quotient: Vector

Get the polynomial modulus of this ring.

Returns:

Type	Description
Vector	p the polynomial modulus of this quotient ring

add

add(polynomial_a: Vector, polynomial_b: Vector) -> Vector

adds two polynomials

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

center_lift

center_lift(polynomial: Vector) -> Vector

Hoffstein page. 414 - 415

Parameters:

Name	Type	Description	Default
polynomial	Vector		required

Returns:

Type	Description
Vector	polynomial

inv

inv(polynomial: Vector) -> Vector

Tries to find the multiplicative inverse of the given polynomial in the ring.

Parameters:

Name	Type	Description	Default
polynomial	Vector		required

Returns:

Type	Description
Vector	polynomial

Raises:

Type	Description
ValueError	If the inverse does not exists

mul

mul(polynomial_a: Vector, polynomial_b: Vector) -> Vector

multiplies two polynomials

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

reduce

reduce(polynomial: Vector) -> Vector

Parameters:

Name	Type	Description	Default
polynomial	Vector		required

Returns:

Type	Description
Vector	polynomial

sub

sub(polynomial_a: Vector, polynomial_b: Vector) -> Vector

subtract one polynomial from the other

Parameters:

Name	Type	Description	Default
polynomial_a	Vector		required
polynomial_b	Vector		required

Returns:

Type	Description
Vector	polynomial

---

General free functions for polynomial operations

pqlattice.polynomial.poly

add

add(p: Vector, q: Vector) -> Vector

Adds two polynomials together.

Parameters:

Name	Type	Description	Default
p	Vector		required
q	Vector		required

Returns:

Type	Description
Vector	polynomial

deg

deg(p: Vector) -> int

Returns degree of the given polynomial. Assumes -1 for the zero polynomial.

Parameters:

Name	Type	Description	Default
p	Vector		required

Returns:

Type	Description
int	degree

Raises:

Type	Description
ValueError	If the vector is empty

is_zero_poly

is_zero_poly(p: Vector) -> bool

Checks if the poly is zero poly - all coefficients are equal to zero.

Parameters:

Name	Type	Description	Default
p	Vector	polynomial	required

Returns:

Type	Description
bool	True if all coefficients are equal to zero, False otherwise

Raises:

Type	Description
ValueError	If the given Vector is empty

make_poly

make_poly(data: ArrayLike) -> Vector

Helper function, creates polynomial from the array like.

Parameters:

Name	Type	Description	Default
data	ArrayLike		required

Returns:

Type	Description
Vector	polynomial

Raises:

Type	Description
ValueError	if the data has wrong shape

monomial

monomial(coeff: int, degree: int) -> Vector

For given degree d and coefficient c, constructs a monomial cX + ** (d - 1)

Parameters:

Name	Type	Description	Default
coeff	int		required
degree	int		required

Returns:

Type	Description
Vector	polynomial

Raises:

Type	Description
ValueError	if degree is negative

mul

mul(p: Vector, q: Vector) -> Vector

Multiplies two polynomials.

Parameters:

Name	Type	Description	Default
p	Vector		required
q	Vector		required

Returns:

Type	Description
Vector	polynomial

pad

pad(p: Vector, max_deg: int) -> Vector

Pad's polynomial's coefficient's array with zero entries for powers higher than polynomial's degree, so that length of resulting array is equal to max_deg + 1.

Parameters:

Name	Type	Description	Default
p	Vector		required
max_deg	int	Degree that p is to be expanded to	required

Returns:

Type	Description
Vector	polynomial

Raises:

Type	Description
ValueError	If max deg is less than the degree of the given polynomial

sub

sub(p: Vector, q: Vector) -> Vector

Subtract one polynomial from the other

Parameters:

Name	Type	Description	Default
p	Vector		required
q	Vector		required

Returns:

Type	Description
Vector	polynomial

trim

trim(p: Vector) -> Vector

Trims zero coefficients of powers higher than polynomial's degree, so that resulting coefficient's arrray has length of deg(p) + 1.

Parameters:

Name	Type	Description	Default
p	Vector		required

Returns:

Type	Description
Vector	polynomial

zero_poly

zero_poly(max_deg: int = 0) -> Vector

constructs zero polynomial, expanded to the given parameter max_deg

Parameters:

Name	Type	Description	Default
max_deg	int	by default 0	0

Returns:

Type	Description
Vector	Vector of length max_deg + 1 filled with zeros

Raises:

Type	Description
ValueError	If the max_deg is negative