Coverage for /usr/lib/python3/dist-packages/sympy/ntheory/modular.py: 16%

1from functools import reduce 

2from math import prod 

3 

4from sympy.core.numbers import igcdex, igcd 

5from sympy.ntheory.primetest import isprime 

6from sympy.polys.domains import ZZ 

7from sympy.polys.galoistools import gf_crt, gf_crt1, gf_crt2 

8from sympy.utilities.misc import as_int 

9 

10 

11def symmetric_residue(a, m): 

12 """Return the residual mod m such that it is within half of the modulus. 

13 

14 >>> from sympy.ntheory.modular import symmetric_residue 

15 >>> symmetric_residue(1, 6) 

16 1 

17 >>> symmetric_residue(4, 6) 

18 -2 

19 """ 

20 if a <= m // 2: 

21 return a 

22 return a - m 

23 

24 

25def crt(m, v, symmetric=False, check=True): 

26 r"""Chinese Remainder Theorem. 

27 

28 The moduli in m are assumed to be pairwise coprime. The output 

29 is then an integer f, such that f = v_i mod m_i for each pair out 

30 of v and m. If ``symmetric`` is False a positive integer will be 

31 returned, else \|f\| will be less than or equal to the LCM of the 

32 moduli, and thus f may be negative. 

33 

34 If the moduli are not co-prime the correct result will be returned 

35 if/when the test of the result is found to be incorrect. This result 

36 will be None if there is no solution. 

37 

38 The keyword ``check`` can be set to False if it is known that the moduli 

39 are coprime. 

40 

41 Examples 

42 ======== 

43 

44 As an example consider a set of residues ``U = [49, 76, 65]`` 

45 and a set of moduli ``M = [99, 97, 95]``. Then we have:: 

46 

47 >>> from sympy.ntheory.modular import crt 

48 

49 >>> crt([99, 97, 95], [49, 76, 65]) 

50 (639985, 912285) 

51 

52 This is the correct result because:: 

53 

54 >>> [639985 % m for m in [99, 97, 95]] 

55 [49, 76, 65] 

56 

57 If the moduli are not co-prime, you may receive an incorrect result 

58 if you use ``check=False``: 

59 

60 >>> crt([12, 6, 17], [3, 4, 2], check=False) 

61 (954, 1224) 

62 >>> [954 % m for m in [12, 6, 17]] 

63 [6, 0, 2] 

64 >>> crt([12, 6, 17], [3, 4, 2]) is None 

65 True 

66 >>> crt([3, 6], [2, 5]) 

67 (5, 6) 

68 

69 Note: the order of gf_crt's arguments is reversed relative to crt, 

70 and that solve_congruence takes residue, modulus pairs. 

71 

72 Programmer's note: rather than checking that all pairs of moduli share 

73 no GCD (an O(n**2) test) and rather than factoring all moduli and seeing 

74 that there is no factor in common, a check that the result gives the 

75 indicated residuals is performed -- an O(n) operation. 

76 

77 See Also 

78 ======== 

79 

80 solve_congruence 

81 sympy.polys.galoistools.gf_crt : low level crt routine used by this routine 

82 """ 

83 if check: 

84 m = list(map(as_int, m)) 

85 v = list(map(as_int, v)) 

86 

87 result = gf_crt(v, m, ZZ) 

88 mm = prod(m) 

89 

90 if check: 

91 if not all(v % m == result % m for v, m in zip(v, m)): 

92 result = solve_congruence(*list(zip(v, m)), 

93 check=False, symmetric=symmetric) 

94 if result is None: 

95 return result 

96 result, mm = result 

97 

98 if symmetric: 

99 return symmetric_residue(result, mm), mm 

100 return result, mm 

101 

102 

103def crt1(m): 

104 """First part of Chinese Remainder Theorem, for multiple application. 

105 

106 Examples 

107 ======== 

108 

109 >>> from sympy.ntheory.modular import crt1 

110 >>> crt1([18, 42, 6]) 

111 (4536, [252, 108, 756], [0, 2, 0]) 

112 """ 

113 

114 return gf_crt1(m, ZZ) 

115 

116 

117def crt2(m, v, mm, e, s, symmetric=False): 

118 """Second part of Chinese Remainder Theorem, for multiple application. 

119 

120 Examples 

121 ======== 

122 

123 >>> from sympy.ntheory.modular import crt1, crt2 

124 >>> mm, e, s = crt1([18, 42, 6]) 

125 >>> crt2([18, 42, 6], [0, 0, 0], mm, e, s) 

126 (0, 4536) 

127 """ 

128 

129 result = gf_crt2(v, m, mm, e, s, ZZ) 

130 

131 if symmetric: 

132 return symmetric_residue(result, mm), mm 

133 return result, mm 

134 

135 

136def solve_congruence(*remainder_modulus_pairs, **hint): 

137 """Compute the integer ``n`` that has the residual ``ai`` when it is 

138 divided by ``mi`` where the ``ai`` and ``mi`` are given as pairs to 

139 this function: ((a1, m1), (a2, m2), ...). If there is no solution, 

140 return None. Otherwise return ``n`` and its modulus. 

141 

142 The ``mi`` values need not be co-prime. If it is known that the moduli are 

143 not co-prime then the hint ``check`` can be set to False (default=True) and 

144 the check for a quicker solution via crt() (valid when the moduli are 

145 co-prime) will be skipped. 

146 

147 If the hint ``symmetric`` is True (default is False), the value of ``n`` 

148 will be within 1/2 of the modulus, possibly negative. 

149 

150 Examples 

151 ======== 

152 

153 >>> from sympy.ntheory.modular import solve_congruence 

154 

155 What number is 2 mod 3, 3 mod 5 and 2 mod 7? 

156 

157 >>> solve_congruence((2, 3), (3, 5), (2, 7)) 

158 (23, 105) 

159 >>> [23 % m for m in [3, 5, 7]] 

160 [2, 3, 2] 

161 

162 If you prefer to work with all remainder in one list and 

163 all moduli in another, send the arguments like this: 

164 

165 >>> solve_congruence(*zip((2, 3, 2), (3, 5, 7))) 

166 (23, 105) 

167 

168 The moduli need not be co-prime; in this case there may or 

169 may not be a solution: 

170 

171 >>> solve_congruence((2, 3), (4, 6)) is None 

172 True 

173 

174 >>> solve_congruence((2, 3), (5, 6)) 

175 (5, 6) 

176 

177 The symmetric flag will make the result be within 1/2 of the modulus: 

178 

179 >>> solve_congruence((2, 3), (5, 6), symmetric=True) 

180 (-1, 6) 

181 

182 See Also 

183 ======== 

184 

185 crt : high level routine implementing the Chinese Remainder Theorem 

186 

187 """ 

188 def combine(c1, c2): 

189 """Return the tuple (a, m) which satisfies the requirement 

190 that n = a + i*m satisfy n = a1 + j*m1 and n = a2 = k*m2. 

191 

192 References 

193 ========== 

194 

195 .. [1] https://en.wikipedia.org/wiki/Method_of_successive_substitution 

196 """ 

197 a1, m1 = c1 

198 a2, m2 = c2 

199 a, b, c = m1, a2 - a1, m2 

200 g = reduce(igcd, [a, b, c]) 

201 a, b, c = [i//g for i in [a, b, c]] 

202 if a != 1: 

203 inv_a, _, g = igcdex(a, c) 

204 if g != 1: 

205 return None 

206 b *= inv_a 

207 a, m = a1 + m1*b, m1*c 

208 return a, m 

209 

210 rm = remainder_modulus_pairs 

211 symmetric = hint.get('symmetric', False) 

212 

213 if hint.get('check', True): 

214 rm = [(as_int(r), as_int(m)) for r, m in rm] 

215 

216 # ignore redundant pairs but raise an error otherwise; also 

217 # make sure that a unique set of bases is sent to gf_crt if 

218 # they are all prime. 

219 # 

220 # The routine will work out less-trivial violations and 

221 # return None, e.g. for the pairs (1,3) and (14,42) there 

222 # is no answer because 14 mod 42 (having a gcd of 14) implies 

223 # (14/2) mod (42/2), (14/7) mod (42/7) and (14/14) mod (42/14) 

224 # which, being 0 mod 3, is inconsistent with 1 mod 3. But to 

225 # preprocess the input beyond checking of another pair with 42 

226 # or 3 as the modulus (for this example) is not necessary. 

227 uniq = {} 

228 for r, m in rm: 

229 r %= m 

230 if m in uniq: 

231 if r != uniq[m]: 

232 return None 

233 continue 

234 uniq[m] = r 

235 rm = [(r, m) for m, r in uniq.items()] 

236 del uniq 

237 

238 # if the moduli are co-prime, the crt will be significantly faster; 

239 # checking all pairs for being co-prime gets to be slow but a prime 

240 # test is a good trade-off 

241 if all(isprime(m) for r, m in rm): 

242 r, m = list(zip(*rm)) 

243 return crt(m, r, symmetric=symmetric, check=False) 

244 

245 rv = (0, 1) 

246 for rmi in rm: 

247 rv = combine(rv, rmi) 

248 if rv is None: 

249 break 

250 n, m = rv 

251 n = n % m 

252 else: 

253 if symmetric: 

254 return symmetric_residue(n, m), m 

255 return n, m