 NAME
 VERSION
 SYNOPSIS
 DESCRIPTION
 DIAGNOSTICS
 DEPENDENCIES
 BUGS AND LIMITATIONS
 SEE ALSO
 AUTHOR
 ACKNOWLEDGEMENTS
 LICENSE AND COPYRIGHT
 DISCLAIMER OF WARRANTY
NAME
Math::ModInt  modular integer arithmetic
VERSION
This documentation refers to version 0.013 of Math::ModInt.
SYNOPSIS
use Math::ModInt qw(mod divmod qmod);
$a = mod(32, 127); # 32 (mod 127)
$b = $a>new(99); # 99 (mod 127)
$c = $a + $b; # 4 (mod 127)
$d = $a**2  $b/$a; # 120 (mod 127)
($i, $e) = divmod(32, 5); # 6, mod(2, 5)
$m = $d>modulus; # 127
$r = $d>residue; # 120
$s = $d>signed_residue; # 7
$t = "$a"; # 'mod(32, 127)'
use Math::BigRat;
$q = Math::BigRat>new('2/3');
$f = qmod($q, 5); # 4 (mod 5)
DESCRIPTION
Math::ModInt provides overloaded operators for modular integer arithmetic. Math::ModInt objects represent integer residue classes. These objects can be used in arithmetic expressions just like Perl numbers. Math::ModInt objects are immutable. Mutators like +=
will replace an object rather than change its state.
In mixed expressions with Math::ModInt objects and ordinary numbers the numbers are interpreted as their residue class modulo the modulus of the rest of the expression. Different moduli must not be mixed, though.
There are different implementations, optimized for moduli of a particular size or using a particular math library. The base module will transparently choose a suitable backend whenever a constructor is called.
Application Interface
Constructors
 new

Called as a class method,
Math::ModInt>new($int, $modulus)
creates a new object of a subclass appropriate for the given modulus and current platform. The modulus must be a positive integer value.Called as an object method,
$x>new($int)
creates a new object sharing both its type and modulus with the invocant object$x
.  new2

The constructor method
new2
is called exactly likenew
but it returns two values: an integer division result and a modular integer object.  mod

For convenience,
mod
can be imported as an abbreviation for the class method constructor;mod($int, $modulus)
is equivalent toMath::ModInt>new($int, $modulus)
. Note thatmod
has to be called as a plain function, not like a method.  divmod

The
divmod
function can be imported, too. It takes two integers likemod
but it returns two values: an integer division result and a modular integer object. Thusdivmod($int, $modulus)
is equivalent toMath::ModInt>new2($int, $modulus)
.  qmod

Another importable constructor function is
qmod
. It can convert rational numbers to modular integers of a given modulus if the denominator is coprime to that modulus. The expressionqmod($rat, $modulus)
is equivalent tomod($rat>numerator, $modulus) / mod($rat>denominator, $modulus)
. Note that$rat
must be an object withnumerator
anddenominator
methods, like e.g. an instance of Math::BigRat.Note also that mixed expressions with modular integers and rational numbers are not permitted. Always convert rational numbers explicitly with
qmod
.  undefined

This method returns the
undefined
placeholder object representing undefined results in the domain of modular integer arithmetic, such as from division by an operand not coprime to the modulus. See Math::ModInt::Event for how to control whether this object or other ways to report arithmetic faults should be employed.
Operators
+  * / ** == !=

Addition, negation, subtraction, multiplication, division, exponentiation with integer exponents, and equivalence operators are provided through overloaded perl operators. Division or exponentiation with negative exponents may trigger an
UndefinedResult
event and yield anundefined
result.Operands must either have the same modulus or be plain integers, except for equality/inequality checks. Operands with different moduli may be compared and are considered unequal.
For other exceptions to the requirement of identical moduli, see Math::ModInt::ChineseRemainder.
Note that neither the modulo operator
%
nor bitoperations&  ^ << >>
nor order relations< <= > >= <=>
are defined.  inverse

The object method
$x>inverse
returns the multiplicative modular inverse of$x
, if it exists, otherwise theundefined
placeholder. (y is the modular inverse of x modulo m if x * y is equivalent to 1 modulo m.)
Accessors
 is_defined
 is_undefined

The object methods
$x>is_defined
and$x>is_undefined
return boolean values checking whether$x
is a proper residue class object or theundefined
placeholder. Besidesas_string
, these are the only legal accessors for theundefined
placeholder.  modulus

The object method
$x>modulus
returns the modulus of the residue class the object represents.  residue

The object method
$x>residue
returns the normalized residue of the residue class the object represents. Its value is chosen as if it was a division remainder, i.e. between zero (inclusive) and the modulus (exclusive).  signed_residue

The object method
$x>signed_residue
returns a representative of the residue class the object represents, chosen as close to zero as possible. In case of a tie, i.e. when the modulus is an even number and the residue is half the modulus, the negative value is given preference (like in many native signed integer formats).  centered_residue

The object method
$x>centered_residue
is equivalent to$x>signed_residue
except that the positive value is given preference when the residue is precisely half the modulus.  is_zero
 is_not_zero

The object methods
$x>is_zero
and$x>is_not_zero
return boolean values checking whether$x
is the zero element of its ring, i.e.0 == $x>residue
). Either one of these methods can be called implicitly when a Math::ModInt object is being used in boolean context.  as_string

The object method
$x>as_string
returns a string representation of$x
. It will be in the formmod(residue, modulus)
(similar to the constructor) in case of proper residue classes, ormod(?, ?)
in case of theundefined
placeholder.
Miscellaneous methods
 optimize_time

Some implementations can employ different optimization strategies for either time or space efficiency. Time efficiency aims to speed up repetitive calculations at the expense of memory space. Space efficiency aims to minimize the memory footprint at the expense of cpu cycles. Where such a distinction is available, separate choices can be made for each modulus.
The object method
$x>optimize_time
gives a hint to the implementation of$x
to prefer time over space efficiency for the modulus of$x
. It returns the object it was called with.  optimize_space

The object method
$x>optimize_space
gives a hint to the implementation of$x
to prefer space over time efficiency for the modulus of$x
. It returns the object it was called with.  optimize_default

The object method
$x>optimize_default
restores the default behaviour of the implementation of$x
with respect to its optimization strategy for the modulus of$x
. It returns the object it was called with. Defaults may depend on the modulus and may or may not be equivalent to one of the other strategy choices. They should, however, be reasonably secure to use on small systems, and thus lean more to space than time efficiency.
Implementation Interface
Math::ModInt offers a special interface for implementations, intended to simplify operator overloading. Implementations are subclasses overriding only a couple of methods, as listed below. The overload pragma should not explicitly be used in implementations adhering to this interface.
Implementations handle a restricted set of moduli, sometimes only one. Currently, these restrictions are known in the base module and hardcoded there. Future revisions of Math::ModInt may offer a registration mechanism with precedences to make platformspecific choices possible.
Mandatory Methods
 residue

This method should return the normalized residue as defined in the application interface.
 modulus

This method should return the modulus as defined in the application interface.
 _NEW

This constructor will be called either as a class method with two parameters residue and modulus, or as an object method with just one parameter residue. It should return a new object with the given residue and modulus in the former case, or the given residue and the modulus of the invocant object in the latter case.
Note that the constructors mod and new of the application interface should not be overridden, as they need to switch implementations, depending on parameters rather than the package they are called from.
 _NEG

$x>_NEG
should return a new object representing$x
.  _INV

$x>_INV
should return a new object representing the modular inverse of$x
, if it exists, otherwiseMath::ModInt>undefined
.  _ADD

$x>_ADD($y)
should return a new object representing$x+$y
. The parameter$y
will always be an object of the same class and have the same modulus as$x
.  _SUB

$x>_SUB($y)
should return a new object representing$x$y
. The parameter$y
will always be an object of the same class and have the same modulus as$x
.  _MUL

$x>_MUL($y)
should return a new object representing$x*$y
. The parameter$y
will always be an object of the same class and have the same modulus as$x
.  _DIV

$x>_DIV($y)
should return a new object representing$x/$y
if it exists, otherwiseMath::ModInt>undefined
. The parameter$y
will always be an object of the same class and have the same modulus as$x
.  _POW

$x>_POW($y)
should return a new object representing$x ** $y
if it exists, otherwiseMath::ModInt>undefined
. The exponent$y
will always be an integer number. An undefined result means that the exponent was negative while$x
had no modular inverse.
Optional Methods
 _NEW2

This constructor method will be called like
_NEW
but it must return two values: an integer division result and the newly created modular integer object. It should be implemented if the underlying library offers an efficient way to calculate a quotient and remainder simultaneously.  optimize_time
 optimize_space
 optimize_default

These methods give hints for the optimization strategy for a particular modulus, as described in the application interface above. They do not need to be implemented.
DIAGNOSTICS
Some operations are not defined for all operands. For instance, division only makes sense if the denominator residue is coprime to the modulus. Operands with different moduli generally can not be combined in binary operations.
By default, operations with incompatible operands or undefined results consistently yield the Math::ModInt>undefined object, which will raise an exception upon modulus/residue inspection, but can be recognized by the boolean result of the is_defined/is_undefined methods. See Math::ModInt::Event for ways to alter this behaviour.
DEPENDENCIES
This module uses Math::BigInt for arbitraryprecision calculations. If you want control over which Math::BigInt backend is to be used, import Math::BigInt before Math::ModInt, like this:
use Math::BigInt try => 'GMP,Pari';
use Math::ModInt qw(mod);
The minimal required perl version is 5.6.
BUGS AND LIMITATIONS
Math::BigInt version 1.99 can not be used together with this module, as the former has a severe bug with modular integer arithmetic which is detected in our test suite. Math::BigInt version 1.991 has this issue resolved.
A little bit of effort has been put into making this module suite reasonably efficient even in the absence of convenient big integer libraries. For best performance, though, we recommend installing a fast integer library such as Math::BigInt::GMP together with Math::ModInt.
Currently, the choice of Math::ModInt backend is hardwired into the main module, for the sake of simplicity. Please contact the maintainer if you intend to use a backend not from this distribution, so that something clever can be done about it.
Math::ModInt has settled down a bit after a decade of beta testing. The interface may now be considered stable and new features will not intentionally break or remove existing ones from this point.
Bug reports and suggestions are always welcome. Please submit them through the github issue tracker, https://github.com/mhasch/perlMathModInt/issues .
More information for potential contributors can be found in the file named CONTRIBUTING in this distribution.
SEE ALSO
The subject "modular arithmetic" on Wikipedia. http://en.wikipedia.org/wiki/Modular_arithmetic
AUTHOR
Martin Becker, <beckercpanmp at cozap.com>
ACKNOWLEDGEMENTS
Thanks go to Ilya Zakharevich for the overload package, and for mentioning this package ages before it was actually written, in perlnumber.pod. I also appreciate the role of cpantesters.org in quality assurance for CPAN.
If you find something cool you can do with Math::ModInt you like to share with others, you are welcome to submit your code for the examples section, as well as your name or chosen identity for the hall of fame.
LICENSE AND COPYRIGHT
Copyright (c) 20092021 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 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.