Lukuteoriasta viestin salaamiseen 1

Aloitan tässä kirjoitusten sarjan, jonka tavoitteena on selvittää, kuinka lukuteorian matemaattisia ideoita käytetään nykyaikaisessa tietotekniikassa viestien salaamiseen. Tähän törmäämme esimerkiksi silloin kun netin kautta maksamme laskujamme pankkiin ja meille on avautunut ns. suojattu yhteys.

Aluksi siis muutama kirjoituskerta tarvittavia käsitteitä ja laskennallisia apuneuvoja.

Alkuluvut
Alkuluvut ovat ykköstä suurempia positiivisia kokonaislukuja, jotka ovat jaollisia vain ykkösellä ja itsellään. Alkulukuja ovat siten 2, 3, 5, 7, 11, 13, 17, ... . Sen testaamiseen, onko joku luku alkuluku vai ei, joudutaan periaatteessa kokeilemaan jaollisuutta kaikilla tutkittavaa lukua pienemmillä alkuluvuilla. Käytännössä tätä helpottaa se, että jos tutkittavana on luku n, riittää tutkia jaollisuutta lukua &radic n pienemmillä alkuluvuilla. Hyvin suurilla alkuluvuilla tämän testaaminen tietokoneellakin on erittäin vaativa tehtävä ja siihen viestien salaaminen perustuukin. Tällä hetkellä suurin löydetty alkuluku on 2 ^{32 582 657} -1. Luvussa on 9 808 358 numeroa! Jos tätä alkulukua pienempiä lukuja pystyttäisiin tutkimaan nopeudella 10 ^-9 s/kpl, lukujen läpikäyminen kestäisi noin 10 ^{9 808 340} vuotta ja siinä ajassa avattava viesti on kyllä ehtinyt vanhentua :) . Lisää osoitteessa http://primes.utm.edu/largest.html

Jakoyhtälö
Kun luku 147 jaetaan jakokulmassa luvulla 11, saadaan (vaillinaiseksi) osamääräksi 13 ja jakojäännökseksi jää vielä 4. Tämä voidaan kirjoittaa ns. jakoyhtälönä seuraavasti: 147 = 13 * 11 + 4.

Siis jaettava = osamäärä * jakaja + jakojäännös,

missä jakojäännös on aina pienempi kuin jakaja.

Vielä toinen esimerkki: jaettaessa luku 65432 luvulla 234 saadaan jakoyhtälöksi 65432 = 279 * 234 + 146.

Muurahaisten matematiikkaa

Kesäloman pitkän tauon jälkeen yritän taas tuottaa tänne uutta lukemista.

Lomalla lehtiä selatessani näin Tiede -lehdessä (nro 7/2008, s. 46) mielenkiintoisen jutun muurahaisten suunnistamisesta takaisin pesälleen vaelluksen jälkeen. Idea perustuu siihen, että muurahainen pystyy aistimaan auringon säteiden tulosuunnan myös pilvisenä päivänä ja tämän lisäksi reksiteröimään ajankulun (ja siten tasaisella nopeudella liikkuessaan myös matkan) eri matkaetapeilla. Tällöin etapeista muodostuneen kokonaiskulman α (ja siten kulman takaisin pesälle) muurhainen saa kaavasta




Tuo on siis painotettu keskiarvo kulkukulmista kun painokertoimina ovat kuljetut matkat (tai etappeihin käytetyt ajat). Kaavan antama tulos ei ole tarkka arvo, mitä Tiede -lehti ei kyllä mitenkään kommentoinut. Pienillä kulmamuutoksilla kaava antaa kyllä varsin tarkkoja tuloksia. Kaavan antaman pienen virheen voi helposti todeta vaikkapa vektoreilla ja kahden etapin taivallusta tarkastellen.