Matematiker Kryptera bilder med Sudoku matematik

Pusslet med nummerplacering, Sudoku, består av ett 9 x 9 rutnät som måste fyllas med siffrorna 1 till 9.

Det finns dock flera ytterligare begränsningar. Varje siffra kan bara förekomma en gång i varje kolumn, en gång i varje rad och en gång i vart och ett av de nio 3 x 3 blocken som utgör rutnätet. Ett rutnät för Soduko-lösning visas nedan. Spelare får ett antal siffror från lösningen för att få igång spelet.

Sudoku har skapat ett antal intressanta utmaningar för matematiker. Tidigare i år tittade vi till exempel på hur matematiker hade löst 'minsta Sudoku-problemet' för att hitta det minsta antalet ledtrådar som leder till en unik lösning (svar, 17).

Idag använder Yue Wu vid Tufts University i Medford och ett par kompisar Sudoku för att ta itu med ett annat problem – hur man krypterar bilder innan de skickas.

Dessa killar säger att de speciella egenskaperna hos Sudoku-rutnät leder till en helt ny typ av matrismatematik som de har utnyttjat för att förvränga bilder.

Först lite bakgrund om matriser. En matris är helt enkelt en rektangulär matris av tal. Varje element i arrayen identifieras unikt av en rutnätsreferens – dess kolumn och radnummer.

Men Wu och co säger att det är möjligt att identifiera element i en array på andra sätt om du tänker på det som ett Sudoku-rutnät. I så fall innehåller varje element en siffra från 1 till 9 som uppfyller reglerna för Sudoku. Med andra ord, förutom raden och kolumnen har varje element också en siffra.

Så i rutnätet ovan är elementet i den första raden och första kolumnen (1,1) också associerat med siffran 8, element (1,2) är associerat med 7, element (1,3) med 4 och så vidare .

Dessutom är varje element också associerat med ett 3 x 3 block, numrerat som visas i rutnätet ovan. Så element (1,1) är associerat med block 1, element (2,8) med block 7 och element (8,5) med block 6 och så vidare.

Det gör det möjligt att identifiera varje element på andra sätt. Så elementet i block 5 som innehåller siffran 9 är element (4,5) i konventionell notation; elementet i kolumn 3 som innehåller siffran 7 är (8,3) i konventionell notation och elementet i rad 6 som innehåller 2 är (6,9).

Totalt finns det sex olika sätt att representera varje element, säger Wu och co. Vart och ett av dessa system är ekvivalenta och det är möjligt att omvandla koordinaterna från ett system till ett annat med hjälp av en uppsättning enkla matematiska omvandlingsfunktioner.

Dessa konverteringsfunktioner är nyckeln till förvrängning av bilder. Börja med en bild som består av 9x9 pixlar. Lägg sedan över en Soduko-lösning på detta rutnät så att varje pixel nu kan representeras av de nya koordinatsystemen.

Nu, genom att tillämpa en av konverteringsfunktionerna på rutnätet, byter pixlarnas position, och bilden blandas ihop.

Vad Wu och co har upptäckt är hur man använder en kort sekvens av konverteringsfunktioner som helt förvränger bilden. Det är användbart eftersom det är helt deterministiskt och ändå ger ett till synes slumpmässigt resultat (som visas i den översta bilden).

Detta motsvarar en sorts kryptering där den ursprungliga Sudoku-lösningen är nyckeln. (För större bilder lägger du helt enkelt ihop bilden med flera Sudoku-rutnät.)

Wu och co har gjort en inledande jämförelse mellan deras metod och andra bildkrypteringsalgoritmer och säger att den matchar eller överträffar dem.

Och eftersom det för en bild på 256 x 256 finns minst 256!=2^1684 möjliga Sudoku-matriser, är det inte lätt för en motståndare att slå på lösningen av misstag eller ens av brutalt våld.

Wu och co gör inga påståenden om dess potentiella säkerhet men det finns helt klart utrymme för ytterligare utforskning här.

Fantastiskt vad Sudoku kan göra för mänskligheten!

Ref: arxiv.org/abs/1207.5856 : Sudoku Associated Two Dimensional Bijections for Image Scrambling

Dölj