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.
About this entry
You’re currently reading “Chinese remainder theorem,” an entry on Shriphani Palakodety
- Published:
- 08.20.07 / 5pm
- Category:
- Mathematics, python
3 Comments
Jump to comment form | comments rss [?] | trackback uri [?]