Les mathématiciens chiffrent les images à l'aide des mathématiques du sudoku

Le puzzle de placement des nombres, Sudoku, se compose d'une grille de 9 x 9 qui doit être remplie à l'aide des chiffres 1 à 9.

Cependant, il existe plusieurs contraintes supplémentaires. Chaque chiffre ne peut apparaître qu'une fois dans chaque colonne, une fois dans chaque ligne et une fois dans chacun des neuf blocs 3 x 3 qui composent la grille. Une grille de solution Soduko est présentée ci-dessous. Les joueurs reçoivent un certain nombre de chiffres de la solution pour démarrer le jeu.

Sudoku a lancé un certain nombre de défis intéressants pour les mathématiciens. Plus tôt cette année, par exemple, nous avons examiné comment les mathématiciens avaient résolu le « problème du sudoku minimum » pour trouver le plus petit nombre d'indices menant à une solution unique (réponse, 17).

Aujourd'hui, Yue Wu de l'Université Tufts de Medford et quelques amis utilisent Sudoku pour résoudre un problème différent : comment crypter des images avant de les envoyer.

Ces gars-là disent que les propriétés spéciales des grilles de Sudoku conduisent à un tout nouveau type de mathématiques matricielles qu'ils ont exploitées pour brouiller les images.

Tout d'abord, un peu de contexte sur les matrices. Une matrice est simplement un tableau rectangulaire de nombres. Chaque élément du tableau est identifié de manière unique par une référence de grille – son numéro de colonne et de ligne.

Mais Wu et ses collègues disent qu'il est possible d'identifier les éléments d'un tableau d'autres manières si vous le considérez comme une grille de Sudoku. Dans ce cas, chaque élément contient un chiffre de 1 à 9 qui satisfait aux règles du Sudoku. En d'autres termes, en plus de la ligne et de la colonne, chaque élément a également un chiffre.

Ainsi dans la grille ci-dessus, l'élément de la première ligne et de la première colonne (1,1) est également associé au chiffre 8, l'élément (1,2) est associé au 7, l'élément (1,3) au 4 et ainsi de suite .

De plus, chaque élément est également associé à un bloc 3 x 3, numéroté comme indiqué dans la grille ci-dessus. Ainsi l'élément (1,1) est associé au bloc 1, l'élément (2,8) au bloc 7 et l'élément (8,5) au bloc 6 et ainsi de suite.

Cela permet d'identifier chaque élément par d'autres moyens. Ainsi, l'élément du bloc 5 contenant le chiffre 9 est l'élément (4,5) en notation conventionnelle ; l'élément de la colonne 3 contenant le chiffre 7 est (8,3) en notation conventionnelle et l'élément de la ligne 6 contenant 2 est (6,9).

Au total, il existe six façons différentes de représenter chaque élément, disons Wu and co. Chacun de ces systèmes est équivalent et il est possible de convertir les coordonnées d'un système à un autre en utilisant un ensemble de fonctions de conversion mathématiques simples.

Ces fonctions de conversion sont la clé du brouillage des images. Commencez avec une image composée de 9x9 pixels. Superposez ensuite une solution de Soduko sur cette grille afin que chaque pixel puisse maintenant être représenté par les nouveaux systèmes de coordonnées.

Maintenant, en appliquant l'une des fonctions de conversion à la grille, échange la position des pixels, brouillant l'image.

Ce que Wu et ses collaborateurs ont découvert, c'est comment appliquer une courte séquence de fonctions de conversion qui brouille complètement l'image. C'est utile car il est entièrement déterministe et produit un résultat apparemment aléatoire (comme le montre l'image du haut).

Cela équivaut à une sorte de cryptage dans lequel la solution de Sudoku d'origine est la clé. (Pour les images plus grandes, il vous suffit de mosaïquer l'image avec plusieurs grilles de Sudoku.)

Wu et co ont fait une première comparaison entre leur méthode et d'autres algorithmes de brouillage d'images et disent qu'elle les correspond ou les surpasse.

Et comme pour une image 256 x 256, il y a au moins 256 !=2^1684 matrices Sudoku possibles, il n'est pas facile pour un adversaire de trouver la solution par accident ou même par force brute.

Wu and co ne prétendent pas à sa sécurité potentielle, mais il y a clairement de la place pour une exploration plus approfondie ici.

Incroyable ce que le Sudoku peut faire pour l'humanité !

Réf : arxiv.org/abs/1207.5856 : Bijections bidimensionnelles associées au sudoku pour le brouillage d'images

cacher