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 comments
Thank you very much for a good site
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.
Glad to be of help. I might do a few posts on cryptography
Leave a Comment