/ 
Sidef-26.05
⭐ Starred 115 / Sidef::Types::Number::PolynomialMod

NAME

Sidef::Types::Number::PolynomialMod - Polynomial arithmetic in quotient rings

DESCRIPTION

This class implements polynomial arithmetic in quotient rings of the form R[x]/(m(x)), where polynomials are reduced modulo a fixed modulus polynomial m(x). This mirrors how integers modulo n work (via Sidef::Types::Number::Mod), but in the polynomial domain.

A PolynomialMod object is a pair [poly, modulus] where poly is the residue polynomial (already reduced) and modulus is the polynomial by which all results are reduced. All arithmetic operations automatically reduce their result modulo the shared modulus.

Internally, polynomials are stored as a hash mapping integer exponents to their coefficients (Sidef::Types::Number::Number objects). Zero coefficients are not stored.

Typical use cases include:

  • Finite field arithmetic (e.g., GF(2^8) for AES)

  • Algebraic number fields (e.g., Q[x]/(x^2+1) ≅ Gaussian integers)

  • Cyclotomic fields and rings of algebraic integers

  • Factoring polynomials over finite fields

SYNOPSIS

# Create polynomials mod (1 + x^2) — working in Q[x]/(x^2 + 1)
var i = PolynomialMod([0, 1], [1, 0, 1])   # represents the element x (i.e. sqrt(-1))
say i**2     # Output: -1 (mod x^2 + 1)
say i**4     # Output: 1 (mod x^2 + 1)

# General arithmetic
var p = PolynomialMod([1, 2, 3], [1, 0, 1])   # (3x^2 + 2x + 1) mod (x^2 + 1)
var q = PolynomialMod([1, 2],   [1, 0, 1])    # (2x + 1) mod (x^2 + 1)
say (p + q)      # Addition
say (p - q)      # Subtraction
say (p * q)      # Multiplication, reduced mod (x^2 + 1)
say (p ** 3)     # Exponentiation via square-and-multiply

# Division (exact when the inverse exists)
say (p / q)

# Polynomial GCD and extended GCD
var (g, u, v) = p.gcdext(q)

# Evaluate the polynomial at a point
say p.eval(2)

# Retrieve parts
say p.modulus      # The modulus polynomial: x^2 + 1
say p.lift         # The underlying Polynomial (without modulus)

# CRT reconstruction
var r = PolynomialMod.chinese(p, q)

COEFFICIENT ORDER IN ARRAY CONSTRUCTORS

When constructing from an array, coefficients are given in descending degree order (highest-degree coefficient first):

PolynomialMod([a_n, a_{n-1}, ..., a_1, a_0], modulus)
# represents a_n*x^n + a_{n-1}*x^{n-1} + ... + a_1*x + a_0

Examples:

PolynomialMod([1, 0, 1], [1, 0, 0, 1])
# polynomial:  x^2 + 1
# modulus:     x^3 + 1

PolynomialMod([0, 1], [1, 0, 1])
# polynomial:  x
# modulus:     x^2 + 1

The same descending convention applies when constructing the modulus array.

INHERITS

Inherits methods from:

Sidef::Types::Number::Polynomial

Many methods not overridden here (such as degree, coeffs, exponents, content, leading_coefficient, height, etc.) are provided by the parent class and operate on the lifted polynomial without the modulus constraint.

METHODS

new

PolynomialMod(array_ref, modulus_array_ref)
PolynomialMod(array_ref, modulus_poly)
PolynomialMod(poly,      modulus)
self.new(...)

Constructs a new PolynomialMod object. The last argument is always the modulus; everything before it specifies the polynomial residue.

The modulus may be given as an array reference or as an existing Sidef::Types::Number::Polynomial object. The residue polynomial is reduced modulo the modulus upon construction.

# From coefficient arrays (descending degree order)
var p = PolynomialMod([3, 2, 1], [1, 0, 1])   # (3x^2 + 2x + 1) mod (x^2 + 1)

# From an existing Polynomial object
var m = Polynomial([1, 0, 1])
var p = PolynomialMod([3, 2, 1], m)

# Instance-method form (creates new object with same class)
var q = p.new([1, 2], [1, 0, 1])

Special case — instance call with one argument: when called as an instance method with a single argument (no coefficients before the modulus), it evaluates the polynomial at that argument rather than constructing a new object. See "eval".

Aliases: call

lift

self.lift

Returns the underlying Sidef::Types::Number::Polynomial object, i.e. the reduced residue polynomial stripped of its modulus. The returned value is a plain Polynomial in the free ring R[x].

var p = PolynomialMod([1, 2, 3], [1, 0, 1])
say p.lift    # Polynomial: 2x + (1 - 3) = -2 + 2x (after reduction)

Aliases: to_poly

modulus

self.modulus

Returns the modulus polynomial by which all arithmetic in this quotient ring is reduced. The return value is a Sidef::Types::Number::Polynomial.

var p = PolynomialMod([1, 2], [1, 0, 1])
say p.modulus   # x^2 + 1

+

a + b

Returns the sum of a and b, reduced modulo the shared modulus. Both operands must share the same modulus polynomial. If b is a scalar (non-PolynomialMod), it is added to the constant term after reduction.

Aliases: add

++

a++

Increments a by 1 (adds the constant polynomial 1) and reduces modulo the modulus. Equivalent to a + 1.

Aliases: inc

-

a - b

Returns the difference a - b, reduced modulo the shared modulus. If b is a scalar, it is subtracted from the constant term after reduction.

Aliases: sub

--

a--

Decrements a by 1 (subtracts the constant polynomial 1) and reduces modulo the modulus.

Aliases: dec

*

a * b

Returns the product of a and b, reduced modulo the shared modulus. Coefficient multiplication is also reduced modulo the modulus at each step, keeping intermediate values small.

If b is a scalar, each coefficient of a is multiplied by b (after reducing b mod the modulus) without a full polynomial multiplication.

Aliases: mul

sqr

x.sqr

Returns the square of x modulo the modulus. Equivalent to x * x.

**

a ** n

Returns a raised to the integer power n, computed modulo the modulus polynomial using the binary (square-and-multiply) method. n may be:

  • A non-negative integer — standard modular exponentiation.

  • A negative integer — computes (a^|n|)^{-1} via "inv".

var i = PolynomialMod([1, 0], [1, 0, 1])   # x mod (x^2 + 1)
say i**2    # -1 mod (x^2 + 1)
say i**4    #  1 mod (x^2 + 1)

Aliases: pow

powmod

base.powmod(exp, poly_mod)

Computes base^exp mod poly_mod using binary (square-and-multiply), reducing modulo poly_mod after every multiplication to keep the degree below deg(poly_mod).

Returns a PolynomialMod object, representing the modular exponentiation result.

/

a / b

Divides a by b in the quotient ring.

  • If b is a PolynomialMod with the same modulus, polynomial Euclidean division is attempted. If the division is exact, the quotient is returned. If not exact, a Sidef::Types::Number::Fraction object is returned.

  • If b is zero, returns a polynomial with an infinite coefficient.

  • If b is a scalar, each coefficient of a is divided by b (after reducing b mod the modulus).

Note that exact division in a polynomial quotient ring requires the leading coefficient of b to be invertible modulo the coefficient ring (e.g., the modulus is prime for GF(p)[x] arithmetic). If the inverse does not exist (e.g. working over a non-field), the result is NaN.

Aliases: div, ÷

//

a // b

Returns the integer quotient from Euclidean division of a by b, discarding the remainder. Equivalent to the quotient component of "divmod".

Note: The rounding variants (idiv_ceil, idiv_floor, idiv_round, idiv_trunc) are all currently aliased to the same integer-quotient behaviour.

Aliases: idiv, idiv_ceil, idiv_floor, idiv_round, idiv_trunc

%

a % b

When b is a PolynomialMod with the same modulus as a, returns the remainder from Euclidean polynomial division (i.e. the second component of "divmod").

When b is a different polynomial (or has a different modulus), reinterprets b as the new modulus and returns a new PolynomialMod object with the same residue polynomial but reduced under the new modulus. This is the primary way to change the modulus of an existing polynomial.

var p = PolynomialMod([1, 2, 3], [1, 0, 1])
var q = PolynomialMod([1, 1],   [1, 0, 1])
say p % q      # remainder of p divided by q, mod (x^2 + 1)

Aliases: mod

divmod

x.divmod(y)

Performs Euclidean polynomial division of x by y within the quotient ring, using the standard long-division algorithm. The leading coefficient of y must be invertible in the coefficient ring (its modular inverse is computed and used at each step).

Returns a list of two PolynomialMod objects (quotient, remainder) satisfying x == quotient * y + remainder with deg(remainder) < deg(y).

If x and y have different moduli, both quotient and remainder are NaN. If the leading coefficient of y has no modular inverse, returns NaN.

neg

x.neg

Returns the additive inverse of x: the polynomial whose coefficients are all negated. Adding x and x.neg yields the zero polynomial.

abs

x.abs

Returns x multiplied by the sign of its leading coefficient, ensuring the leading coefficient is positive. Equivalent to x * x.sgn.

inv

x.inv

Compute the multiplicative inverse of a PolynomialMod element.

In the quotient ring R[x]/(m(x)), the inverse of f(x) exists if and only if gcd(f, m) = 1. When it exists, the extended Euclidean algorithm gives polynomials u and v such that:

u(x)*f(x) + v(x)*m(x) = 1

which means u(x)*f(x) ≡ 1 (mod m(x)), so u is the inverse.

We use Polynomial::gcdext on the lifted polynomials (plain polynomial ring arithmetic), which normalizes the GCD to monic. If the result is the constant polynomial 1, the Bézout coefficient u is the inverse. The PolynomialMod constructor automatically reduces u modulo m.

Reference

https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B%C3%A9zout's_identity_and_extended_GCD_algorithm

Example

# Matches PARI/GP: Mod(1+2*x, x^3+1)^(-1)
var p = PolynomialMod([2, 1], [1, 0, 0, 1])   # (2x+1) mod (x^3+1)
say(p.inv)    # -4/7*x^2 + 2/7*x - 1/7  (mod x^3+1)
say((p * p.inv) == 1)   # true

gcd

x.gcd(y)

Returns the greatest common divisor of polynomials x and y in the quotient ring, using the polynomial Euclidean algorithm (repeated remainder computation):

r0 = x, r1 = y
loop: (r0, r1) = (r1, r0 mod r1) until r1 is zero
return r0

Both x and y must share the same modulus. The result is the GCD as a PolynomialMod in the same ring.

Reference: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclid's_algorithm

gcdext

x.gcdext(y)

Extended Euclidean algorithm for polynomials in the quotient ring. Returns a list of five values:

(g, u, v, a1, b1)

where g = gcd(x, y) and u, v are Bézout coefficients satisfying:

u*x + v*y == g

The additional values a1 and b1 (the final remainders scaled by a sign factor) are also returned; they relate to the last non-trivial step of the

extended Euclidean recursion.

Example:

var (g, u, v) = p.gcdext(q)
say u*p + v*q == g    # True

Reference: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B%C3%A9zout's_identity_and_extended_GCD_algorithm

lcm

x.lcm(y)

Returns the least common multiple of polynomials x and y, computed as:

lcm(x, y) = abs(x * y) / gcd(x, y)

normalize_to_monic

x.normalize_to_monic

Returns a monic version of x (leading coefficient equal to 1) by multiplying each coefficient by the modular inverse of the leading coefficient. If the leading coefficient is already 1, x is returned unchanged. If the inverse does not exist (e.g. the coefficient ring is not a field), returns x unchanged.

derivative

x.derivative

Returns the formal derivative of x with respect to the polynomial variable, reduced modulo the modulus. Each term c_k * t^k maps to k * c_k * t^{k-1}, with the coefficient also reduced modulo the modulus polynomial.

var p = PolynomialMod([1, 3, 1], [1, 0, 1])   # x^2 + 3x + 1 mod (x^2+1)
say p.derivative   # 3 + 2x, reduced mod (x^2 + 1)

eval

x.eval(value)

Evaluates the polynomial at value by Horner-style substitution, using modular arithmetic throughout. The value is first reduced modulo the modulus polynomial, and powers of the value are computed as Sidef::Types::Number::Mod elements to keep results in the quotient ring.

Returns a scalar (Sidef::Types::Number::Number).

var p = PolynomialMod([1, 2, 3], [1, 0, 1])
say p.eval(2)     # evaluates (3*4 + 2*2 + 1) mod ... = 17 mod (x^2+1)

If the polynomial is the zero polynomial, returns 0 directly.

binomial

n.binomial(k)

Computes the generalised binomial coefficient C(n, k) where n is a PolynomialMod and k is an integer. Uses the falling-factorial definition:

C(n, k) = n * (n-1) * ... * (n-k+1) / k!

The product is computed via binary splitting for efficiency, and the division by k! is performed via "div".

var x = PolynomialMod([1, 0], [1, 0, 1])   # x mod (x^2+1)
say x.binomial(2)   # x*(x-1)/2 mod (x^2+1)

chinese

*polynomials.chinese

Applies the Chinese Remainder Theorem (CRT) to a list of PolynomialMod objects that may have different moduli. Finds a single polynomial congruent to each input modulo its respective modulus. The combined modulus is the LCM of all individual moduli.

var a = PolynomialMod([1, 2], [1, 0, 1])   # 2x+1 mod (x^2+1)
var b = PolynomialMod([3, 1], [1, 1, 1])   # x+3 mod (x^2+x+1)
var c = PolynomialMod.chinese(a, b)

==

a == b

Returns true if a and b are equal as elements of the same quotient ring. Two PolynomialMod objects are equal if and only if their moduli are equal and their residue polynomials are equal (coefficient by coefficient). When comparing against a non-PolynomialMod value, the value is reduced modulo a's modulus before comparison.

Aliases: eq

!=

a != b

Returns true if a is not equal to b. Implemented as the logical negation of "==". See "==" for the equality semantics.

Aliases: ne

<=>

a <=> b

Three-way comparison. When both arguments are PolynomialMod objects, the moduli are compared first; if they differ, that result is returned. Otherwise the residue polynomials are compared lexicographically (highest-degree coefficient first, then lower degrees). Returns -1, 0, or 1.

Aliases: cmp

<

a < b

Returns true if a is strictly less than b under the lexicographic ordering defined by "<=">.

Aliases: lt

>

a > b

Returns true if a is strictly greater than b.

Aliases: gt

≤

a ≤ b

Returns true if a is less than or equal to b.

Aliases: <=, le

≥

a ≥ b

Returns true if a is greater than or equal to b.

Aliases: >=, ge

is_zero

x.is_zero

Returns true if x is the zero polynomial (the additive identity). Uses "==" against 0.

is_one

x.is_one

Returns true if x is the polynomial 1 (the multiplicative identity). Uses "==" against 1.

is_mone

x.is_mone

Returns true if x equals the constant polynomial -1. Uses "==" against -1.

factor_exp

poly.factor_exp

Performs complete Cantor-Zassenhaus factorization of a polynomial over GF(p)[x].

The result includes multiplicities and is returned as an array of [factor, exponent] pairs.

Each irreducible factor is returned as a monic PolynomialMod object with scalar modulus p. The first entry in the result is the leading coefficient of the original polynomial, represented as a [lc, 1] pair.

Algorithm

1. Preprocessing

The polynomial is normalized to monic form, then made squarefree by dividing by gcd(f, f'). This removes one copy of each repeated factor.

2. DDF

Distinct Degree Factorization groups irreducible factors by degree.

3. EDF

Each DDF group is split into irreducible factors using Cantor-Zassenhaus.

4. Multiplicity recovery

Each irreducible factor is repeatedly divided into the original polynomial to determine its multiplicity.

factor

poly.factor

Returns the factorization as a flat array of factors, with each irreducible factor repeated according to its multiplicity.

float

x.float

Returns a new PolynomialMod with each coefficient converted to a floating-point approximation, preserving the modulus.

rat

x.rat

Returns a new PolynomialMod with each coefficient converted to an exact rational number (Math::GMPq), preserving the modulus.

rat_approx

x.rat_approx

Returns a new PolynomialMod with each floating-point coefficient replaced by a nearby rational approximation, preserving the modulus.

floor

x.floor

Returns a new PolynomialMod with floor() applied to each coefficient, preserving the modulus.

ceil

x.ceil

Returns a new PolynomialMod with ceil() applied to each coefficient, preserving the modulus.

round

x.round(r)

Returns a new PolynomialMod with each coefficient rounded to r decimal places (or to the nearest integer when r is zero/unspecified), preserving the modulus.

to_s

x.to_s

Returns a Sidef::Types::String::String representation of the polynomial in the form:

<polynomial expression> (mod <modulus expression>)

For example: 2*x + 1 (mod x^2 + 1).

Aliases: stringify

pretty

x.pretty

Like "to_s" but uses the pretty display method from the parent class, which renders Unicode superscripts and cleaner coefficient notation.

dump

x.dump

Returns a Sidef::Types::String::String containing a round-trippable representation of the PolynomialMod object:

PolynomialMod(<exponent> => <coeff>, ..., <modulus>)

This mirrors the internal sparse storage format and is suitable for debugging.

BOOLEAN CONTEXT

In boolean context (if, while, etc.), a PolynomialMod is truthy if its constant term (coefficient of x^0) is truthy, and falsy if zero or absent.

EXAMPLES

Gaussian integers via Q[x]/(x² + 1)

var i = PolynomialMod([1, 0], [1, 0, 1])   # x ≡ i
say i**2    # -1 (mod x^2 + 1)
say i**4    # 1  (mod x^2 + 1)

var a = PolynomialMod([3, 2], [1, 0, 1])   # 2x + 3 ≡ 3 + 2i
var b = PolynomialMod([1, 4], [1, 0, 1])   # 4x + 1 ≡ 1 + 4i
say (a * b)   # (3+2i)(1+4i) = 3+12i+2i+8i^2 = (3-8) + 14i = -5 + 14i
              # Output: 14*x - 5 (mod x^2 + 1)

GCD and Bézout coefficients

var p = PolynomialMod([1, 0, 1], [1, 0, 0, 1])  # x^2+1 mod x^3+1
var q = PolynomialMod([1, 1],   [1, 0, 0, 1])   # x+1   mod x^3+1
var (g, u, v) = p.gcdext(q)
say g             # gcd
say (u*p + v*q)   # should equal g

Finite field GF(2)[x]/(x^4 + x + 1) — an irreducible polynomial over GF(2)

var m = [1, 0, 0, 1, 1]    # x^4 + x + 1
var a = PolynomialMod([1, 1, 0, 1], m)  # x^3 + x + 1
var b = PolynomialMod([1, 0, 1, 1], m)  # x^3 + x^2 + 1
say (a * b)    # product in GF(2^4)

Chinese Remainder Theorem

var a = PolynomialMod([2, 1], [1, 0, 1])   # 2x+1 mod (x^2+1)
var b = PolynomialMod([1, 3], [1, 1, 1])   # x+3  mod (x^2+x+1)
var c = PolynomialMod.chinese(a, b)
say c         # polynomial congruent to both a and b mod their respective moduli

Derivative in a quotient ring

var p = PolynomialMod([1, 0, 3, 2], [1, 0, 1])  # 3x^2 + 2x (after reduction)
say p.derivative   # formal derivative reduced mod (x^2 + 1)

REFERENCES

NOTES

  • Operand compatibility: Most binary operations (+, -, *, gcd, divmod, etc.) require both operands to share the same modulus polynomial. Mixing operands with different moduli will either give wrong results or return NaN.

  • Coefficient ring: Coefficients are general Sidef::Types::Number::Number objects (arbitrary precision). For finite-field semantics (e.g. GF(p)[x]), you should use a modulus polynomial whose coefficients are already in GF(p) and ensure your input coefficients are also reduced mod p.

SEE ALSO

Sidef::Types::Number::Polynomial, Sidef::Types::Number::Mod, Sidef::Types::Number::Fraction