Utility classes for multi-modular algorithms¶

class sage.arith.multi_modular.MultiModularBasis[source]¶

Bases: MultiModularBasis_base

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

class sage.arith.multi_modular.MultiModularBasis_base[source]¶

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

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

Python

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

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

crt(b)[source]¶

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 – list of length at most self.n

OUTPUT:

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

EXAMPLES:

Sage

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

Python

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

extend_with_primes(plist, partial_products=None, check=True)[source]¶

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

EXAMPLES:

Sage

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]

Python

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

list()[source]¶

Return a list with the prime moduli.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> from sage.arith.multi_modular import MultiModularBasis_base
>>> mm = MultiModularBasis_base([Integer(46307), Integer(10007)])
>>> mm.list()
[46307, 10007]

partial_product(n)[source]¶

Return a list containing precomputed partial products.

EXAMPLES:

Sage

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

Python

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

precomputation_list()[source]¶

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

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]

Python

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

prod()[source]¶

Return the product of the prime moduli.

EXAMPLES:

Sage

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

Python

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

class sage.arith.multi_modular.MutableMultiModularBasis[source]¶

Bases: MultiModularBasis

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

next_prime()[source]¶

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

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

Python

>>> from sage.all import *
>>> from sage.arith.multi_modular import MutableMultiModularBasis
>>> mm = MutableMultiModularBasis([Integer(10007)])
>>> p = mm.next_prime()
>>> Integer(1024) < p < Integer(32768)
True
>>> p != Integer(10007)
True
>>> mm.list() == [Integer(10007), p]
True

replace_prime(ix)[source]¶

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

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

Python

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