1
$\begingroup$

Cryptography assignment question: matrix $A$ is \begin{equation} A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 \end{array}\right) \end{equation} (Hill Cipher key). Show that for a vector $x_1$, $x_1A=x_2A \mod 26$ for exactly $13$ $x_2$'s.

Progress so far: $\det(A)=13$ so $A$ is not invertible $\mod 26$. Re-write the problem as find $y$ such that $yA=0 \mod 26$. I thought I could find $y$ by finding the null space of $A$ $\mod 26$ but I don't know how to do that. It doesn't seem to be working.

$\endgroup$
  • $\begingroup$ sorry forgot to mention that re-arranged it as (x1-x2)A=0 mod 26 and let (x1-x2)=y so there should be 13 different y vectors such that yA=0 mod 26 $\endgroup$ – Alan Jan 20 '14 at 22:42
1
$\begingroup$

So, $A=\pmatrix{1&0&0\\1&3&1\\0&2&5}$ and let $y=(y_1,y_2,y_3)$. Then we need to find the solutions of $yA=0$, i.e. $$\matrix{y_1+y_2 &=& 0 &&& (i) \\ 3y_2+2y_3 &=& 0 &&& (ii)\\ y_2+5y_3 &=& 0 &&& (iii) }$$ Now perform $(ii)\,-\,3\cdot(iii)$ to obtain $\ \ -13y_3=0 \quad\quad (iv)$.
Since all these are modulo $26$, any even $y_3\in\Bbb Z_{26}$ will be a solution of $(iv)$. (There are exactly $13$ even numbers modulo $26$.)
Then, $y_2$ can be uniquely determined by either $(iii)$ or $(ii)$, knowing the choice for $y_3$ and also, $y_2$ determines $y_1$ by $(i)$.

$\endgroup$

Your Answer

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

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