Monday 21 October 2013

calculus - Getting an X for Chinese Remainder Theorem (CRT)



how do I get modulo equations to satisfy a given X in CRT.



For example say I have X = 1234. I choose mi as 5, 7, 11, 13. This satisfies the simple requirements of Mignotte's threshold secret sharing scheme. More precisely given in my example k = n = 4, and the product of any k - 1 is smaller then X how come simply computing the remainder of each won't give equations that solve to X = 1234.




In the case of the example,



x = 4 mod 5
x = 2 mod 7
x = 2 mod 11
x = 12 mod 13


Which resolves to 31264 (won't CRT produce the smallest?)




Any hints?


Answer



The final result of the CRT calculation must be reduced modulo 5 x 7 x 11 x 13 = 5005. This gives the correct answer.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...