Math::ModInt::ChineseRemainder - solving simultaneous integer congruences
This documentation refers to version 0.013 of Math::ModInt::ChineseRemainder.
use Math::ModInt qw(mod);
use Math::ModInt::ChineseRemainder qw(cr_combine cr_extract);
my $a = mod(42, 127); # 42 (mod 127)
my $b = mod(24, 128); # 24 (mod 128)
my $c = cr_combine($a, $b); # 2328 (mod 16256)
my $d = cr_extract($c, 127); # 42 (mod 127)
The intersection of two or more integer residue classes is either empty or another integer residue class modulo the least common multiple of their moduli. The Chinese remainder theorem states that this class exists and is in fact unique if those moduli are pairwise coprime, and explicit methods are known that will find it. Some of these methods can be extended to arbitrary moduli, resulting in general algorithms to solve simultaneous modular integer congruences or prove them to be unsolvable.
Math::ModInt::ChineseRemainder is a Perl implementation of such a generalized method. Like Math::ModInt, it should work for moduli of any size Math::BigInt can handle.
The subroutine cr_combine takes a list of Math::ModInt objects (modints) and returns one modint. The result will be either the modint representing the common residue subclass of the given modints, or the undefined modint if no such residue class exists. The result will always be defined if no two moduli have a common divisor greater than 1. If defined, the result modulus will be the least common multiple of all moduli.
The subroutine cr_extract is a kind of reverse operation of cr_combine in that it can extract modints with smaller moduli from a combined modint. It takes a Math::ModInt object and a new modulus, and returns a modint reduced to the new modulus, if that was a divisor of the original modulus, otherwise the undefined modint. In terms of residue classes the returned residue class is the superset of the original one with the given modulus.
Some calculations performed by cr_combine are only dependent on the set of moduli involved. In order to save time when the same moduli are used again -- which is a fairly typical use case --, these intermediate results are stored in a cache for later perusal. A couple of class methods can be used to inspect or change some aspects of this caching mechanism.
The class method cache_size returns the current maximal number of slots the cache is configured to use.
The class method cache_level returns the actual number of slots currently in use in the cache.
The class method cache_flush removes all items currently in the cache, releasing the memory used for their storage. It returns 0.
The class method cache_resize configures the maximal number of slots of the cache as the given value, which it also returns. If the new size is less than the number of slots already in use, items in excess of that number are removed immediately. If the new size is zero, caching is altogether disabled.
By default, nothing is exported into the caller's namespace. The subroutines cr_combine and cr_extract can be imported explicitly.
The class methods dealing with cache management must always be qualified with the class name.
There are no diagnostic messages specific to this module. Operations with undefined results return the undefined object unless the UndefinedResult event is trapped (see Math::ModInt::Event).
The subject "Chinese remainder theorem" in Wikipedia. http://en.wikipedia.org/Chinese_remainder_theorem
The current implementation is not rigidly optimized for performance. It does, however, cache some computed values to speed up repeated calculations with the same set of moduli. The interface to inspect and modify this caching behaviour should not be considered final.
Martin Becker, <becker-cpan-mp at cozap.com>
Copyright (c) 2010-2021 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).
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::ModInt, copy and paste the appropriate command in to your terminal.
perl -MCPAN -e shell
For more information on module installation, please visit the detailed CPAN module installation guide.