Math::Polynomial::ModInt - univariate polynomials over modular integers
This documentation refers to version 0.002 of Math::Polynomial::ModInt.
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
Math::Polynomial::ModInt is a subclass of Math::Polynomial for modular integer coefficient spaces. It adds domain-specific methods and stringification options to the base class. Notably, it implements a bijection from unsigned integers to polynomials for a given modulus.
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.
Math::Polynomial::ModInt->new(@coeff)
@coeff
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, do not make sense with modular integers in general. Some of them could be used with prime moduli, but specialized modules like Math::GaloisField implement similar operations more efficiently.
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.
Math::Polynomial::ModInt->from_index($index, $modulus)
$index
The subroutine modpoly can be imported and used as a shortcut for the from_index constructor. modpoly($index, $modulus) is equivalent to Math::Polynomial::ModInt->from_index($index, $modulus), then.
modpoly($index, $modulus)
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.
Math::Polynomial::ModInt->from_int_poly($poly, $modulus)
$poly
$modulus
When called as an object method, the modulus argument of constructors 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 to Math::Polynomial::ModInt->from_index($index, $modulus).
$p->from_index($index)
$p->from_index($index, $p->modulus)
$p->from_index($index, $modulus)
Similarly, $p->from_int_poly($intpoly) is equivalent to $p->from_int_poly($intpoly, $p->modulus).
$p->from_int_poly($intpoly)
$p->from_int_poly($intpoly, $p->modulus)
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.
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.
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.
$p->index calculates the index of a modular integer polynomial $p, as defined above. Cf. #from_index.
$p->index
$p
Note that the index grows exponentially with the degree of the polynomial and is thus represented as a Math::BigInt object.
$p->modulus returns the modulus common to all coefficients of the modular integer polynomial $p.
$p->modulus
$p->number_of_terms returns the number of non-zero coefficients of the modular integer polynomial $p.
$p->number_of_terms
This method should actually better be provided by the parent class, as the property is not quite specific to modular integer coefficients. Expect this to be done in an upcoming Math::Polynomial release.
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.
$p->as_string
'(x^5 + 2*x^2 + x + 1 (mod 3))'
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.
$p->lift
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.
Dealing with Math::ModInt objects can generally trigger exceptions from Math::ModInt::Event. Mixing different moduli or dividing non-coprime elements could be causes.
Other error conditions, like using non-integers or non-objects where they would be expected, are not rigorously checked and may yield unreliable behavior rather than error messages.
The few error conditions that are actually diagnosed are these:
usage error: modulus parameter missing
The from_index or from_int_poly construcors 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.
This library uses Math::ModInt (version 0.011 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.
Bug reports and suggestions are always welcome — please submit them through the CPAN RT, <http://rt.cpan.org/NoAuth/Bugs.html?Dist=Math-Polynomial-ModInt>.
Math::Polynomial::ModInt::Order
Math::Polynomial
Math::ModInt
Math::GaloisField
Martin Becker, <becker-cpan-mp (at) cozap.com>
<becker-cpan-mp (at) cozap.com>
Contributions to this library are welcome (see the CONTRIBUTING file).
Copyright (c) 2013-2019 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).
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.
To install Math::Polynomial::ModInt, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::Polynomial::ModInt
CPAN shell
perl -MCPAN -e shell install Math::Polynomial::ModInt
For more information on module installation, please visit the detailed CPAN module installation guide.