Chinese Remainder Theory (CRT)CRT allows us to determine n, giving a number of equations, such as n mod a = w, n mod b = y, n mod c = z, where we know [a,b,c] and [w,x,y] and where there are no common factors in the values a, b and c [gcd(a,b,c)=1]: |
Quiz
Can you solve this [Try]:
x mod 3 = 2 x mod 5 = 3 x mod 11 = 2
Examples
The following are some examples:
- x mod 3 = 2, x mod 5 = 2, x mod 7 = 2 ([3,5,7][2,3,2])?. Try
- x mod 3 = 2, x mod 7 = 4, x mod 13 = 11 ([3,7,13] [2,4,11])?. Try
- ([3,7,17,14],[2,5,13,8]). Try
- ([3,7,17,19,11,23],[2,5,13,8,11,20]). Try
Code
from functools import reduce import math nval = [3,5,7] aval = [2,3,2] def chinese_remainder(n, a): sum = 0 prod = reduce(lambda a, b: a*b, n) for n_i, a_i in zip(n, a): p = prod / n_i sum += a_i * mul_inv(p, n_i) * p return sum % prod def mul_inv(a, b): b0 = b x0, x1 = 0, 1 if b == 1: return 1 while a > 1: try: q = a / b a, b = b, a%b x0, x1 = x1 - q * x0, x0 except: print("Bad N values (check no common factors in N vals)") return 0 if x1 < 0: x1 += b0 return x1 def gcd(L): return reduce(math.gcd, L) n = nval a = aval g = gcd(nval) print("GCD of N values: "+ str(g)) if (g>1): print("Cannot compute - check your N values for a common factor") else: print("Result (x) is: "+str(chinese_remainder(n, a))+"\n") count=0 for str1 in nval: print("x mod "+str(str1)+"="+str(aval[count])) count=count+1