VRNITEV ARNOLDOVE MA ˇ CKE MITJA LAKNER1, PETER PETEK2, MARJETA ˇSKAPIN RUGELJ1 1Fakulteta za gradbeniˇstvo in geodezijo, Univerza v Ljubljani 2Pedagoˇska fakulteta, Univerza v Ljubljani Math. Subj. Class. (2010): 37D45, 94A60 Hiperboliˇcna matrika doloˇca preslikavo na torusu, vendar jo lahko opazujemo tudi na N × N rastru, kot je to napravil V. I. Arnold [2]. Opazoval je sliko maˇcke, ki se je po doloˇcenem ˇstevilu iteracij vrnila. Zanima nas povezava med gostoto rastra in periodo vrnitve. To lastnost lahko uporabimo tudi za ˇsifriranje in prikrivanje informacij. RECURRENCE OF ARNOLD’S CAT A hyperbolic matrix yields a mapping on the torus. However we can, as V. I. Arnold [2] did, consider the picture of the cat on N × N raster. After a certain number of iterations the cat returns. We are interested in the dependence of the period of return on the density of the raster net. The property of return can be used for coding and covering up information. Uvod V klasiˇcni mehaniki nastopa jo posebni sistemi diferencialnih enaˇcb – ha­miltonski sistemi. Po javlja jo se npr. pri nebesni mehaniki ali pri dvo jnem nihalu. Standardna obravnava [1] nas pripelje do prostorov v obliki veˇcdi­menzionalnih torusov. Lokalne reˇsitve sistema opiˇsemo z matriko, ki ohranja ploˇsˇcino. Matrika v eno smer razteguje, v drugo stiska in je hiperboliˇcna, kar pomeni, da nima lastnih vrednosti dolˇzine ena. V nekem smislu ta hi­perboliˇcnost zagotavlja dobro meˇsanje slike. Ruski matematik V. I. Arnold je obravnaval take sisteme, posebej na dvodimenzionalnem torusu. Opazo­val je zanimive lastnosti, ka j se zgodi na neki ekvidistantni mreˇzi – rastru – na torusu. Toˇck na mreˇzi je konˇcno mnogo, matrika jih zgolj premeˇsa, permutira med sabo. Po konˇcnem ˇstevilu korakov vsaka permutacija spet pripelje stvari v prvotno stanje. Arnold, ki je imel rad slikovite prispodobe, je vzel sliko maˇcke, jo ra­striral in iteriral preslikavo na torusu [2]. In maˇcka se je spet po javila po doloˇcenem konˇcnem ˇstevilu korakov. Seveda je perioda odvisna od gostote rastra in to precej misteriozno. Vsa j teoretiˇcno se da uporabiti to metodo za prikrivanje podatkov, ste­ganogra.jo. Pri tem ni treba slediti prvotni Arnoldovi matriki, vsaka iz sploˇsne linearne grupe nad celimi ˇstevili je dobra. In kot je navada ˇze v kriptogra.ji, kjer si ˇzelijo velikih praˇstevil, si tuka j ˇzelimo dolgo periodo. Sicer pa je, ˇce jo opazujemo na celem torusu in ne le na rastrski mreˇzi, preslikava kaotiˇcna. A o tem v prihodnjem ˇclanku. Hiperboliˇcni avtomor.zmi torusa Torus dobimo, ˇce enotski kvadrat zlepimo po dveh vzporednih stranicah in isto naredimo ˇse z nastalima kroˇznicama. To je vsebina naslednje de.nicije: ˇ De.nicija 1. Ce v ravnini R2 identi.ciramo vse toˇcke, katerih koordinate se razlikujejo za celo ˇstevilo, dobimo torus T . Identi.kacija de.nira ekvivalenˇcno relacijo na R2, kjer je (x1, y1) ~ (x2, y2) natanko teda j, ko sta x2 - x1 in y2 - y1 celi ˇstevili. Ta ekvivalenˇcna relacija doloˇca pro jekcijo . : R2 › T , .(x, y) = [x, y]. Poglejmo si, ka j dobimo, ˇce tlakovano celoˇstevilsko ravninsko mreˇzo pre­slikamo s celoˇstevilsko matriko dimenzije 2 ×2. Na sliki 1 na sredini vidimo, da pri mnoˇzenju z matriko z determinanto 1 dobimo tlakovanje mreˇze s ˇ skladnimi »ploˇsˇcicami«. Ce pa ima matrika determinanto 2, so »ploˇsˇcice« tlakovanja razliˇcne. Iz slike intuitivno sklepamo, da se je smiselno omejiti na matrike z determinanto ±1. Slika 1. Tlakovanje ravninske mreˇze (na levi) in sliki mreˇze, ˇce uporabimo matriki z determinanto 1 (na sredi) oz. 2 (na desni). De.nicija 2. Na j bo A = (aij) matrika dimenzije 2 × 2 z lastnostmi (a) A je hiperboliˇcna (lastni vrednosti ne leˇzita na enotski kroˇznici v kom­pleksni ravnini); (b) aij . Z, 1 . i, j . 2; (c) det A = ±1. Slika 2. Slika kroˇznice pri mnoˇzenju z matriko A. Matrika A inducira tako preslikavo LA : T › T , da je LA . . = . . A. To preslikavo imenujemo hiperboliˇcni avtomor.zem torusa: x LA([x, y]) . A (mod 1). y Opomba 1. Ker je det A = ±1, je A-1 tudi hiperboliˇcna in elementi ma-trike so cela ˇstevila. Torej A-1 tudi inducira hiperboliˇcni avtomor.zem torusa (LA)-1 . 2 1 Primer. Preslikavo LA torusa, inducirano z matriko A = , ime­ 1 1 nujemo preslikava Arnoldove maˇcke CA [2]. Lastni vrednosti matrike A sta . . 3+ 5 3- 5 .1 = 2 in .2 = 2 . Na sliki 2 vidimo, kam se pri mnoˇzenju z matriko A preslika kroˇznica s srediˇsˇcem v izhodiˇsˇcu. Ker je det A = 1, je CA hi­perboliˇcni avtomor.zem torusa. Poglejmo, kam A preslika enotski kvadrat. Ker je . . . . . . . . . . . . A 1 0 = 2 1 , A 0 1 = 1 1 , A 1 1 = 3 2 , se enotski kvadrat preslika v paralelogram enake ploˇsˇcine (glej sliko 3). Na sliki 4 vidimo, kako se slika maˇcke, ki jo predstavimo s 124 × 124 toˇckami, razmaˇze po paralelogramu in po 15 iteracijah ponovno po javi. Slika 3. Avtomor.zem. Izhodiˇsˇce je edina negibna toˇcka preslikave CA. Bralec se lahko z upo­rabo popolne indukcije prepriˇca, da za potenco matrike A velja F2n+1 F2n An = , F2n F2n-1 kjer je (Fn) Fibonaccijevo zaporedje s F0 = 0, F1 = 1 in Fn+1 = Fn-1 + Fn. Resniˇcno sliko predstavimo z N × N slikovnimi toˇckami, enakomerno razporejenimi v kvadratno mreˇzo. Na j bo .(N) na jmanjˇse tako ˇstevilo, da je Ak . I (mod N). Potem se po .(N) iteracijah preslikave CA vrne prvotna slika. Na jbolj znan raster je N = 124, ko je .(124) = 15 (slika 4). Diskretna preslikava Arnoldove maˇcke Diskretna preslikava Arnoldove maˇcke je podana s predpisom xn+1 xn . A (mod N), (1) yn+1 yn 2 1 kjer je A = , in deluje na kvadratni mreˇzi z N ×N toˇckami, katerih 1 1 koordinate so cela ˇstevila 0, 1, . . . , N - 1. Na j toˇcke pomenijo slikovne toˇcke slike maˇcke. Vsaka iteracija toˇcke pomeˇsa med sabo. To vidimo takole: y preslikava (x, y) › (N x , ) preslika kvadrat [0, N )2 bijektivno na [0, 1)2 . N Ker . preslika kvadrat [0, 1)2 bijektivno na torus T , kjer je LA bijekcija, je diskretna preslikava Arnoldove maˇcke res permutacija. Slika 4. Iteracija avtomor.zma. Vpraˇsanje pa je, koliko iteracij je treba, da zopet dobimo prvotno sliko. V matriˇcnem zapisu to pomeni, da iˇsˇcemo tako ˇstevilo P = P (N), da bo ˇ AP . I (mod N) (glej sliko 4). Stevilo P (N) imenujemo perioda, s .(N) pa oznaˇcimo minimalno periodo, ko se slika ponovi. V primeru na sliki 4 je .(124) = 15. Izkaˇze se, da minimalna perioda ni naraˇsˇca joˇca funkcija N ([6, 3, 4]). Slika 5 prikazuje minimalno periodo do vkljuˇcno N = 5000. Ker velja F2n+1 F2n An = , (2) F2n F2n-1 kjer je (Fn) Fibonaccijevo zaporedje za F0 = 0, F1 = 1, sta perioda in minimalna perioda preslikave (1) odvisni od deljivosti Fibonaccijevih ˇstevil. Iz enaˇcbe (2) sledi, da je ˇstevilo T perioda P (N) preslikave (1), ˇce in samo ˇce velja F2T -1 . 1 (mod N) in F2T . 0 (mod N). (3) Pokaˇzimo zelo grobo oceno za minimalno periodo. Izrek 1. Za poljubno sliko velikosti N ×N, kjer je N . 3, velja .(N) . N2 . Za dokaz izreka potrebujemo tri kratke leme. Na j bo .n na jmanjˇsi nenegativni ostanek Fn pri deljenju z N: Fn . .n (mod N). Slika 5. Minimalna perioda .(N). Na sliki opazimo premice, opisane v izrekih 6 in 7. Primer. (a) Za N = 2 je zaporedje .n periodiˇcno z minimalno periodo 3, (0, 1, 1, 0, 1, 1, . . .). (b) Za N = 7 je zaporedje .n periodiˇcno z minimalno periodo 16, (0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, . . .). (c) Za N = 11 je zaporedje .n periodiˇcno z minimalno periodo 10, (0, 1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1, 1, 2, 3, 5, 8, 2, 10, 1, . . .). Lema 2. Prvi par, ki se ponovi v zaporedju parov (.1, .2), (.2, .3), . . . , (.n, .n+1), . . ., je par (1, 1). Dokaz. Ker je na jveˇc N2 razliˇcnih parov, poljubna mnoˇzica N2 + 1 parov vsebuje vsa j dva enaka para. Pa recimo, da je prvi par, ki se ponovi, enak (.k, .k+1), kjer je k > 1. Poiˇsˇcimo torej v zaporedju tak par (.r, .r+1), kjer je r > k, da velja .k = .r in .k+1 = .r+1. Iz de.nicije Fibonaccijevih ˇstevil sledi .r-1 = .r+1 - .r in .k-1 = .k+1 - .k, torej .r-1 = .k-1. To pa pomeni, da je (.r-1, .r) = (.k-1, .k). Toda (.k-1, .k) se v zaporedju po javi pred (.k, .k+1). To pa je v nasprotju z naˇso predpostavko, da je k > 1. Torej je k = 1. Lema 3. Za poljubno pozitivno celo ˇstevilo N obstaja med prvimi N2 Fibo­naccijevimi ˇstevili vsaj eno, ki je deljivo z N. Dokaz. Iz leme 2 sledi, da je (1, 1) prvi par v zaporedju, ki se ponovi. Torej je (.t, .t+1) = (1, 1) za neko celo ˇstevilo t, 1 < t . N2 + 1. Potem je Ft . 1 (mod N) in Ft+1 . 1 (mod N). Toda Ft-1 = Ft+1 - Ft in zato je Ft-1 . 0 (mod N). 1 1 Fn+1 Fn Na j bo B = . Potem je A = B2 in Bn = . 1 0 Fn Fn-1 ˇ Lema 4. Naj bo N > 2. Ce velja Fn . 0 (mod N) in Fn+1 . 1 (mod N), potem je ˇstevilo n sodo. Dokaz. Lema je ekvivalentna trditvi, da za N > 2 iz Bn . I (mod N) sledi, da je n sodo ˇstevilo. Ker je det B = -1, je det Bn = (det B)n = (-1)n . 1 (mod N). Torej je n sodo ˇstevilo. Dokaz izreka 1. Iz leme 2 in leme 3 sledi, da se vzorec 0, 1, 1 v zaporedju .0, .1, .2, . . . , .n, .n+1, . . . prviˇc ponovi za .t-1, .t, .t+1, kjer je 0 < t - 1 . N2 . Iz leme 4 sledi, da je t - 1 sodo ˇstevilo. Iz de.nicije minimalne periode pa dobimo, da velja 2.(N) . 2.(N) = t - 1, kar dokazuje izrek. Za preslikavo (1) iz pogo ja (3) in leme 4 sledi naslednja trditev: Trditev 5. Naj bo N > 2. Potem velja: (a) T je perioda preslikave (1), ˇce in samo ˇce je 2T perioda zaporedja (.n). (b) T je minimalna perioda preslikave (1), ˇce in samo ˇce je 2T minimalna perioda zaporedja (.n). Dyson in Falk [6] sta dokazala, da velja jo bistveno bolj stroge meje kot v izreku 1. Izrek 6. (a) .(N) = 3N, ˇce in samo ˇce je N = 2 × 5k, kjer je k = 1, 2, . . . (b) .(N) = 2N, ˇce in samo ˇce je N = 5k ali N = 6 × 5k, kjer je k = 0, 1, 2, . . . (c) .(N) . 12N za vse preostale N. 7 Primer. .(10) = 30, .(5) = 10, .(6) = 12, .(30) = 60, .(2) = 3, .(3) = 4. Lastnosti, ki jih je Wall v ˇclanku [11] dokazal za periode zaporedij (.n), sta Bao in Yang [3] z uporabo trditve 5 zdruˇzila v naslednje izreke: Izrek 7. Naj bo N praˇstevilo, veˇcje od 5. Potem za preslikavo (1) velja: ˇ (a) Ce je N oblike 10m ± 3, potem je N + 1 neka perioda preslikave (1). ˇ (b) Ce je N oblike 10m ± 1, potem je N-1 neka perioda preslikave (1). 2 Primer. Minimalna perioda pa je lahko ˇse bistveno manjˇsa: .(29) = 7, .(47) = 16, .(521) = 13, .(9349) = 19. ˇ .1 .2 .k Izrek 8. Ce ima N praˇstevilsko faktorizacijo N = p · p · · · p , potem 1 2 k .1 .k je .(N) najmanjˇsi skupni veˇckratnik ˇstevil .(p1 ), . . . , .(pk ). Se pravi, da moramo doloˇciti .(N) le ˇse za potence praˇstevil N = pM . Pri tem je p = 2 poseben primer. ˇ Izrek 9. Ce je p = 2, potem je .(2) = .(4) = 3. Za M . 2 pa je .(2M ) = 3 × 2M-2 . Primer. .(8) = 6, .(16) = 12, .(32) = 24. Za praˇstevila, veˇcja od 2, raˇcuni kaˇzejo, da je .(p2) > .(p). Velja pa Slika 6. Skrivno sporoˇcilo in njegov deseti iterat s preslikavo Arnoldove maˇcke. M Izrek 10. Naj za praˇstevilo p velja .(p Potem za N = pvelja 2)= .(p). ˇk) .(N) = pM-1.(p). Ce je k najveˇcje tako celo ˇstevilo, da velja .(p= .(p), potem je .(N) = pM-k.(p) za M > k. Primer. .(3) = 4, .(9) = 12, .(27) = 36, .(7) = 8, .(49) = 56, .(343) = 392. Posploˇsena diskretna preslikava Arnoldove maˇcke ˇ Ce v enaˇcbi (1) vzamemo matriko 1 + ab a A = , b 1 kjer sta a in b naravni ˇstevili, dobimo avtomor.zem torusa, sa j sta lastni vrednosti razliˇcni realni ˇstevili, katerih produkt je enak 1. Tako dobljeno preslikavo imenujemo posploˇsena diskretna preslikava Arnoldove maˇcke. Po­sploˇsena preslikava se uporablja v kriptogra.ji in steganogra.ji. Cilj kriptograf´ije (grˇsko krypt´os – skrit in gr´aphein – pisati) je narediti podatke neberljive, medtem ko je cilj kriptoanalize razkrivanje ˇsifriranih podatkov [7]. Osnovno sporoˇcilo po navadi imenujemo ˇcistopis (cleartext, plaintext), zaˇsifrirano pa ˇsifropis ali ta jnopis (kriptogram, ciphertext). Spo­roˇcilo po nekem algoritmu spremenimo v kriptirano sporoˇcilo. Doloˇcene vre­dnosti parametrov, ki jih uporabimo v algoritmu, imenujemo kljuˇc. Sogo­vornika se morata torej dogovoriti o algoritmu in kljuˇcu, da si lahko poˇsiljata ˇsifrirana sporoˇciji so ˇcilo zakodirali tako, da cila. V stari GrˇSpartanci sporoˇso na valj navili ozek trak in sporoˇcilo napisali pravokotno na smer traku. Naslovniku so potem poslali odvit trak in ˇce je ˇzelel sporoˇcilo prebrati, je moral trak naviti na valj z enakim premerom. Kljuˇc tega postopka je bil torej premer valja. Julij Cezar je sporoˇcila svo jim vo jskovodjem zakodiral tako, da je vsako ˇcrko zamenjal s ˇcrko, ki je bila po abecedi neka j mest za njo. Matematiˇcno tak naˇcin kodiranja lahko opiˇsemo kot f(a) . (a + k) (mod n), kjer je n ˇstevilo ˇcrk v abecedi, k pa kljuˇc. Takih sporoˇcil ni teˇzko deˇsifrirati, ˇce uporabimo statistiˇcno analizo ˇcrk, znaˇcilnih za doloˇcen jezik. Iz daljˇsega besedila ugotovimo frekvenco doloˇcenih ˇcrk v jeziku in s pri­merjavo frekvenc ˇcrk v kodiranem besedilu lahko relativno hitro ugotovimo, katera ˇcrka pomeni doloˇceno ˇcrko, in tako razˇsifriramo sporoˇcilo. Skozi zgo­dovino so z uporabo matematike razvili razliˇcne postopke ˇsifriranja. Pri moderni kriptogra.ji je algoritem kodiranja velikokrat znan, torej je pou­darek kriptoanalize na odkrivanju kljuˇca. Na Fakulteti za raˇcunalniˇstvo v Ljubljani prof. dr. Aleksandar Juriˇsi´c vodi Laboratorij za kriptogra.jo in ra­ˇcunalniˇsko varnost in na strani http://lkrv.fri.uni-lj.si/ je kar neka j literature s tega podroˇcja. Cilj steganogra.je (grˇsko steganos – prikrit in gr´aphein – pisati) je prikri­vanje obsto ja podatkov [10]. Stari Kita jci so npr. sporoˇcilo napisali na ozek svilen trak, ga tesno zvili, potopili v vosek in tako dobili voˇsˇcene kroglice, ki jih je nato pogoltnil sel. Med na jbolj znanimi metodami steganogra.je je zapis sporoˇcila s ˇcrnilom, ki je pri normalni sobni temperaturi nevidno. Ko list papirja segrejemo, pa se sporoˇcilo obarva rjavo. Kot ˇcrnilo lahko uporabimo na primer limonin sok, kis ali mleko. Ena od moˇznosti uporabe posploˇsene preslikave Arnoldove maˇcke v ste­ganogra.ji je, da vzamemo sliko, ki ji dodamo skrivno sporoˇcilo, ki ga pred tem transformiramo z eno ali veˇc razliˇcnimi preslikavami [8], [9]. Spremenjeno sliko nato poˇsljemo tistemu, ki mu ˇzelimo sporoˇciti skrivno sporoˇcilo. Z ustreznim kljuˇcem lahko naslovnik loˇci sliko od ˇsifriranega sporoˇcila. Pri tem je pomembno, da s prostim oˇcesom ne loˇcimo originalne slike od slike z dodanim sporoˇcilom, tako da slika ni sumljiva. Ker je ranljivost algoritmov veˇcja, ˇce je perioda preslikave kratka, je zelo pomembno poznavanje periode v odvisnosti od parametrov a, b in N [4,5]. Primer. Na sliki 6 je skrivno sporoˇcilo »OMF« in njegov deseti iterat. Na sliki 7 je na levi originalna slika muce, na desni pa je slika muce z dodanim skrivnim sporoˇcilom. Na vseh slikah je raster enak 124, zato ˇ je minimalna perioda .(124) = 15. Ce ima naslovnik, ki mu je sporoˇcilo namenjeno, originalno sliko muce, lahko dobi ˇsifrirano skrivno sporoˇCe cilo. ˇpozna ˇse kljuˇc, ki je v naˇsem primeru zaporedna ˇstevilka iterata, lahko dobi originalno skrivno sporoˇcilo. Ker smo sliki dodali deseti iterat sporoˇcila s preslikavo Arnoldove maˇcke, izraˇcunamo peti iterat ˇsifriranega sporoˇcila. Slika 7. Muca brez in s skrivnim sporoˇcilom. Neka j nalog 1. Vzemimo za A osnovno Arnoldovo matriko in raster N = 50. (a) Koliko je .(50)? (b) Ka j pa, ˇce se vpraˇsamo po minimalni potenci p, da je 0 0 Ap + I . (mod N), 0 0 seveda ˇce tak p sploh obsta ja? 7 3 2. Na j bo A posploˇsena Arnoldova matrika A = in raster N = 26. 2 1 Koliko je .(26)? Ka j pa, ˇce je raster N = 124? 1 + ab a 3. Ali na jdete ˇse kakˇsno hiperboliˇcno matriko, ki ni oblike A = ? b 1 4. Katera celoˇstevilska matrika dimenzije 2 × 2 ustreza enaˇcbi A3 . I (mod 5)? http://www.dmfa-zaloznistvo.si/ Reˇsitve: 1. (a) .(50) = 150. (b) 75. 2. .(26) = 14, .(124) = 14. 3 5 3 4 3. Primera takih matrik: 1 2 in 2 3 . 1 1 21 4. Primera takih matrik: in . 2 3 32 LITERATURA [1] V. I. Arnold, Mathematical Methods of Classical Mechanics, Springer, 1989. [2] V. I. Arnold in A. Avez, Ergodic problems in Classical Mechanics, Benjamin, New York, 1968. [3] J. Bao in Q. Yang, Period of the discrete Arnold cat map and general cat map, Non­linear Dynam. 70 (2012), 1365–1375. [4] F. Chen, K. Wong, X. Liao in T. Xiang, Period distribution of generalized discrete Arnold cat map for N = p e, IEEE T. Inform. Theory 58 (2012), 445–452. [5] F. Chen, X. Liao, K. Wong, T. Xiang, Q. Han in Y. Li, Period distribution of some linear maps, Commun. Nonlinear Sci. Numer. Simulat. 17 (2012), 3848–3856. [6] F. Dyson in H. Falk, Period of a Discrete Cat Mapping, Amer. Math. Monthly 99 (1992), 603–614. [7] Kriptogra.ja, dostopno na: http://www.egradiva.net/moduli/upravljanje\_ik/ 14\_kriptiranje/01\_datoteka.html, ogled 3. 6. 2015. [8] M. Mishra, A. R. Routray in S. Kumar, High Security Image Steganography with Modi.ed Arnold’s Cat Map, Int. J. Comput. Appl. 37 (2012), 16–20. [9] S. Rawat in B. Raman, A chaotic system based fragile watermarking scheme for image temper detection, Int. J. Electron. Commun. 65 (2011), 840–847. [10] Steganogra.ja, dostopno na: http://www.monitor.si/clanek/skrivanje­podatkov-steganografija/123365/?xURL=301, ogled 3. 6. 2015. [11] D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67 (1960), 525–532. http://www.dmfa-zaloznistvo.si/ http://www.obzornik.si/