Los matemáticos cifran imágenes utilizando matemáticas de sudoku

El rompecabezas de colocación de números, Sudoku, consiste en una cuadrícula de 9 x 9 que debe llenarse con los dígitos del 1 al 9.

Sin embargo, existen varias limitaciones adicionales. Cada dígito solo puede aparecer una vez en cada columna, una vez en cada fila y una vez en cada uno de los nueve bloques de 3 x 3 que componen la cuadrícula. A continuación se muestra una cuadrícula de solución de Soduko. Los jugadores reciben una cantidad de dígitos de la solución para comenzar el juego.

Sudoku ha presentado una serie de desafíos interesantes para los matemáticos. A principios de este año, por ejemplo, observamos cómo los matemáticos habían resuelto el 'problema mínimo de Sudoku' para encontrar la menor cantidad de pistas que conduzcan a una solución única (respuesta, 17).

Hoy, Yue Wu de la Universidad Tufts en Medford y un par de amigos usan Sudoku para abordar un problema diferente: cómo encriptar imágenes antes de enviarlas.

Estos chicos dicen que las propiedades especiales de las cuadrículas de Sudoku conducen a un tipo completamente nuevo de matemáticas matriciales que han explotado para codificar imágenes.

Primero, algunos antecedentes sobre matrices. Una matriz es simplemente una matriz rectangular de números. Cada elemento de la matriz se identifica de forma única mediante una referencia de cuadrícula: su columna y su número de fila.

Pero Wu y sus colegas dicen que es posible identificar elementos en una matriz de otras formas si lo considera una cuadrícula de Sudoku. En ese caso, cada elemento contiene un dígito del 1 al 9 que cumple con las reglas del Sudoku. En otras palabras, además de la fila y la columna, cada elemento también tiene un dígito.

Entonces, en la cuadrícula anterior, el elemento en la primera fila y la primera columna (1,1) también está asociado con el dígito 8, el elemento (1,2) está asociado con 7, el elemento (1,3) con 4 y así sucesivamente. .

Además, cada elemento también está asociado con un bloque de 3 x 3, numerado como se muestra en la cuadrícula de arriba. Entonces el elemento (1,1) está asociado con el bloque 1, el elemento (2,8) con el bloque 7 y el elemento (8,5) con el bloque 6 y así sucesivamente.

Eso permite identificar cada elemento de otras formas. Por tanto, el elemento del bloque 5 que contiene el dígito 9 es el elemento (4, 5) en notación convencional; el elemento de la columna 3 que contiene el dígito 7 es (8,3) en notación convencional y el elemento de la fila 6 que contiene 2 es (6,9).

En total, hay seis formas diferentes de representar cada elemento, dicen Wu y compañía. Cada uno de estos sistemas es equivalente y es posible convertir las coordenadas de un sistema a otro utilizando un conjunto de funciones de conversión matemáticas simples.

Estas funciones de conversión son la clave para codificar imágenes. Comience con una imagen compuesta por 9x9 píxeles. A continuación, superponga una solución Soduko en esta cuadrícula para que ahora cada píxel pueda ser representado por los nuevos sistemas de coordenadas.

Ahora, aplicando una de las funciones de conversión a la cuadrícula, cambia la posición de los píxeles, mezclando la imagen.

Lo que Wu y compañía han descubierto es cómo aplicar una secuencia corta de funciones de conversión que codifica completamente la imagen. Eso es útil porque es completamente determinista y, sin embargo, produce un resultado aparentemente aleatorio (como se muestra en la imagen superior).

Esto equivale a una especie de cifrado en el que la solución original de Sudoku es la clave. (Para imágenes más grandes, simplemente coloque la imagen en mosaico con varias cuadrículas de Sudoku).

Wu y sus colegas han hecho una comparación inicial entre su método y otros algoritmos de codificación de imágenes y dicen que los iguala o los supera.

Y dado que para una imagen de 256 x 256, hay al menos 256! = 2 ^ 1684 posibles matrices de Sudoku, no es fácil para un adversario encontrar la solución por accidente o incluso por fuerza bruta.

Wu y compañía no hacen afirmaciones sobre su seguridad potencial, pero claramente hay espacio para una mayor exploración aquí.

¡Increíble lo que el Sudoku puede hacer por la humanidad!

Ref: arxiv.org/abs/1207.5856 : Biyecciones bidimensionales asociadas al sudoku para la codificación de imágenes

esconder