Revision history [back]
 | 1 | initial version |
One way to fix that would be, in the file
to replace calls such as xx.parent() with parent(xx).
One would need to make sure this does not slow things down. If it does,
then maybe first trying xx.parent(), and then, if that fails, parent(xx),
would mitigate the slowdown.
To make things work now, start with the following and then run your code.
from sage.structure.coerce import py_scalar_to_element
from sage.arith.misc import XGCD
def CRT_list(values, moduli=None):
r"""
Given a list ``values`` of elements and a list of corresponding
``moduli``, find a single element that reduces to each element of
``values`` modulo the corresponding moduli.
This function can also be called with one argument, each element
of the list is a :mod:`modular integer <sage.rings.finite_rings.integer_mod>`.
In this case, it returns another modular integer.
.. SEEALSO::
- :func:`crt`
EXAMPLES::
sage: CRT_list([2,3,2], [3,5,7])
23
sage: x = polygen(QQ)
sage: c = CRT_list([3], [x]); c
3
sage: c.parent()
Univariate Polynomial Ring in x over Rational Field
It also works if the moduli are not coprime::
sage: CRT_list([32,2,2],[60,90,150])
452
But with non coprime moduli there is not always a solution::
sage: CRT_list([32,2,1],[60,90,150])
Traceback (most recent call last):
...
ValueError: no solution to crt problem since gcd(180,150) does not divide 92-1
Call with one argument::
sage: x = CRT_list([mod(2,3),mod(3,5),mod(2,7)]); x
23
sage: x.parent()
Ring of integers modulo 105
The arguments must be lists::
sage: CRT_list([1,2,3],"not a list")
Traceback (most recent call last):
...
ValueError: arguments to CRT_list should be lists
sage: CRT_list("not a list",[2,3])
Traceback (most recent call last):
...
ValueError: arguments to CRT_list should be lists
The list of moduli must have the same length as the list of elements::
sage: CRT_list([1,2,3],[2,3,5])
23
sage: CRT_list([1,2,3],[2,3])
Traceback (most recent call last):
...
ValueError: arguments to CRT_list should be lists of the same length
sage: CRT_list([1,2,3],[2,3,5,7])
Traceback (most recent call last):
...
ValueError: arguments to CRT_list should be lists of the same length
TESTS::
sage: CRT([32r,2r,2r],[60r,90r,150r])
452
sage: from numpy import int8 # needs numpy
sage: CRT_list([int8(2), int8(3), int8(2)], [int8(3), int8(5), int8(7)]) # needs numpy
23
sage: from gmpy2 import mpz
sage: CRT_list([mpz(2),mpz(3),mpz(2)], [mpz(3),mpz(5),mpz(7)])
23
Tests for call with one argument::
sage: x = CRT_list([mod(2,3)]); x
2
sage: x.parent()
Ring of integers modulo 3
sage: x = CRT_list([]); x
0
sage: x.parent()
Ring of integers modulo 1
sage: x = CRT_list([2]); x
Traceback (most recent call last):
...
TypeError: if one argument is given, it should be a list of IntegerMod
Make sure we are not mutating the input lists::
sage: xs = [1,2,3]
sage: ms = [5,7,9]
sage: CRT_list(xs, ms)
156
sage: xs
[1, 2, 3]
sage: ms
[5, 7, 9]
"""
if not isinstance(values, list) or (moduli is not None and not isinstance(moduli, list)):
raise ValueError("arguments to CRT_list should be lists")
return_mod = moduli is None
if return_mod:
from sage.rings.finite_rings.integer_mod import IntegerMod_abstract, Mod
if not values:
return Mod(0, 1)
if not all(isinstance(v, IntegerMod_abstract) for v in values):
raise TypeError("if one argument is given, it should be a list of IntegerMod")
if len(values) == 1:
return values[0]
moduli = [v.modulus() for v in values]
values = [v.lift() for v in values]
else:
assert moduli is not None
if len(values) != len(moduli):
raise ValueError("arguments to CRT_list should be lists of the same length")
if not values:
return ZZ.zero()
if len(values) == 1:
return parent(moduli[0])(values[0])
# The result is computed using a binary tree. In typical cases,
# this scales much better than folding the list from one side.
from sage.arith.functions import lcm
while len(values) > 1:
vs, ms = values[::2], moduli[::2]
for i, (v, m) in enumerate(zip(values[1::2], moduli[1::2])):
vs[i] = CRT(vs[i], v, ms[i], m)
ms[i] = lcm(ms[i], m)
values, moduli = vs, ms
if return_mod:
return Mod(values[0], moduli[0])
else:
return values[0] % moduli[0]
def crt(a, b, m=None, n=None):
r"""
Return a solution to a Chinese Remainder Theorem problem.
INPUT:
- ``a``, ``b`` -- two residues (elements of some ring for which
extended gcd is available), or two lists, one of residues and
one of moduli
- ``m``, ``n`` -- (default: ``None``) two moduli, or ``None``
OUTPUT:
If ``m``, ``n`` are not ``None``, returns a solution `x` to the
simultaneous congruences `x\equiv a \bmod m` and `x\equiv b \bmod
n`, if one exists. By the Chinese Remainder Theorem, a solution to the
simultaneous congruences exists if and only if
`a\equiv b\pmod{\gcd(m,n)}`. The solution `x` is only well-defined modulo
`\text{lcm}(m,n)`.
If ``a`` and ``b`` are lists, returns a simultaneous solution to
the congruences `x\equiv a_i\pmod{b_i}`, if one exists.
.. SEEALSO::
- :func:`CRT_list`
EXAMPLES:
Using ``crt`` by giving it pairs of residues and moduli::
sage: crt(2, 1, 3, 5)
11
sage: crt(13, 20, 100, 301)
28013
sage: crt([2, 1], [3, 5])
11
sage: crt([13, 20], [100, 301])
28013
You can also use upper case::
sage: c = CRT(2,3, 3, 5); c
8
sage: c % 3 == 2
True
sage: c % 5 == 3
True
Note that this also works for polynomial rings::
sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K.<a> = NumberField(x^3 - 7)
sage: R.<y> = K[]
sage: f = y^2 + 3
sage: g = y^3 - 5
sage: CRT(1, 3, f, g)
-3/26*y^4 + 5/26*y^3 + 15/26*y + 53/26
sage: CRT(1, a, f, g)
(-3/52*a + 3/52)*y^4 + (5/52*a - 5/52)*y^3 + (15/52*a - 15/52)*y + 27/52*a + 25/52
You can also do this for any number of moduli::
sage: # needs sage.rings.number_field
sage: K.<a> = NumberField(x^3 - 7)
sage: R.<x> = K[]
sage: CRT([], [])
0
sage: CRT([a], [x])
a
sage: f = x^2 + 3
sage: g = x^3 - 5
sage: h = x^5 + x^2 - 9
sage: k = CRT([1, a, 3], [f, g, h]); k
(127/26988*a - 5807/386828)*x^9 + (45/8996*a - 33677/1160484)*x^8
+ (2/173*a - 6/173)*x^7 + (133/6747*a - 5373/96707)*x^6
+ (-6/2249*a + 18584/290121)*x^5 + (-277/8996*a + 38847/386828)*x^4
+ (-135/4498*a + 42673/193414)*x^3 + (-1005/8996*a + 470245/1160484)*x^2
+ (-1215/8996*a + 141165/386828)*x + 621/8996*a + 836445/386828
sage: k.mod(f)
1
sage: k.mod(g)
a
sage: k.mod(h)
3
If the moduli are not coprime, a solution may not exist::
sage: crt(4, 8, 8, 12)
20
sage: crt(4, 6, 8, 12)
Traceback (most recent call last):
...
ValueError: no solution to crt problem since gcd(8,12) does not divide 4-6
sage: x = polygen(QQ)
sage: crt(2, 3, x - 1, x + 1)
-1/2*x + 5/2
sage: crt(2, x, x^2 - 1, x^2 + 1)
-1/2*x^3 + x^2 + 1/2*x + 1
sage: crt(2, x, x^2 - 1, x^3 - 1)
Traceback (most recent call last):
...
ValueError: no solution to crt problem since gcd(x^2 - 1,x^3 - 1) does not divide 2-x
sage: crt(int(2), int(3), int(7), int(11))
58
crt also work with numpy and gmpy2 numbers::
sage: import numpy # needs numpy
sage: crt(numpy.int8(2), numpy.int8(3), numpy.int8(7), numpy.int8(11)) # needs numpy
58
sage: from gmpy2 import mpz
sage: crt(mpz(2), mpz(3), mpz(7), mpz(11))
58
sage: crt(mpz(2), 3, mpz(7), numpy.int8(11)) # needs numpy
58
"""
if isinstance(a, list):
return CRT_list(a, b)
try:
f = (b - a).quo_rem
except (TypeError, AttributeError):
# Maybe there is no coercion between a and b.
# Maybe (b-a) does not have a quo_rem attribute
a = py_scalar_to_element(a)
b = py_scalar_to_element(b)
f = (b - a).quo_rem
g, alpha, beta = XGCD(m, n)
q, r = f(g)
if r != 0:
raise ValueError("no solution to crt problem since gcd(%s,%s) does not divide %s-%s" % (m, n, a, b))
from sage.arith.functions import lcm
x = a + q * alpha * py_scalar_to_element(m)
return x % lcm(m, n)
CRT = crt
