/ 
Math-ModInt-0.001
River stage one • 1 direct dependent • 1 total dependent
/ Math::ModInt::ChineseRemainder

NAME

Math::ModInt::ChineseRemainder - solving simultaneous integer congruences

VERSION

This documentation refers to version 0.001 of Math::ModInt::ChineseRemainder.

SYNOPSIS

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)

DESCRIPTION

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.

Calculations

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.

Precomputation cache management

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 takes a number and configures the maximal number of slots of the cache as that 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.

EXPORT

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.

DIAGNOSTICS

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).

SEE ALSO

BUGS AND LIMITATIONS

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.

AUTHOR

Martin Becker, <becker-cpan-mp@cozap.com>

LICENSE AND COPYRIGHT

Copyright (c) 2010 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.

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.