La matriz tiene dimensión n × n ( n - 1 ) . Queremos llenar A utilizando números enteros entre 1 y n , ambos inclusive.
Requisitos:
- Cada columna de es una permutación de 1 , ... , n .
- Cualquier submatriz formada por dos filas de no puede tener columnas idénticas.
Pregunta:
¿Es posible llenar la matriz satisfaciendo los requisitos?
Relación con la criptografía:
Cada número de fila corresponde a un texto sin formato. Cada columna corresponde a una clave. Como una clave define una inyección, cada columna debe ser una permutación. El segundo requisito es el secreto perfecto para dos mensajes.
Respuestas:
Tsuyoshi, gran observación en tu comentario! Creo que esto casi resuelve el problema.
Considere las siguientes dos preguntas
fuente
Esta es una solución parcial. Tal matriz existe si n es una potencia principal.
Sea F el campo finito de orden n . Construimos una matriz n × n ( n −1) cuyas filas están etiquetadas con F , cuyas columnas están etiquetadas con ( F ∖ {0}) × F , y cuyas entradas están en F de la siguiente manera: la i -ésima fila de la La columna etiquetada ( a , b ) viene dada por ai + b . En palabras, cada columna corresponde a un grado y un polinomio en F . Entonces cada columna contiene cada elemento de F exactamente una vez, y no hay dos columnas que tengan entradas iguales en más de una fila porque los valores de dos polinomios de grado uno pueden coincidir como máximo en un punto.
(Si desea una matriz cuyas entradas están en {1, ..., n } en lugar de en F , reemplace los elementos de F con {1, ..., n } arbitrariamente).
fuente