forked from sympy/sympy
-
Notifications
You must be signed in to change notification settings - Fork 1
/
modular.py
63 lines (47 loc) · 1.28 KB
/
modular.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from sympy.core.numbers import igcdex
def crt(m, v, symmetric=False):
"""Chinese Remainder Theorem.
The integers in m are assumed to be pairwise coprime. The output
is then an integer f, such that f = v_i mod m_i for each pair out
of v and m.
"""
mm = 1
for m_i in m:
mm *= m_i
result = 0
for m_i, v_i in zip(m, v):
e = mm // m_i
s, t, g = igcdex(e, m_i)
c = v_i*s % m_i
result += c*e
result %= mm
if symmetric:
if result <= mm//2:
return result
else:
return result - mm
else:
return result
def crt1(m):
"""First part of chines remainder theorem, for multiple application. """
mm, e, s = 1, [], []
for m_i in m:
mm *= m_i
for m_i in m:
e.append(mm // m_i)
s.append(igcdex(e[-1], m_i)[0])
return mm, e, s
def crt2(m, v, mm, e, s, symmetric=False):
"""Second part of Chinese Remainder Theorem, for multiple application. """
result = 0
for m_i, v_i, e_i, s_i in zip(m, v, e, s):
c = v_i*s_i % m_i
result += c*e_i
result %= mm
if symmetric:
if result <= mm // 2:
return result
else:
return result - mm
else:
return result