CRT

def CRT(c1, n1, c2, n2, c3, n3):
    N = n1 * n2 * n3
    N1 = N / n1
    N2 = N / n2
    N3 = N / n3

    d1 = N1 mod n1
    d1 = modInverse(N1, n1)
    d2 = modInverse(N2, n2)
    d3 = modInverse(N3, n3)

    x = c1*N1*d1 + c2*N2*d2 + c3*N3*d3 #mod N

    modInverse(x, N)


#http://www.di-mgt.com.au/crt.html
#There are three recipients with public keys (87,3), (115,3) and (187,3). That is, we have e=3 and

#c1 = 103 mod 87 = 43; c2 = 103 mod 115 = 80; c3 = 103 mod 187 = 65

#N = n1n2n3 = 87 x 115 x 187 = 1870935
#N1 = N/n1 = 115x187 = 21505; d1 = 21505-1 (mod 87) = 49
#N2 = N/n2 = 87x187 = 16269; d2 = 16269-1 (mod 115) = 49
#N3 = N/n3 = 87x115 = 10005; d3 = 10005-1 (mod 187) = 2
#x = c1N1d1 + c2N2d2 + c3N3d3 (mod N)
#x = (43.21505.49) + (80.16269.49) + (65.10005.2) = 110386165 = 1000 (mod 1870935)