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.