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

NAME

Sidef::Types::Number::PolynomialMod - Polynomial type over finite rings with modular arithmetic operations.

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.

Although a PolynomialMod is internally stored as this [poly, modulus] pair rather than the coefficient hash used by the parent Sidef::Types::Number::Polynomial class, hash-style access such as $obj-{exponent}> is transparently redirected to the underlying residue polynomial's own storage. This is what lets many methods inherited unchanged from Polynomial (like "to_n" below) keep working correctly without needing to be reimplemented here.

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.to_poly      # The underlying Polynomial (without modulus)

# CRT reconstruction (called as an instance method on one of the polynomials)
var r = p.chinese(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 residue polynomial without further modulus reduction, thanks to the hash-access redirection described above.

CONSTRUCTION

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

with_value

self.with_value(value)

Creates a new constant PolynomialMod holding just value, in the same quotient ring as the receiver (same modulus). Discards the receiver's own residue polynomial entirely.

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

COMPONENTS

to_poly

self.to_poly

Returns the underlying Sidef::Types::Number::Polynomial object, i.e. the reduced residue polynomial stripped of its modulus.

var p = PolynomialMod([1, 2, 3], [1, 0, 1])
say p.to_poly    # the residue polynomial, without a modulus

Aliases: lift

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

ARITHMETIC OPERATIONS

add

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: +

sub

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: -

mul

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: *

sqr

x.sqr

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

pow

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: **

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.

div

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: ÷

idiv

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_ceil, idiv_floor, idiv_round, idiv_trunc

mod

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: %

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.

inc

++a

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

Aliases: ++

dec

--a

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

Aliases: --

inv

x.inv

Computes 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.

This uses 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.

# 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, LCM, AND FACTORIZATION

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.

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.

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

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.

factor_exp

poly.factor_exp

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

Requirement: this only works when the object's modulus is a plain prime number (i.e., the polynomial represents an element of Z_p[x] directly), not a polynomial modulus — the more general R[x]/(m(x)) case used elsewhere in this class does not apply here.

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 from "factor_exp" as a flat array of factors, with each irreducible factor repeated according to its multiplicity. Subject to the same scalar-modulus requirement as "factor_exp".

CALCULUS

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: value is first reduced modulo the modulus, then each nonzero term coeff_k * value^k is computed independently — with value^k computed via modular exponentiation on Sidef::Types::Number::Mod — and all the terms are summed and reduced modulo the modulus.

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

var p = PolynomialMod([1, 2, 3], [1, 0, 1])
say p.eval(2)     # sum of coeff_k * 2^k, reduced mod (x^2+1)

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

COMBINATORICS

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 REMAINDER THEOREM

chinese

self.chinese(other, ...)

Applies the Chinese Remainder Theorem (CRT) to the receiver together with one or more other PolynomialMod objects that may have different moduli. Finds a single polynomial congruent to each one modulo its own modulus. The combined modulus is the LCM of all the individual moduli.

Called as an instance method on one of the polynomials being combined — not as a class-level call:

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 = a.chinese(b)

ROUNDING AND CONVERSION

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_n

x.to_n

Inherited unchanged from Sidef::Types::Number::Polynomial: converts to a plain Number when the residue polynomial is the zero or a constant polynomial, or NaN otherwise.

say PolynomialMod([5], [1, 0, 1]).to_n     # 5
say PolynomialMod([1, 0], [1, 0, 1]).to_n   # NaN (non-constant)

PREDICATES

is_zero

x.is_zero

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

is_one

x.is_one

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

is_mone

x.is_mone

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

is_unit

self.is_unit

Returns true if this element is invertible in the quotient ring (its "inv" succeeds rather than producing NaN).

COMPARISON

eq

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: ==

ne

a != b

Returns true if a is not equal to b. Implemented as the logical negation of "eq".

Aliases: !=

cmp

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: <=>

lt

a < b

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

Aliases: <

gt

a > b

Returns true if a is strictly greater than b.

Aliases: >

le

a <= b

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

Aliases: <=, ≤

ge

a >= b

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

Aliases: >=, ≥

STRING REPRESENTATION AND BOOLEAN CONTEXT

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.

__boolify__

self.__boolify__

Backs the object's boolean-context overload (e.g. if polymod_value). Checks only the constant term (coefficient of x^0) of the residue polynomial: truthy if it's present and nonzero, falsy if it's zero or absent — regardless of whether other, higher-degree terms are nonzero.

if (PolynomialMod([1, 0], [1, 0, 1])) { ... }   # falsy: no constant term
if (PolynomialMod([1, 3], [1, 0, 1])) { ... }   # truthy: constant term is 3

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 = a.chinese(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)

Factoring over GF(p)[x]

# Modulus here is the scalar prime p, not a polynomial
var f = PolynomialMod([1, 0, -1], 5)   # x^2 - 1 over GF(5)
say f.factor_exp
say f.factor

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