 NAME
 VERSION
 SYNOPSIS
 DESCRIPTION
 CLASS METHODS
 OBJECT METHODS
 DIAGNOSTICS
 DEPENDENCIES
 ROADMAP
 BUGS AND LIMITATIONS
 SEE ALSO
 AUTHOR
 CONTRIBUTING
 LICENSE AND COPYRIGHT
 DISCLAIMER OF WARRANTY
NAME
Math::Polynomial::ModInt  univariate polynomials over modular integers
VERSION
This documentation refers to version 0.004 of Math::Polynomial::ModInt.
SYNOPSIS
use Math::Polynomial;
use Math::ModInt qw(mod);
use Math::Polynomial::ModInt qw(modpoly);
$p = modpoly(265, 3); # some polynomial modulo 3
$p = Math::Polynomial::ModInt>from_index(265, 3); # the same
$p = Math::Polynomial::ModInt>new(
mod(1, 3), mod(1, 3), mod(2, 3), mod(0, 3), mod(0, 3), mod(1, 3)
); # the same
$p = Math::Polynomial::ModInt>from_int_poly(
Math::Polynomial>new(1, 1, 2, 0, 0, 1), 3
); # the same
$q = $p>from_index(27); # x^3 (mod 3)
$t = $p>isa('Math::Polynomial'); # true
$s = $p>as_string; # '(x^5 + 2*x^2 + x + 1 (mod 3))'
$d = $p>degree; # 5
$i = $p>index; # 265
$b = $p>modulus; # 3
$n = $p>number_of_terms; # 4
$u = $p>lift; # x^5 + 2*x^2 + x + 1
$v = $p>centerlift; # x^5  x^2 + x + 1
$z = $p>first_root; # undef
$m = $p>is_irreducible; # true
$r = modpoly(131, 3); # x^4 + x^3  x^2 + x  1
$x = $r>first_root; # mod(2, 3)
$c = $r>is_irreducible; # false
$f = $r>lambda_reduce(2); #  x  1 (mod 3)
DESCRIPTION
Math::Polynomial::ModInt is a subclass of Math::Polynomial for modular integer coefficient spaces. It adds domainspecific methods and stringification options to the base class. Notably, it implements a bijection from unsigned integers to polynomials for a given modulus.
CLASS METHODS
Constructors
 new

Math::Polynomial::ModInt>new(@coeff)
creates a polynomial from its coefficients in ascending order of degrees.@coeff
must have at least one value and all values must be Math::ModInt objects with the same modulus.Other constructors defined in the parent class Math::Polynomial, like monomial and from_roots, are also valid. Note, however, that polynomial operations assuming that the coefficient space is a field, like interpolate and divmod, are safe to use only with prime moduli. Using them with a composite modulus may result in a "modulus not prime" exception.
 from_index

As there are finitely many modular integer polynomials for any fixed modulus and degree, and countably many for any fixed modulus, they can be enumerated with an unsigned integer index. Indeed, a number written with base n digits is equivalent to a polynomial with modulo n coefficients. We call the number the index of the polynomial.
Math::Polynomial::ModInt>from_index($index, $modulus)
creates a polynomial from its index.$index
can be a perl native integer or a Math::BigInt object.  modpoly

The subroutine modpoly can be imported and used as a shortcut for the from_index constructor.
modpoly($index, $modulus)
is equivalent toMath::Polynomial::ModInt>from_index($index, $modulus)
, then.  from_int_poly

It is also possible to create a modular integer polynomial from an integer polynomial and a modulus.
Math::Polynomial::ModInt>from_int_poly($poly, $modulus)
, where$poly
is a Math::Polynomial object with integer coefficients and$modulus
is a positive integer, does this.
OBJECT METHODS
Constructors
 from_index

When called as an object method, the modulus argument of this constructor can be omitted.
$p>from_index($index)
is equivalent to$p>from_index($index, $p>modulus)
, then. If a modulus is specified, it takes precedence over the invocant. Thus,$p>from_index($index, $modulus)
is equivalent toMath::Polynomial::ModInt>from_index($index, $modulus)
.  from_int_poly

Similarly,
$p>from_int_poly($intpoly)
is equivalent to$p>from_int_poly($intpoly, $p>modulus)
.
Operators
All operators of the parent module Math::Polynomial, as far as they do not involve division, are valid for Math::Polynomial::ModInt objects, too. Notably, addition, subtraction, and multiplication of modular integer polynomials is valid and indeed handled by the parent class. Invalid operations will yield exceptions from Math::ModInt.
If the modulus is a prime number, division is valid in the coefficient space and thus all operators, including divmod and gcd, are safe.
Additionally, a number of comparison operators are defined for modular integer polynomials only. Currently, these are implemented in the Math::Polynomial::ModInt::Order helper module rather than as overloaded operators, for reasons explained there.
Property Accessors
In addition to properties defined in the parent module Math::Polynomial, like degree, coeff, and is_monic, some properties specific for modular integer polynomials are defined.
 index

$p>index
calculates the index of a modular integer polynomial$p
, as defined above. Cf. "from_index".Note that the index grows exponentially with the degree of the polynomial and is thus represented as a Math::BigInt object.
 modulus

$p>modulus
returns the modulus common to all coefficients of the modular integer polynomial$p
.  number_of_terms

$p>number_of_terms
returns the number of nonzero coefficients of the modular integer polynomial$p
. Recent versions of the parent module also have this method.
Algebraic Operators
 lambda_reduce

$p>lambda_reduce($lambda)
generates a polynomial of degree lambda or lower from a highdegree polynomial in this way: Remove the highest degree coefficient (for degree n) and add it to the coefficient of degree n  lambda, and repeat until the degree of the remaining polynomial is less or equal to lambda.If lambda happens to be a multiple of the Carmichael totient of the modulus, which will be one less than the modulus if the modulus is a prime number, the reduced polynomial will evaluate pointwise equivalent to the original polynomial.
 first_root

$p>first_root
returns the root with the smallest nonnegative residue of the polynomial, if such roots exist, otherwise undef. As currently implemented, this operation will be timeconsuming for large moduli.  is_irreducible

If
$p
is a modular integer polynomial with prime modulus,$p>is_irreducible
returns a boolean value telling if the polynomial is irreducibe. An irreducible polynomial is a nonconstant polynomial that is not a product of two or more other nonconstant polynomials.Irreducibility is mostly of interest for prime moduli, where factorization is always unique. This method therefore is implemented for prime moduli only. Note, however, that primality of the modulus is not explicitly checked, as this can be done beforehand once and would unnecessarily slow down operations on several polynomials with the same modulus. As currently implemented, the method may either return a meaningless result or throw a 'modulus is not prime' exception when called with such a modulus.
Conversions
 as_string

For conversion to a string, the whole string configuration functionality of the parent module can be employed. For convenience, the default string configuration for Math::Polynomial::ModInt is already adapted to a more terse representation, so that the modulus is only written once.
$p>as_string
could return'(x^5 + 2*x^2 + x + 1 (mod 3))'
, for example.  lift

The lift method is a reverse operation to from_int_poly.
$p>lift
returns a Math::Polynomial object with integer coefficients with values ranging from zero to the modulus minus one. It is equivalent to the Math::Polynomial::ModInt object$p
in the sense that from_int_poly would turn it back to$p
.  centerlift

The centerlift method is an alternative to lift with the only difference that the integer values of the coefficients range from minus half of the modulus, rounded up, to plus half of the modulus, rounded down, if the modulus is odd, or minus half of the modulus, plus one, to plus half of the modulus, if it is even.
All lifting methods may be used together with tree conversions to get yet more string representations of polynomials, if so desired.
DIAGNOSTICS
Dealing with Math::ModInt objects can generally trigger exceptions from Math::ModInt::Event. Mixing different moduli or dividing noncoprime elements could be causes. These exceptions will correctly be propagated as failures of code calling Math::Polynomial::ModInt in general, but in some situations Math::Polynomial may be blamed.
Other error conditions, like using nonintegers or nonobjects where they would be expected, are not rigorously checked and may yield unreliable behavior rather than error messages.
The error conditions that are actually reported are these:
modulus not prime

A method only defined for prime moduli, like is_irreducible, has been called inappropriately. Note that this is not always detected and the result might be just wrong in such cases.
undefined inverse

A method needing the multiplicative inverse of a coefficient, like monize, has been called where that coefficient had no inverse. This can occur with coefficients that are not coprime to the modulus.
usage error: modulus parameter missing

The from_index or from_int_poly constructors have been used with insufficient information as to the value of the modulus. They should be either invoked with an explicit modulus (recommended) or as an object method.
DEPENDENCIES
This library uses Math::ModInt (version 0.012 and up) for modular integer calculations and Math::Polynomial (version 1.015 and up) for polynomial arithmetic, as well as Carp (any version) for diagnostic messages. The minimal required perl version is 5.6.
ROADMAP
The toolbox of algebraic operations is by no means complete. Irreducibility checking is based on Berlekamp's factorization algorithm but full factorization is not yet implemented. It is intended to be added in one of the next releases.
Some applications of modular integer polynomials will be provided by the Math::GaloisField hierarchy of modules rather than in this package. Math::Polynomial::ModInt is meant for basic stuff that can more or less be expected in a subclass of Math::Polynomial, while algebraic field properties are more appropriate in the other package. For example, division means polynomial division with remainder here, and proper division governed by field arithmetic there.
Ideally (pun not intended), the element type Math::Polynomial::ModInt with nonprime moduli should have a corresponding space type like Math::PolynomialRing::ModInt, where more algebraic ring stuff could have a home. It is not yet planned, though, but some tidbits could make an appearance in the Math::Polynomial::ModInt examples collection in the meantime.
BUGS AND LIMITATIONS
Most of the time, method arguments are not rigourosly checked to make sense. Cf. Diagnostics.
Some calculations, like root finding and checking for irreducibility, can be timeconsuming. Operations involving large integer numbers will be faster if Math::BigInt::GMP is installed. So far, this package is pure perl only. An XS version may be added eventually, but not in the near future.
Bug reports and more suggestions are always welcome — please submit them through the CPAN RT, http://rt.cpan.org/NoAuth/Bugs.html?Dist=MathPolynomialModInt.
SEE ALSO
Math::GaloisField (soon to be published)
AUTHOR
Martin Becker, <beckercpanmp (at) cozap.com>
CONTRIBUTING
Contributions to this library are welcome (see the CONTRIBUTING file).
LICENSE AND COPYRIGHT
Copyright (c) 20132019 by Martin Becker, Blaubeuren.
This library is free software; you can distribute it and/or modify it under the terms of the Artistic License 2.0 (see the LICENSE file).
DISCLAIMER OF WARRANTY
This library is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.