I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem.

Due to the system being modulo a non-prime (in my problem, I have p, a large prime, but in this particular part of the problem, this system is modulo p-1), obviously many numbers will not have modular inverses- so I turned to the Chinese Remainder Theorem, which is perfect for this issue.

I proceeded in the manner described on page 20 and 21 of the following thesis (side note- the assignment I'm working on is similar to the one in this thesis- a discrete log problem): http://howelljs.people.cofc.edu/math/msthesis.pdf. What I'm doing is constructing a matrix, and an answer vector. I'm 99% sure that I've done this correctly- I've verified that the matrix satisfies all of my criteria.

Once I have the system, which is mod p-1, I solve it modulo each of the factors of p-1, as described in the above link. In my case, the factors of p-1 are 2, 2, 2, 23, and 59407 (I think the multiple factors of 2 may be what's giving me trouble here).

At this point, I have 3 result vectors- one for the system mod 2, one for the system mod 23, and one for the system mod 59407. Accoring to the Chinese Remainder Theorem, I should be able to take the $i^{th}$ element of each result vector, as well as a vector containing my bases (2, 23, 59407) and construct the $x = L_i$ that would satisfy each congruence. Here's what I mean:

My original system looks like this:

$\begin{matrix} 0 & 5 & 4 & 1 \\ 1 & 7 & 0 & 2\\ 8 & 1 & 0 & 2\\ 10 & 5 & 1 &0 \end{matrix}$*$\begin{matrix} L_1\\L_2\\L_3\\L_4 \end{matrix}$=$\begin{matrix} 2946321 \\ 5851213 \\ 2563617\\10670279 \end{matrix}$ $\pmod{10930888}$

And when I solve it modulo each factor (2, 23, 59407) I get the following $L_i$ vectors:

$\begin{matrix} 0\\1\\0\\0 \end{matrix}\pmod2$ and $\begin{matrix} 1\\1\\12\\14\end{matrix}\pmod{23}$ and $\begin{matrix} 14087\\1\\14365\\37320 \end{matrix}\pmod{59407}$

So now, for example, I can construct $L_1$ by taking the 1st value from each result vector, and the bases, and construct a mini system of congruences:

  • $0=x\pmod{2}$
  • $1=x\pmod{23}$
  • $14087=x\pmod{59407}$

I found a Chinese Remainder Theorem function online, and used it to find the smallest $x$ that satisfies the 3 congruences above (I also verified the answers with a different CRT function, and a CRT command in an entirely different math program).

The interesting part is that, for the answer to come back correctly, I had to use the command $CRT([0, 1, 14087],[6, 23, 59407])$. You probably noticed the 6- I think this is how to account for the 2 showing up 3 times in the factorization of p-1 (and no, for some reason 8 doesn't yield the correct answer, as I expected).

So, I found that $L_1 = x = 5776566$, which is correct. This also works for $L_2$ However, using the above process for $L_3$ and $L_4$ doesn't work!

Note: I know the result values $L_i$- I found them through an easy exhaustive search in an earlier part of the problem, but I need to be able to generate them procedurally. If I sub the known answers into the original system up above, the congruence holds true. However, the $L_3$ and $L_4$ that I get from the Chinese Remainder Theorem process I described above do not work in the original system.

What am I doing wrong here? Is it how I handle the multiple factors of 2 in my original modulus? I can provide more detailed information if needed, I just wanted to keep this post as short as possible (which isn't short at all, it seems). Thanks for any advice- I feel like I'm really close to the solution here!

EDIT: the first comment below is correct- when using the method, the system needs to be solved mod 8, 23, and 59407 instead of 2, 23, and 59407. At that point, using the Chinese Remainder Theorem with 8 as the base instead of 2 will allow correct reconstruction of the desired $L$ vector

  • $\begingroup$ At this point: "And when I solve it modulo each factor $(2, 23, 59407)$ I get the following $L_i$ vectors", you want to perform the calculation modulo $8$ instead of $2$. The reason is that knowing the remainders modulo $2$, $23$ and $59407$ does not determine the resulting uniquely modulo $2^3.23.59407$; just modulo $2.23.59407$. $\endgroup$ Nov 29 '13 at 15:32
  • $\begingroup$ You're correct! I thought this wouldn't work because 8 wasn't a prime factor of p-1. Thank you very much- now I have to implement a modular solver in MATLAB that can accept a non-prime as the modulus. Is there some way I can give you credit for your answer? $\endgroup$
    – dkhaupt
    Nov 29 '13 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.