sympy/ntheory/modular.py

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