torstai 11. syyskuuta 2008

Lukuteoriasta viestin salaamiseen 4

Ja nyt sitten viimeinen valmisteleva paketti viestien salaamisen matematiikkaan. Tämän kerran käsitteenä

Kongruenssi

Määritelmä: Kokonaisluvut a ja b ovat kongruentit modulo n jos lukujen erotus a - b on jaollinen luvulla n, tämä merkitään
a\equiv b\; (mod\; n).
Esimerkki
78\equiv 48\; (mod\; 15),
koska 78 - 48 = 30 ja 30 on jaollinen luvulla 15.

Jokainen luku a on kongruentti sen jakojäännöksen kanssa, joka saadaan kun a jaetaan n:llä. Esimerkiksi 27 = 4*6 + 3, joten 27\equiv 3\; (mod\; 6)
ja tämähän on totta edellä olleen kongruenssin määritelmän mukaan: 27 - 3 on 24 ja 24 on jaollinen 6:lla.

Näin kongruenssin avulla löydetään pienempiä, helpommin käsiteltäviä lukuja b, joilla on sama jakojäännös kuin alkuperäisellä luvulla a jaettaessa sitä luvulla n. Näitä yksinkertaistamisia tehtäessä lausekkeissa yhteenlaskettavat, tulontekijät ja potenssien kantaluvut voidaan korvata kongruenteilla luvuilla (eksponentteja ei voi korvata).

Esimerkki Tutki, mikä on jakojäännös, kun luku
155 + 790\ast 25^{213}
jataan luvulla 3.

Ratkaisu Nyt 155\equiv 2(mod3), \; \; 790\equiv 1(mod3)\; \; ja\; 25\equiv 1(mod3),
joten
155+790\ast 25^{213}\equiv 2+1\ast 1^{213}\equiv 3\equiv 0(mod\; 3),
ja siten alussa annetun luvun jakojäännös kolmella jaettaessa on 0, eli jako menee tasan.
Esimerkki Laske luvun 2^{99} viimeinen numero.
Ratkaisu. Kun kymmenjärjestelmässä halutaan selvittää luvun viimeinen numero, tutkitaan mitä jää jakojäännökseksi kun luku jaetaan 10:llä. Siksi ryhdytään tutkimaan kongruensseja modulo 10. Kokeillen selvitetään ensin jokin luvun 2 potenssi, joka olisi yksinkertainen tarkasteltaessa modulo 10 ryhmää. Näin
2^{2}=4\equiv -6(mod10),\; 2^{3}=8\equiv -2(mod10), 2^{4}=16\equiv 6(mod10)
kunnes löytyy
2^{5}=32\equiv 2(mod\; 10).

Nyt tätä ja potenssin laskusääntöjä käyttäen saadaan
2^{99}\equiv 2^{5\ast 19+4}\equiv 2^{4}\ast \left(2^{5} \right)^{19}\equiv 2^{4}\ast 2^{19}\equiv 2^{23}
\equiv 2^{5\ast 4+3}\equiv 2^{3}\ast \left(2^{5} \right)^{4}\equiv 2^{3}\ast 2^{4}\equiv 2^{7}\equiv 2^{2}\ast 2^{5}
\equiv 2^{2}\ast 2\equiv 8\; (mod\; 10).
Näin annetun luvun 2^{99} viimeinen numero on 8
Lähettänyt klo
Tunnisteet: ,

Ei kommentteja:

Lähetä kommentti

Tilaa: Lähetä kommentteja (Atom)