Martin Becker >
Math-ModInt >
Math::ModInt::ChineseRemainder

Module Version: 0.007
Math::ModInt::ChineseRemainder - solving simultaneous integer congruences

This documentation refers to version 0.007 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.

*cr_combine*-
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. *cr_extract*-
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.

*cache_size*-
The class method

`cache_size`

returns the current maximal number of slots the cache is configured to use. *cache_level*-
The class method

`cache_level`

returns the actual number of slots currently in use in the cache. *cache_flush*-
The class method

`cache_flush`

removes all items currently in the cache, releasing the memory used for their storage. It returns 0. *cache_resize*-
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).

- Math::ModInt
- 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@cozap.com>

Copyright (c) 2010-2012 by Martin Becker. All rights reserved.

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.6.0 or, at your option, any later version of Perl 5 you may have available.

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.

syntax highlighting: