Chinese remainder theorem

Have a look at this. I found this question in my neighbour’s CS book. He is a CS student and his college’s introductory CS course is taught in C (Sadly I don’t know C :( )

import nzmath.gcd

def crt(xl,ml):

    k = len(xl)

    m = ml[0]

    x = xl[0]

    for i in range(1,k):

        u,v,d = gcd.extgcd(m,ml[i])

        if d > 1:

            raise Error

            x = u*m*xl[i] + v*l[i]*x

            m = m*ml[i]

            x = x%m

    return x

There seemingly is an RSA based on the CRT but I don’t know about that. This question really got me to think.

3 responses to “Chinese remainder theorem”

  1. realleaws

    Thank you very much for a good site

  2. Avradip

    Dude u made my day…. i was searching for some CRT code online… here u are (too lazy to write myself ;) )…
    By the way hope u know by how CRT is used in RSA… that’s really a classic example which shows how important is CRT.

Leave a Reply


*