2
$\begingroup$

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?

2 Answers 2

4

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

11

Here is a 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 search for hidden innate structure in a problem before diving head-first into brute-force mechanical calculations!

The key insight is: the congruences split into pairs with obvious constant solutions by CCRT, viz.

$\begin{align}\rm\quad\quad\quad\quad\quad x\equiv \ \ \ 2\ \ \:(mod\ 7),\ \ x\equiv \ \ \ 2\ \ \:(mod\ 11)\ \iff\ x\equiv \ \ \ \color{#0a0}2\ \ (mod\ \color{#0a0}{77})\\[0.3em] \rm\quad\quad\quad\quad\quad x\equiv -1\ \ (mod\ 5),\,\ \ x\equiv\ {-}1\ \ (mod\ 13)\ \iff\ x\equiv \color{#c00}{-1}\ \ (mod\ \color{#c00}{65})\end{align}$

So we reduced the above four original LHS equations to the above two RHS equations, which are easy to solve by CRT = Chinese Remainder Theorem. $ $ Indeed, applying Easy CRT below

$\rm\quad\quad\quad\quad\quad x\equiv\ \color{#0a0}{2 + 77}\ \bigg[\displaystyle\frac{\color{#c00}{-1}-\color{#0a0}2}{\color{#0a0}{77}}\ mod\,\, \color{#c00}{65}\bigg]\,\ \ (mod\ 77\cdot65)$

In the brackets $\,\rm\displaystyle\left[\, mod\ \ 65\!:\ \ \frac{-3}{77} \equiv \frac{-3}{12} \equiv \frac{-1}4 \equiv \frac{64}4 \equiv \color{#d0f}{16}\,\right]\quad $ (see Beware below)

This yields $\rm\ \ x\ \equiv\ \color{#0a0}{2 + 77}\,[\,\color{#d0f}{16}\,] \equiv 1234\,\ \ (mod\ 77\cdot 65)\quad $ QED


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

$\rm\displaystyle\qquad\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\,\ mn)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,n\ |\ x'-x\ \Rightarrow\ mn\ |\ x'-x\ \ $ since $\rm\ \:m,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = mn\ \ \ $ 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 formula. This explains the $(\Leftarrow)$ proof: $ $ fill in the dots in $\rm\:x\equiv a + m\ [\,\cdots\,]\:$ to make $\rm\,x\equiv b\pmod{\! n}$

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

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

enter image description here enter image description here

  • 0
    @Code Where are you stuck?2012-11-02