Äärelliset kätköt / Finite caches Mystery Cache

• 10 aiemman ranto-mysteerin loppukoordinaattien tietämystä
• hieman äärellisten kuntien laskentaa, jonka voi hoitaa weppi-laskurilla
• pientä yritystä myös purkin noutoon
• ONKIMINEN EI ENÄÄ ONNISTU

To log this cache you probably need to solve all 10 previous ranto mysteries and a bit more. If you are still interested, please contact me for an English translation.

Äärelliset kunnat

16 alkion kunta

Tarkastelemme esimerkkinä 16 alkion kuntaa, koska sitä käytetään lopulta kätkön koordinaattien laskemiseen. Siinä on siis 2⁴ "lukua" eli se saadaan 2 alkion kunnasta 4-asteisena laajennuksena. Meillä on siis 2 alkion alkukunta {0,1}, jossa lasketaan modulo 2. Lisäksi otamme alkion a, joka toteuttaa 4-asteisen polynomiyhtälön a⁴+a+1=0. Koska kaikki "normaalit" laskusäännöt ovat voimassa, nämä ehdot määräävätkin tämän kunnan yksikäsitteisesti.

Kunnan alkiot voidaan esittää a:n potensseina: 0, 1, a, a², ..., a¹⁴. Koska kunta on äärellinen, niin myös potenssit toistavat kehää: a¹⁵ = a⁰ =1. Potenssiesitys on hyvä kertolaskuissa, koska esimerkiksi a⁶ * a¹⁴ = a²⁰ = a⁵. Samalla tulee hoidettua myös jakolaskut: koska aⁱ * a^15-i = 1, niin 1/aⁱ = a^15-i.

Yhteenlaskuissa edullisempi esitys on sellainen, jossa a:n korkeammat potenssit esitetään alle neliasteisina polynomeina: esimerkiksi a⁴ = -(a+1) = a+1, koska modulo 2 miinusmerkit voidaan unohtaa -1=1. Samalla tavalla voidaan listata muutkin potenssit:

Tästä kunnasta käytetään monesti merkintää GF(16) (Galois Field) suuren matemaatikon Évariste Galois'n muistoksi, jolle nämä kunnat tulivat ensimmäisenä mieleen.

Virheitä korjaavat koodit

Jos olet ihmetellyt, kuinka naarmuinen cd-levysi soi napsumatta tai digi-tv kuva on niin selvä (paitsi pikselöityessään), niin syynä on ns. virheitä korjaavat koodit (error correcting codes), joita nykyään löytyy lähes kaikista digitaalisista tiedonsiirtojärjestelmistä (GSM, 3G, LTE, DVB-T/C/S, jne.). Suuri osa virheitä korjaavista koodeista on suunniteltu käyttäen äärellisiä kuntia - erityisesti 2^m alkion kuntia, koska tietokoneet esittävät tiedon binäärilukuina. Nythän esimerkiksi 8 bitin tavu (byte) voi saada 2⁸=256 eri arvoa ja ne voidaan helposti ajatella kunnan GF(256) alkioina.

Virheitä korjaavien koodien toiminta perustuu ylimääräiseen toistoon: jos vain data lähetetään ilman toistoa, ei voida päätellä, menikö tiedonsiirrossa joku bitti väärin. Esimerkiksi bittijono 11101 voidaan lähetetään muodossa 11101 101, jossa 101 ovat tarkistusbittejä. Toisinpäin voidaan ajatella, että kaikki 8-bittiset sanat eivät ole oikeita koodisanoja, vaan ainoastaan jokin sovittu osajoukko.

Reedin-Salomonin koodit

Cd-levyissä käytetään virheen korjaukseen Reedin ja Salomonin kehittämää RS-koodia. Cd-levyissä käytetään RS-koodia kunnassa GF(256), mutta tässä kätkökuvauksessa käytämme yksinkertaisuuden vuoksi kuntaa GF(16). Koodisanojen osajoukko valitaan valitsemalla polynomien osajoukko kaikkien polynomien joukosta.

Otetaan esimerkiksi alle 8-asteiset polynomit kunnassa GF(16). Ne voidaan esittää muodossa

Kun data koodataan ylläesitetyllä tavalla sallituiksi koodisanoiksi lisäämällä 8 datasymboliin 8 tarkistussymbolia, saadaan korjattua 3 virheellistä symbolia mistä paikasta tahansa Berlekampin ja Masseyn algoritmilla. Tämä paljon käytetty algoritmi on kuitenkin sen verran hankala, etten viitsi sitä tässä esitellä. Tiedonjanoiset löytävät kyllä kuvauksia netistä.

Jossain tilanteissa virheellisten symbolien paikat tiedetään ja silloin homma muuttuu selkeämmäksi ja yllämainitulla koodilla pystytään korjaamaan jopa 8 virheellistä symbolia. Silloin 8 polynomin arvoa laskettuna tiedetyillä kunnan alkioilla on oikein ja saadaan 8 lineaarista yhtälöä ja 8 muuttujaa ja tämä lasku on ratkaistavissa. Kyseessä on lineaarisen yhtälöryhmän ratkaiseminen ihan samoin kuin reaaliluvuilla tai muissa "normaaleissa" lukukunnissa. Ne, jotka ovat pyöritelleet matriiseja, huomaavat, että kyseessä on 8*8-matriisin kääntäminen.

Varsinaisen tehtävän helpottamiseksi kuvailen, minkämuotoisia lausekkeita polynomeista saadaan. Esimerkiksi yllämainitun polynomin p(x) arvot kunnan alkioilla 0, 1 ja aⁱ ovat

Kätkön koordinaattien laskeminen

Varmista ensin, että sinulla on tsekkerin hyväksymät tai ehdottamat koordinaatit kaikilta aiemmilta ranto-mysteerikätköiltä, joissa tsekkeri on. Laske pohjoisten minuuttien desimaalit xxx yhteen kaikilta 10 kätköltä: olkoon tuo luku JKLM. Laske itäisten minuuttien desimaalit yyy yhteen kaikilta 10 kätköltä: olkoon tuo luku RSTU. Käytetään seuraavaa vastaavuutta numeroiden 0-9 ja kunnan GF(16) alkioiden välillä:

Etsi sitten sellainen alle 8-asteinen GF(16)-kertoiminen polynomi p(x), joka toteuttaa yhtälön

Purkin löydät koordinaateista:

Magma-laskin avuksi

En ole niin julma, että pistäisin ketään kääntämään 8*8-matriisia kunnassa GF(16) kynällä ja paperilla, vaan siihen löytyy työkalu wepistä. MAGMA on kaupallinen algebran laskentaan tarkoitettu ohjelmisto, mutta sen kevyt-versio Magma Calculator on ilmaiseksi käytettävissä. Tässä esimerkkinä koodinpätkä, joka hakee polynomin, joka saa arvot 23456789 pisteissä 0, 1, a, a², a³, a⁴, a⁵, a⁶.

F<a>:=GF(2^4);
M := Matrix(F, 8, [1,   0,   0,    0,    0,    0,    0,    0,
                   1,   1,   1,    1,    1,    1,    1,    1, 
                   1,   a,   a^2,  a^3,  a^4,  a^5,  a^6,  a^7,
                   1,   a^2, a^4,  a^6,  a^8,  a^10, a^12, a^14,
                   1,   a^3, a^6,  a^9,  a^12, a^15, a^18, a^21, 
                   1,   a^4, a^8,  a^12, a^16, a^20, a^24, a^28,
                   1,   a^5, a^10, a^15, a^20, a^25, a^30, a^35,
                   1,   a^6, a^12, a^18, a^24, a^30, a^36, a^42 ]);
b := Matrix(F, 1, [a^2, a^3, a^4,  a^5,  a^6,  a^7,  a^8,  a^9 ]);
c := M^-1*b;
f := Polynomial(F, [c[1,1], c[2,1], c[3,1], c[4,1], c[5,1], c[6,1], c[7,1], c[8,1]]);
for d in F do
  [d, Evaluate(f,d)];
end for;

En ole myöskään niin kiltti, että tuolla ohjelmanpätkällä saisi suoraan oikeat naatit, vaan sitä pitää pikkaisen muokata kysyttyyn tilanteeseen. Happy hunting.