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