Matematycy szyfrują obrazy za pomocą matematyki Sudoku

Sudoku składa się z siatki 9 x 9, którą należy wypełnić cyframi od 1 do 9.

Istnieje jednak kilka dodatkowych ograniczeń. Każda cyfra może pojawić się tylko raz w każdej kolumnie, raz w każdym rzędzie i raz w każdym z dziewięciu bloków 3 x 3, które tworzą siatkę. Poniżej przedstawiono siatkę rozwiązań Soduko. Gracze otrzymują pewną liczbę cyfr z rozwiązania, aby rozpocząć grę.

Sudoku stawia przed matematykami szereg interesujących wyzwań. Na przykład na początku tego roku przyjrzeliśmy się, jak matematycy rozwiązali „problem minimum Sudoku”, aby znaleźć jak najmniejszą liczbę wskazówek, które prowadzą do unikalnego rozwiązania (odpowiedź, 17).

Dzisiaj Yue Wu z Tufts University w Medford i kilku kumpli używa Sudoku do rozwiązania innego problemu – jak zaszyfrować obrazy przed ich wysłaniem.

Ci goście twierdzą, że specjalne właściwości siatek Sudoku prowadzą do zupełnie nowego rodzaju matematyki macierzowej, którą wykorzystali do zaszyfrowania obrazów.

Najpierw krótkie wprowadzenie do macierzy. Macierz to po prostu prostokątna tablica liczb. Każdy element w tablicy jest jednoznacznie identyfikowany przez odniesienie do siatki — jego numer kolumny i wiersza.

Ale Wu i spółka twierdzą, że możliwe jest identyfikowanie elementów w tablicy na inne sposoby, jeśli pomyślimy o tym jako o siatce Sudoku. W takim przypadku każdy element zawiera cyfrę od 1 do 9, która spełnia zasady Sudoku. Innymi słowy, oprócz wiersza i kolumny każdy element ma również cyfrę.

Tak więc w powyższej siatce element w pierwszym wierszu i pierwszej kolumnie (1,1) jest również powiązany z cyfrą 8, element (1,2) jest powiązany z 7, element (1,3) z 4 i tak dalej .

Co więcej, każdy element jest również powiązany z blokiem 3 x 3, ponumerowanym tak, jak pokazano na powyższej siatce. Czyli element (1,1) jest powiązany z blokiem 1, element (2,8) z blokiem 7, a element (8,5) z blokiem 6 i tak dalej.

Dzięki temu można zidentyfikować każdy element na inne sposoby. Tak więc element w bloku 5 zawierający cyfrę 9 jest elementem (4,5) w notacji konwencjonalnej; element w kolumnie 3 zawierający cyfrę 7 to (8,3) w notacji konwencjonalnej, a element w wierszu 6 zawierający cyfrę 2 to (6,9).

W sumie istnieje sześć różnych sposobów przedstawiania każdego elementu, powiedzmy Wu i spółka. Każdy z tych układów jest równoważny i możliwe jest przekształcenie współrzędnych z jednego układu na inny za pomocą zestawu prostych matematycznych funkcji przeliczeniowych.

Te funkcje konwersji są kluczem do kodowania obrazów. Zacznij od obrazu składającego się z 9x9 pikseli. Następnie nałóż rozwiązanie Soduko na tę siatkę, aby każdy piksel mógł być teraz reprezentowany przez nowe układy współrzędnych.

Teraz, stosując jedną z funkcji konwersji do siatki, zamienia pozycję pikseli, mieszając obraz.

Wu i spółka odkryli, jak zastosować krótką sekwencję funkcji konwersji, która całkowicie zaburza obraz. Jest to przydatne, ponieważ jest całkowicie deterministyczne, a mimo to daje pozornie losowy wynik (jak pokazano na górnym obrazku).

Odpowiada to rodzajowi szyfrowania, w którym kluczem jest oryginalne rozwiązanie Sudoku. (W przypadku większych obrazów po prostu ułóż obraz obok kilku siatek Sudoku.)

Wu i spółka dokonali wstępnego porównania swojej metody z innymi algorytmami szyfrowania obrazu i twierdzą, że pasuje lub przewyższa je.

A ponieważ dla obrazu o wymiarach 256 x 256 jest co najmniej 256!=2^1684 możliwych macierzy Sudoku, przeciwnikowi nie jest łatwo trafić na rozwiązanie przypadkowo lub nawet brutalnie.

Wu i spółka nie twierdzą, że jest to potencjalne bezpieczeństwo, ale wyraźnie jest tu miejsce na dalszą eksplorację.

Niesamowite, co Sudoku może zrobić dla ludzkości!

Nr ref.: arxiv.org/abs/1207.5856 : Sudoku Dwuwymiarowe Bijekcje związane z szyfrowaniem obrazu

ukryć