NAME

Sidef::Types::Number::PolynomialMod - Polynomial arithmetic modulo another polynomial

DESCRIPTION

This class implements polynomial arithmetic in quotient rings, where polynomials are computed modulo another polynomial. This is particularly useful for finite field arithmetic, algebraic number theory, and cryptographic applications.

A PolynomialMod object represents a polynomial reduced modulo a given modulus polynomial, similar to how integers modulo n work but in the polynomial domain.

SYNOPSIS

# Create a polynomial mod object
var p = PolynomialMod([1, 2, 3], [1, 0, 1])  # (1 + 2x + 3x²) mod (1 + x²)

# Arithmetic operations
var q = PolynomialMod([2, 1], [1, 0, 1])
say p + q      # Addition
say p * q      # Multiplication
say p ** 3     # Exponentiation

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

# Get the modulus
say p.modulus

# Lift to regular polynomial
say p.lift

INHERITS

Inherits methods from:

* Sidef::Types::Number::Polynomial

METHODS

!=

a != b

Returns true if polynomial a is not equal to polynomial b modulo their common modulus.

Aliases: ne

%

a % b

Returns the remainder of polynomial a divided by polynomial b, computed modulo the modulus polynomial.

Aliases: mod

*

a * b

Returns the product of polynomials a and b, reduced modulo the modulus polynomial.

Aliases: mul

**

a ** b

Returns polynomial a raised to the power b, computed modulo the modulus polynomial. Supports both positive integers and negative integer exponents (computing modular inverse when needed).

Aliases: pow

+

a + b

Returns the sum of polynomials a and b, reduced modulo the modulus polynomial.

Aliases: add

++

a++

Increments polynomial a by 1 (adds the constant polynomial 1), reducing modulo the modulus polynomial.

Aliases: inc

-

a - b

Returns the difference of polynomials a and b, reduced modulo the modulus polynomial.

Aliases: sub

--

a--

Decrements polynomial a by 1 (subtracts the constant polynomial 1), reducing modulo the modulus polynomial.

Aliases: dec

/

a / b

Returns the quotient of polynomial a divided by polynomial b, computed modulo the modulus polynomial. This computes a times the modular inverse of b.

Aliases: ÷, div

//

a // b

Returns the integer (floor) division of polynomial a by polynomial b, computed modulo the modulus polynomial.

Aliases: idiv, idiv_ceil, idiv_floor, idiv_round, idiv_trunc

<

a < b

Compares polynomials a and b lexicographically by their coefficients. Returns true if a is less than b.

Aliases: lt

<=>

a <=> b

Three-way comparison operator. Returns -1 if a is less than b, 0 if equal, and 1 if greater. Comparison is performed lexicographically on coefficients.

Aliases: cmp

==

a == b

Returns true if polynomial a equals polynomial b modulo their common modulus.

Aliases: eq

>

a > b

Compares polynomials a and b lexicographically by their coefficients. Returns true if a is greater than b.

Aliases: gt

≤

a ≤ b

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

Aliases: <=, le

≥

a ≥ b

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

Aliases: >=, ge

abs

x.abs

Returns the absolute value of the polynomial. For polynomials, this typically ensures the leading coefficient is positive.

binomial

n.binomial(k)

Returns the binomial coefficient C(n, k) computed in the polynomial mod ring. This generalizes the standard binomial coefficient to polynomial quotient rings.

ceil

x.ceil

Returns the ceiling of the polynomial. For polynomials with rational or real coefficients, this applies the ceiling function to each coefficient.

chinese

*polynomials.chinese

Applies the Chinese Remainder Theorem to solve a system of polynomial congruences. Given polynomials with different moduli, finds a polynomial that satisfies all congruences simultaneously.

derivative

x.derivative

Returns the formal derivative of the polynomial with respect to its variable, computed modulo the modulus polynomial.

divmod

x.divmod(y)

Returns a pair (quotient, remainder) from dividing polynomial x by polynomial y, computed modulo the modulus polynomial.

dump

x.dump

Returns a detailed string representation of the polynomial mod object, showing its internal structure for debugging purposes.

eval

x.eval(value)

Evaluates the polynomial at the given value by substituting the value for the variable and computing the result modulo the modulus polynomial.

float

x.float

Converts the polynomial to a floating-point approximation. For polynomials, this typically evaluates at x=1 or converts coefficients to floating-point.

floor

x.floor

Returns the floor of the polynomial. For polynomials with rational or real coefficients, this applies the floor function to each coefficient.

gcd

x.gcd(y)

Returns the greatest common divisor of polynomials x and y, computed modulo the modulus polynomial using the Euclidean algorithm.

gcdext

x.gcdext(y)

Returns the extended GCD of polynomials x and y. Returns a triple (g, u, v) where g is the GCD and u, v are polynomials such that u*x + v*y = g (modulo the modulus polynomial).

inv

x.inv

Returns the multiplicative inverse of polynomial x modulo the modulus polynomial. This exists if and only if x and the modulus are coprime.

is_mone

x.is_mone

Returns true if the polynomial equals -1 (the constant polynomial with coefficient -1).

is_one

x.is_one

Returns true if the polynomial equals 1 (the constant polynomial with coefficient 1), which is the multiplicative identity.

is_zero

x.is_zero

Returns true if the polynomial is the zero polynomial, which is the additive identity.

lcm

x.lcm(y)

Returns the least common multiple of polynomials x and y, computed modulo the modulus polynomial.

lift

self.lift

Returns the underlying polynomial without the modulus constraint, "lifting" it from the quotient ring to the polynomial ring.

Aliases: to_poly

modulus

self.modulus

Returns the modulus polynomial by which all operations in this quotient ring are reduced.

neg

x.neg

Returns the additive inverse (negation) of polynomial x, which when added to x gives zero.

new

self.new(coeffs, modulus)
PolynomialMod(coeffs, modulus)

Creates a new PolynomialMod object from a list of coefficients and a modulus polynomial. The coefficients represent the polynomial starting from the constant term.

Example:

var p = PolynomialMod([1, 2, 3], [1, 0, 1])  # (1 + 2x + 3x²) mod (1 + x²)

Aliases: call

pretty

x.pretty

Returns a human-readable string representation of the polynomial in standard mathematical notation (e.g., "1 + 2x + 3x²").

rat

x.rat

Converts the polynomial to rational form, ensuring all coefficients are represented as exact rational numbers.

rat_approx

x.rat_approx

Returns a rational approximation of the polynomial, converting floating-point coefficients to nearby rational numbers.

round

x.round(r)

Rounds each coefficient of the polynomial to r decimal places (or to the nearest integer if r is not specified).

sqr

x.sqr

Returns the square of polynomial x (equivalent to x * x), computed modulo the modulus polynomial.

to_s

x.to_s

Converts the polynomial to a string representation suitable for display.

Aliases: stringify

EXAMPLES

# Working in Q[x]/(x² + 1) - Gaussian integers
var i = PolynomialMod([0, 1], [1, 0, 1])  # represents 'i' where i² = -1
say i ** 2    # Output: -1
say i ** 4    # Output: 1

# Arithmetic in finite fields
var a = PolynomialMod([1, 1], [1, 1, 1])  # (1 + x) mod (1 + x + x²)
var b = PolynomialMod([1, 0, 1], [1, 1, 1])  # (1 + x²) mod (1 + x + x²)
say a * b

# Finding modular inverses
var p = PolynomialMod([1, 2], [1, 0, 0, 1])
say p.inv     # Multiplicative inverse
say p * p.inv # Should be 1

SEE ALSO

Sidef::Types::Number::Polynomial

cpanm Sidef

perl -MCPAN -e shell
install Sidef