¿Por qué hay $ 736$ $2\times 2$ matrices $(M)$ en $\mathbb{Z}_{26}$ para lo cual se sostiene que $M=M^{-1}$ ?

Question

Actualmente estoy tratando de introducirme en la criptografía.

Actualmente estoy leyendo sobre el Cifrado de Hill en el libro Applied Abstract Algebra. El cifrado de Hill utiliza una matriz invertible $M$ para la codificación y la matriz inversa $M^{-1}$ para descifrar. El libro recomienda utilizar una matriz $M$ para lo cual se sostiene que $M=M^{-1}$ ya que entonces tenemos la misma clave para cifrar y descifrar.

En el libro, utilizan un $2 \times 2$ matriz $M$ en $\mathbb{Z}_{26}$ como ejemplo, y afirmar que para hay 736 $2 \times 2$ matrices para las que se sostiene que $M=M^{-1}$ .

Intento captar todo lo posible cuando leo cosas, ya que me parece contraproducente para el aprendizaje saltarse algo, cuando no se entiende la teoría que hay detrás. ¿Puede alguien aclararme por qué hay 736 posibles $2 \times 2$ $M=M^{-1}$ matrices y cómo encontrarlas?

Answer 1

De hecho, resulta que hay una respuesta más sistemática. Calculando el número $a_n$ de matrices autoinversas sobre $\mathbb Z_n$ para algunos $n$ conduce a secuencias OEIS A066907 y A066947 . Resulta que $a_n$ es multiplicativo y viene dado por

$$ a_n=c_m\prod_i\left(2+p_i^{2k_i-1}(p_i+1)\right) $$

para $n=2^m\prod_ip_i^{k_i}$ donde el $p_i$ son los factores primos Impares de $n$ y

$$ c_m= \begin{cases} 1&m=0\;,\\ 4&m=1\;,\\ 28&m=2\;,\\ 9\cdot4^{m-1}+32&m\gt2\;. \end{cases} $$

En el presente caso $26=2^1\cdot13^1$ Así que $a_{26}=4(2+13\cdot14)=736$ .

Desgraciadamente, los enlaces de la entrada están todos rotos y la dirección de correo electrónico del autor está obsoleta, así que la pregunta sigue siendo cómo derivar esto.

Answer 2

Puede que haya una forma más sistemática de hacerlo; he aquí una forma semi-sistemática.

Su condición es equivalente a $M^2=I$ . Para $\displaystyle M=\pmatrix{a&b\\c&d}$ que da lugar a cuatro ecuaciones:

$$ \begin{align} a^2+bc&\equiv1\;,\\ ab+bd&\equiv0\;,\\ ca+dc&\equiv0\;,\\ cb+d^2&\equiv1\;. \end{align} $$

La primera y la última tienen soluciones para $a$ y $d$ respectivamente, si y sólo si $1-bc$ es un residuo cuadrático. Si es así, $a^2\equiv d^2$ y por lo tanto $a\equiv\pm d$ .

La segunda y tercera ecuación son $(a+d)b\equiv0$ y $(a+d)c\equiv0$ . Estos se cumplen para $a\equiv-d$ por lo que tenemos una solución para cada par $b,c$ con $1-bc\equiv0$ o $1-bc\equiv13$ y dos soluciones para cada par $b,c$ con $1-bc$ un residuo cuadrático distinto de $0$ y $13$ . No conozco una forma sistemática de contarlas; este código cuenta $728$ .

Eso deja la alternativa $a\equiv+d$ , excluyendo $a=d=0$ y $a=d=13$ puesto que ya se han contabilizado en $a\equiv-d$ . En este caso $a+d$ es par y no divisible por $13$ Así que $(a+d)b\equiv0$ y $(a+d)c\equiv0$ si y sólo si $b$ y $c$ son ambos $0$ o $13$ . Eso es $4$ y para cada una de ellas hay dos raíces cuadradas de $1-bc$ que $a=d$ puede ser, así que eso hace que $8$ posibilidades adicionales, para un total de $728+8=736$ .

Answer 3

Dejemos que $A,B,C$ se extienden sobre los elementos no nulos de ${\mathbb Z}/13$ .

Entonces, sobre ${\mathbb Z}/13$ Obtengo las siguientes matrices autoinversas:

$$\hbox{12 of type} \pmatrix{0&B\cr 1/B&0\cr}$$ $$\hbox{144 of type} \pmatrix{A&B\cr{1-A^2\over B}&-A\cr}$$ $$\hbox{4 of type} \pmatrix{\pm 1&0\cr 0&\pm 1\cr}$$ $$\hbox{12 each of types} \pmatrix{1&0\cr C&-1\cr}, \pmatrix{-1&0\cr C&1\cr},\pmatrix{1&B\cr 0&-1\cr},\pmatrix{-1&B\cr 0&1\cr}$$

Eso es un total de 208 sobre ${\mathbb Z}/13$ . Si multiplico esto por 4 (el número de matrices autoinversas sobre ${\mathbb Z}/2$ ), obtengo 832, no 736. ¿Dónde está mi error?

Answer 4

Para un $2\times2$ matriz, $M=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ la inversa viene dada por $M^{-1}=\frac1{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$ . Por lo tanto, para que $M=M^{-1}$ Hay dos opciones:
(1) $b=c=0$ entonces $a=\frac{1}{ad}d=\frac1a$ y $d=\frac1{ad}a=\frac1d$ Por lo tanto $a^2=d^2=1$ es decir $a=\pm1$ , $b=\pm1$ - por lo que hay $4$ tales matrices.
(2) Al menos uno de $b,c$ es distinto de cero. Entonces $ad-bc=-1$ y $d=-a$ . Dos opciones a partir de aquí:
(i) Si $bc=0$ entonces $ad=-a^2=-1$ Así que $a=\pm1$ . Así que hay $25$ opciones a elegir $b\neq0$ y dos opciones a elegir $a$ . Así que un total de $50$ matrices con $c=0$ . Por lo tanto, un total de $100$ tales matrices con $bc=0$ .
(ii) $bc\neq0$ . Tenemos $a^2+bc=1$ Así que $1-bc$ tiene que ser un cuadrado $\mod 26$ Por lo tanto $1-bc\in\{0,1,4,9,16,25,10,23,12,3,22,17,14,13\}$ . Desde $bc\neq0$ tenemos $bc\in\{1,23,18,11,2,17,4,15,24,5,10,13,14\}$ . Hay $26(1-\frac12)(1-\frac1{13})=12$ ( Phi de Euler ) elementos invertibles en $\mathbb{Z}_{26}$ . Para cualquier elección de invertible $b$ Hay $13$ opciones para $bc$ , cada uno de ellos da una opción para $c$ cada uno de ellos, a su vez, da $2$ opciones para $a$ , excepto $bc=14$ (ya que $a^2=13$ implica $a=13$ ). Por lo tanto, un total de $12\cdot12\cdot2+12\cdot1\cdot1=300$ tales matrices con $b$ invertible.
Para $bc\in\{18,2,4,24,10,13,14\}$ hay soluciones con $b$ no invertible: cada uno de ellos tiene que ser comprobado manualmente. Por ejemplo:
$bc=18$ entonces $b\in\{2,6,9,18,-2=24,-6=20,-9=17,-18=8\}$ (todos los divisores no invertibles de $18$ ). Por lo tanto, hay $8\cdot 2=16$ ( $2$ opciones para $a$ ) tales matrices.
Y así sucesivamente

Answer 5

Interesante, esta pregunta es muy parecida (pero no del todo) a una tarea que tengo que hacer el lunes, y que he intentado resolver parte del viernes y todo el sábado (y que ya casi he abandonado), sin suerte.

Tengo que responder exactamente a la misma pregunta que tú, pero me han encargado que lo haga "dividiendo el problema en dos casos. Primero un caso en el que es el módulo 2, y luego el módulo 13".

Me imagino que después de encontrar la cantidad módulo 2 y 13, debo usar el Teorema del Resto Chino para hacer el resultado mod 26 de nuevo. Sin embargo, no sé cómo debo hacerlo. Lo que he hecho hasta ahora, es en realidad algo que parece más similar a lo que joriki sugirió (pero no tengo idea, si era el enfoque correcto para hacer en mi caso).

Lo que hago para intentar solucionarlo, es que yo, según las instrucciones, divido $det(A) \equiv \pm 1$ mod 26 en: $det(A) \equiv \pm 1$ mod $13$ y $det(A) \equiv \pm 1$ mod $2$ .

Entonces he estado pensando (y esta es la parte que creo que me recordó la solución de joriki) que como $A=A^{-1}$ significa que $A^2=I$ debería encontrar todos los casos en los que..:

$\pmatrix{a&b\\c&d}^2=\pmatrix{1&0\\0&1}$

Lo que significa que tengo las congruencias: \begin {align} a^2+bc& \equiv1\\ ab+bd& \equiv0\\ ca+dc& \equiv0\\ cb+d^2& \equiv1\ \end {align}

Pero ahí se acaba la diversión. No tengo ni idea de a dónde ir desde este punto.... O si lo que he estado haciendo hasta ahora, es la forma correcta de hacerlo, si quiero mostrarlo usando la pista dada... Espero que alguien pueda (y también ayude), y esté dispuesto a arrojar algo de luz sobre esto.

El curso en el que tengo esta tarea es un curso de introducción a la criptología, por lo que no estoy familiarizado (todavía, me parece que las matemáticas son atractivas, especialmente en un entorno de criptología) con la phi de Euler, las secuencias OEIS y los términos cuadráticos de los residuos, por lo que no he sido capaz de darles la vuelta y darme la suficiente inspiración para resolver mi propio subproblema aquí.

Perdona si me estoy desviando de tu pregunta. Hice una pregunta aparte al principio, pero se consideró un duplicado de esta. Y estoy de acuerdo con eso. Esta es una subpregunta sobre cómo resolver tu pregunta de manera específica. Espero que la respuesta (espero conseguir una) pueda ser interesante para ti también, ya que parece que te estás introduciendo en la criptografía también :)