Utility classes for multi-modular algorithms

class sage.arith.multi_modular.MultiModularBasis

Bases: sage.arith.multi_modular.MultiModularBasis_base

Class used for storing a MultiModular bases of a fixed length.

class sage.arith.multi_modular.MultiModularBasis_base

Bases: object

This class stores a list of machine-sized prime numbers, and can do reduction and Chinese Remainder Theorem lifting modulo these primes.

Lifting implemented via Garner’s algorithm, which has the advantage that all reductions are word-sized. For each \(i\), precompute \(\prod_j=1^{i-1} m_j\) and \(\prod_j=1^{i-1} m_j^{-1} (mod m_i)\).

This class can be initialized in two ways, either with a list of prime moduli or an upper bound for the product of the prime moduli. The prime moduli are generated automatically in the second case.

EXAMPLES:

sage: from sage.arith.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base([3, 5, 7]); mm
MultiModularBasis with moduli [3, 5, 7]

sage: height = 52348798724
sage: mm = MultiModularBasis_base(height); mm
MultiModularBasis with moduli [...]
sage: mm.prod() >= 2*height
True

crt(b)

Calculate lift mod \(\prod_{i=0}^{len(b)-1} m_i\).

In the case that offset > 0, z[j] remains unchanged mod \(\prod_{i=0}^{offset-1} m_i\)

INPUT:

• b - a list of length at most self.n

OUTPUT:

Integer z where \(z = b[i] mod m_i\) for 0 <= i < len(b)

EXAMPLES:

sage: from sage.arith.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base([10007, 10009, 10037, 10039, 17351])
sage: res = mm.crt([3,5,7,9]); res
8474803647063985
sage: res % 10007
3
sage: res % 10009
5
sage: res % 10037
7
sage: res % 10039
9

extend_with_primes(plist, partial_products=None, check=True)

Extend the stored list of moduli with the given primes in plist.

EXAMPLES:

sage: from sage.arith.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base([1009, 10007]); mm
MultiModularBasis with moduli [1009, 10007]
sage: mm.extend_with_primes([10037, 10039])
4
sage: mm
MultiModularBasis with moduli [1009, 10007, 10037, 10039]

list()

Return a list with the prime moduli.

EXAMPLES:

sage: from sage.arith.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base([46307, 10007])
sage: mm.list()
[46307, 10007]

partial_product(n)

Return a list containing precomputed partial products.

EXAMPLES:

sage: from sage.arith.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base([46307, 10007]); mm
MultiModularBasis with moduli [46307, 10007]
sage: mm.partial_product(0)
46307
sage: mm.partial_product(1)
463394149

precomputation_list()

Return a list of the precomputed coefficients \(\prod_j=1^{i-1} m_j^{-1} (mod m_i)\) where \(m_i\) are the prime moduli.

EXAMPLES:

sage: from sage.arith.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base([46307, 10007]); mm
MultiModularBasis with moduli [46307, 10007]
sage: mm.precomputation_list()
[1, 4013]

prod()

Return the product of the prime moduli.

EXAMPLES:

sage: from sage.arith.multi_modular import MultiModularBasis_base
sage: mm = MultiModularBasis_base([46307]); mm
MultiModularBasis with moduli [46307]
sage: mm.prod()
46307
sage: mm = MultiModularBasis_base([46307, 10007]); mm
MultiModularBasis with moduli [46307, 10007]
sage: mm.prod()
463394149

class sage.arith.multi_modular.MutableMultiModularBasis

Bases: sage.arith.multi_modular.MultiModularBasis

Class used for performing multi-modular methods, with the possibility of removing bad primes.

next_prime()

Pick a new random prime between the bounds given during the initialization of this object, update the precomputed data, and return the new prime modulus.

EXAMPLES:

sage: from sage.arith.multi_modular import MutableMultiModularBasis
sage: mm = MutableMultiModularBasis([10007])
sage: p = mm.next_prime()
sage: p > 10007
True
sage: mm.list() == [10007, p]
True

replace_prime(ix)

Replace the prime moduli at the given index with a different one, update the precomputed data accordingly, and return the new prime.

INPUT:

• ix – index into list of moduli

OUTPUT: the new prime modulus

EXAMPLES:

sage: from sage.arith.multi_modular import MutableMultiModularBasis
sage: mm = MutableMultiModularBasis([10007, 10009, 10037, 10039])
sage: mm
MultiModularBasis with moduli [10007, 10009, 10037, 10039]
sage: prev_prod = mm.prod(); prev_prod
10092272478850909
sage: mm.precomputation_list()
[1, 5004, 6536, 6060]
sage: mm.partial_product(2)
1005306552331
sage: p = mm.replace_prime(1)
sage: mm.list() == [10007, p, 10037, 10039]
True
sage: mm.prod()*10009 == prev_prod*p
True
sage: precomputed = mm.precomputation_list()
sage: precomputed == [prod(Integers(mm[i])(1 / mm[j])
....:                      for j in range(i))
....:                 for i in range(4)]
True
sage: mm.partial_product(2) == prod(mm.list()[:3])
True