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?

  • 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.