My Weblog

Blog about programming and math

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]
                [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 ] 

July 13, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: