211service.com
Wiskundigen versleutelen afbeeldingen met de wiskunde van Sudoku
De puzzel voor het plaatsen van nummers, Sudoku, bestaat uit een raster van 9 x 9 dat moet worden gevuld met de cijfers 1 tot en met 9.
Er zijn echter een aantal aanvullende beperkingen. Elk cijfer kan slechts één keer in elke kolom voorkomen, één keer in elke rij en één keer in elk van de negen 3 x 3 blokken waaruit het raster bestaat. Hieronder wordt een Soduko-oplossingsraster weergegeven. Spelers krijgen een aantal cijfers uit de oplossing om het spel te starten.
Sudoku heeft een aantal interessante uitdagingen voor wiskundigen opgeworpen. Eerder dit jaar hebben we bijvoorbeeld gekeken naar hoe wiskundigen het 'minimum Sudoku-probleem' hadden opgelost om het kleinste aantal aanwijzingen te vinden dat tot een unieke oplossing leidde (antwoord, 17).
Tegenwoordig gebruiken Yue Wu van de Tufts University in Medford en een paar vrienden Sudoku om een ander probleem aan te pakken: afbeeldingen versleutelen voordat ze worden verzonden.
Deze jongens zeggen dat de speciale eigenschappen van Sudoku-rasters leiden tot een geheel nieuw type matrixwiskunde dat ze hebben uitgebuit om afbeeldingen door elkaar te gooien.
Eerst wat achtergrondinformatie over matrices. Een matrix is gewoon een rechthoekige reeks getallen. Elk element in de array wordt uniek geïdentificeerd door een rasterverwijzing: het kolom- en rijnummer.
Maar Wu en co zeggen dat het mogelijk is om elementen in een array op andere manieren te identificeren als je het als een Sudoku-raster beschouwt. In dat geval bevat elk element een cijfer van 1 t/m 9 dat voldoet aan de regels van Sudoku. Met andere woorden, naast de rij en kolom heeft elk element ook een cijfer.
Dus in het bovenstaande raster is het element in de eerste rij en eerste kolom (1,1) ook geassocieerd met het cijfer 8, element (1,2) is geassocieerd met 7, element (1,3) met 4 enzovoort .
Bovendien wordt elk element ook geassocieerd met een blok van 3 x 3, genummerd zoals weergegeven in het bovenstaande raster. Dus element (1,1) hoort bij blok 1, element (2,8) bij blok 7 en element (8,5) bij blok 6 enzovoort.
Dat maakt het mogelijk om elk element op een andere manier te identificeren. Dus het element in blok 5 dat het cijfer 9 bevat, is element (4,5) in conventionele notatie; het element in kolom 3 met cijfer 7 is (8,3) in conventionele notatie en het element in rij 6 met 2 is (6,9).
In totaal zijn er zes verschillende manieren om elk element weer te geven, zeggen Wu en co. Elk van deze systemen is equivalent en het is mogelijk om de coördinaten van het ene systeem naar het andere te converteren met behulp van een reeks eenvoudige wiskundige conversiefuncties.
Deze conversiefuncties zijn de sleutel tot het versleutelen van afbeeldingen. Begin met een afbeelding van 9x9 pixels. Leg vervolgens een Soduko-oplossing op dit raster, zodat elke pixel nu kan worden weergegeven door de nieuwe coördinatensystemen.
Door nu een van de conversiefuncties op het raster toe te passen, wordt de positie van pixels verwisseld, waardoor de afbeelding door elkaar wordt gehaald.
Wat Wu en co hebben ontdekt, is hoe je een korte reeks conversiefuncties kunt toepassen die het beeld volledig vervormt. Dat is handig omdat het volledig deterministisch is en toch een schijnbaar willekeurig resultaat oplevert (zoals weergegeven in de bovenste afbeelding).
Dit komt overeen met een soort encryptie waarbij de originele Sudoku-oplossing de sleutel is. (Voor grotere afbeeldingen betegelt u de afbeelding eenvoudig met meerdere Sudoku-rasters.)
Wu en co hebben een eerste vergelijking gemaakt tussen hun methode en andere algoritmen voor het vervormen van afbeeldingen en zeggen dat deze overeenkomt met of beter presteert.
En aangezien er voor een afbeelding van 256 x 256 minstens 256!=2^1684 mogelijke Sudoku-matrices zijn, is het voor een tegenstander niet gemakkelijk om per ongeluk of zelfs met brute kracht op de oplossing te komen.
Wu en co doen geen uitspraken over de potentiële veiligheid, maar er is hier duidelijk ruimte voor verder onderzoek.
Verbazingwekkend wat Sudoku voor de mensheid kan doen!
Referentie: arxiv.org/abs/1207.5856 : Sudoku geassocieerde tweedimensionale bijecties voor beeldvervorming