## Chinese remainder theorem implementation in haskell

Chinese remainder theorem is one of the most important algorithm is modular arithmetics. Suppose n1, n2, …, nk are positive integers which are pairwise coprime. Then, for any given integers a1,a2, …, ak, there exists an integer x solving the system of simultaneous congruences

x= a1 ( mod n1)

x= a2 (mod n2)

.

.

x = ak (mod nk)

The solution x can be found as using the extended Euclidean algorithm. We take product of all n_i for i = 1..k. N= n_1*n_2…….n_k. Since all n_i are pairwise coprime [ if all n_i’s are pairwise coprime then none of n_i’s will have common prime factor ] then for all i , n_i and N/n_i will be coprime. Using extended Euclidean algorithm we can find r_i and s_i such that r_i*n_i + s_i *N/n_i = gcd (n_i,N/n_i). Since n_i and N/n_i are coprime so r_i*n_i + s_i*N/n_i=1.s_i*N/n_i=1 (mod n_i ) and s_i*N/n_i=0 (mod n_j) for all j /= i.Using this result, one solution of system is Sum (a_i*s_i*N/n_i ) for i=1..k.A Haskell implementation of CRT.

extended_gcd:: Integer->Integer->[Integer] extended_gcd a b | mod a b == 0 = [0,1,b] | otherwise = [y,x-y*(div a b),z] where [x,y,z] = extended_gcd b (mod a b) chineseremainder :: [Integer]->[Integer]->Integer chineseremainder as ns = let prod = product ns ls = [extended_gcd x (div prod x) !! 1 |x<- ns] in sum [ div (x*y*prod) z | (x,y,z)<- zip3 as ls ns ]

No comments yet.

## Leave a Reply