Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
Thank you very much! :) –  srcspider Feb 3 '11 at 11:45
add comment

Here is a much, much simpler way to immediately obtain the sought answer. Contrast the solution below to the much longer solution in your link, which involves calculations with much larger numbers and performs 4 inversions vs. the single simple inversion below. Always look for hidden innate symmetries in a problem before diving head-first into brute-force mechanical calculations! Here the key insight is that the equations split into pairs with obvious constant solutions, viz.

$\rm\quad\quad\quad\quad\quad x\equiv \ \ \ 2\ \ \:(mod\ 7),\ \ x\equiv \ \ \ 2\ \ \:(mod\ 11)\ \iff\ x\equiv \ \ \ 2\ \ (mod\ 77)$

$\rm\quad\quad\quad\quad\quad x\equiv -1\ \ (mod\ 5),\ \ x\equiv -1\ \ (mod\ 13)\ \iff\ x\equiv -1\ \ (mod\ 65)$

So we reduced the four original LHS equations to the two RHS equations. $\: $ Now we apply a simple version of the Chinese Remainder Theorem to solve the RHS equations. $\ $ By Easy CRT below

$\rm\quad\quad\quad\quad\quad x\equiv\ 2 + 77\ \bigg[\displaystyle\frac{-3}{77}\ mod\ 65\bigg]\ \ (mod\ 77\cdot65)$

Now $\rm\displaystyle\ \ \ \ \ mod\ \ 65:\ \ \ \ \ \frac{-3}{77}\ \equiv\ \frac{-3}{12}\ \equiv\ \frac{-1}4\ \equiv\ \frac{64}4\ \equiv\ 16$

Hence $\rm\ \ x\ \equiv\ 2 + 77\cdot 16\ \equiv\ 1234\ \ (mod\ 77\cdot 65)\quad\quad\ $ QED

THEOREM $\:$ (Easy CRT) $\rm\ \ $ If $\rm\ m,\:n\:$ are coprime integers then $\rm\ m^{-1}\ $ exists $\rm\ (mod\ n)\ \ $ and

$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ (mod\ m) \\ \rm x&\equiv&\rm\ b\ (mod\ n)\end{eqnarray} \ \iff\ \ x\ \equiv\ a + m\ \bigg[\frac{b-a}{m}\ mod\ n\:\bigg]\ \ (mod\ m\:n)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ m:\ x\ \equiv\ a + m\ [\,\cdots\,]\ \equiv\ a\:,\ $ and $\rm\ mod\ n\!\!:\ x\ \equiv\ a + (b-a)\ m/m\ \equiv\ b\:.$

$\rm (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ m\:n)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,\:n\ |\ x'-x\ \Rightarrow\ m\:n\ |\ x'-x\ \ $ since $\rm\ \:m,\:n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\:n\:.\quad $ QED

Note $\ $ Easy CRT is not only easy to apply, but also very easy to remember. Namely note $\rm\ x\equiv a\pmod m\iff x = a + m\,k,\:$ for some integer $\rm\:k\:$. This further satisfies the second congruence iff $\rm\:mod\ n\!:\ x = a + m\,k\equiv b$ $\iff$ $\rm k\:\equiv (b-a)/m,\ $ hence the "Easy CRT" solution. This enables the $(\Leftarrow)$ proof, i.e. fill in the dots in $\rm\:a + m\ [\,\cdots\,]\:$ so that it is $\rm\equiv b\pmod n\:$

Below is the solution you linked to on"Math Celebrity" (cached to avoid link rot).

enter image description here enter image description here

share|improve this answer
    
@Bill Dubuque: But the OP was just giving an example! Your solution is completely useless for any other, similar problem. Unless you can automate it, of course :-) –  TonyK Feb 3 '11 at 17:27
1  
@TonyK: Most certainly not true. Most math problems do have interesting structure, esp. problems that are designed for tests, competitions etc. In fact this is frequently true even in research problems. Indeed, speaking as a number theorist, I can tell you that methods like the above are very useful in practice. In mathematics, intuition always trumps brute force. –  Bill Dubuque Feb 3 '11 at 17:34
1  
@Bill Dubuque: Well, your methods might be much, much simpler for you. But if they require years of practice, they're not so useful for people like me (or, presumably, the OP). –  TonyK Feb 3 '11 at 18:05
1  
@Tonyk: The above solution can be understood by a bright high-school student. Simple optimizations like the above arise frequently in elementary number theoretical problems, so it is well-worth knowing them. –  Bill Dubuque Feb 3 '11 at 18:54
1  
@TonyK: The optimization I employed above is algorithmic and is frequently applicable in practice. But that was not my point in presenting the above. Rather, it was to emphasize conceptual vs. algorithmic thought - intuition vs. brute force. Mathematical problems are far from random. Typically they involve much structure and their solution requires insightful exploitation of such innate structure - something that cannot be algorithmic (indeed many math problems are algorithmically unsolvable - that's what makes them interesting). –  Bill Dubuque Feb 4 '11 at 0:37
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.