2
$\begingroup$

I'm trying to solve these equations to solve a ciphertext which is encrypted by the Hill Cipher. I tried to solve these equations algebraically. (First choose two of them and try to eliminate one variable and after that choose another two and try the same thing for achieving two unknown two equations etc...)

\begin{align*} \tag{1}7a + 24b + 6c &= 1 \mod 26 \\ \tag{2}16a + 2b + 20c &= 0 \mod 26 \\ \tag{3}9a + 13b + 13c &= 10 \mod 26 \\ \tag{4}10a + 15b + 6c &= 17 \mod 26 \end{align*}

After this method I got $a = 17$, $b = 1$ and $c = 24$ and $a = 17$, $b = 1$, $c = 11$. However, it did not work with all of the four equations. Is there another way to solve these equations?

  • 1
    Try the Chinese Remainder Theorem; it should make stuff easier.2012-10-22
  • 0
    How can I apply Chinese Remainder Theorem in these equation?2012-10-22
  • 0
    To solve them modulo $2$ and modulo $13$, then reconstruct the solutions. It makes deriving $a = 17$ very easy (first and third equations).2012-10-22
  • 0
    The "algebraic way" should work, provided you remember to do all your arithmetic modulo 26, and remember not to divide or multiply by anything that isn't prime to 26.2012-10-22
  • 0
    Multiplying should be harmless, though...2012-10-22
  • 0
    @Lord_Farin: Multiplying a line by zero can be very harmful...2012-10-22
  • 0
    Adding on to that: Try multiplication by 13 to equation 1. Then try multiplication by 13 to equation 2. Equation 3 times 2 is quite similar too.2012-10-22
  • 0
    Also, your solution 2 is the one that fails, on equation 3. Perhaps you divided by 2 or 13 (which is not coprime to 26) while solving for c?2012-10-22
  • 0
    Your strategy for solving does not seem correct. You eliminate two variables from two sets of equations, but still overall you have 4 equations and 4 unknowns. Be careful that you only divide or multiply by something relatively prime to 26 (or use the CRT).2012-10-22

2 Answers 2

3

As suggested by Lord_Farin, consider the equations modulo $2$ and modulo $13$ separately. Modulo $2$ you get

\begin{align} a &\equiv 1 \mod 2 \\ 0 &\equiv 0 \mod 2 \\ a + b + c &\equiv 0 \mod 2 \\ b &\equiv 1 \mod 2 \end{align}

which has solutions $\boxed{(a,b,c) \equiv (1,1,0) \mod 2}$. Modulo $13$ is a bit harder, but we get

\begin{align} -6a - 2b + 6c &\equiv 1 \mod 13 \\ 3a + 2b - 6c &\equiv 0 \mod 13 \\ -4a &\equiv -3 \mod 13 \\ -3a + 2b + 6c &\equiv 4 \mod 13 \end{align}

Using the third equation first, we get $a \equiv 4 \mod 13$, so that the other three become

\begin{align} -2b + 6c &\equiv -1 \mod 13 \\ 2b - 6c &\equiv 1 \mod 13 \\ 2b + 6c &\equiv 3 \mod 13 \end{align}

Solving for $b$ and $c$, we get $b \equiv 1 \mod 13$ and $c \equiv 11 \mod 13$. So modulo $13$, the numbers $a,b,c$ satisfy $\boxed{(a,b,c) \equiv (4,1,11) \mod 13}$.

Combining the two boxes, we get the unique solution $\boxed{(a,b,c) \equiv (17,1,24) \mod 26}$.

1

Hint $\ $ By $\rm (1)+(2),\,\ -3a \equiv 1\equiv 27,\:$ so $\rm\:a\equiv -9.\ $ By $\rm (2)+(4),\,\ 17b\equiv 17,\:$ so $\rm\:b\equiv 1.$ Substituting in $\rm\:(3)\:$ yields $\rm\:6c\equiv -12\:$ so $\rm\:c\equiv -2\pmod{\color{#C00}{13}}.\:$ By $\rm\:(3)\,\ mod\ 2\!:\ c \equiv -a -b = 9-1\equiv 0,\:$ hence $\rm\:c\equiv -2\pmod{\color{#C00}{26}}.\:$ Indeed $\rm\:(a,b,c)\equiv (-9,1,-2)\:$ satisfies all equations.