tiistai 30. syyskuuta 2008

Kaprekarin vakio


Toukokuussa (26.05.2008) kirjoitin, että lukuteoreetikoille luvut eivät ole pelkästään numerosarjoja vaan usein hahmon saaneita jokapäiväisessä elämässä esiin putkahtelevia olioita. Eräs tällainen luku on Kaprekarin vakio, joka on saanut nimensä intialisen matemaatikon D.R. Kaprekarin mukaan.

Valitse mielivaltainen nelinumeroinen luonnollinen luku. Muodosta sen numeroista mahdollisimman suuri ja pieni luku. Vaähennä ne toisistaan. Menettele saamasi luvun kanssa samoin kuin edellä ja jatka toistamista. Korkeintaan seitsemän toiston jälkeen päädyt Kaprekarin vakioon.

Esimerkiksi valitaan luku 2008.
8200 - 0028 = 8172
8721 - 1278 = 7443
7443 - 3447 = 3996
9963 - 3996 = 6264
6642 - 2466 = 4176
7641 - 1467 = 6174.

Ja niin on päädytty Kaprekarin vakioon.

Luku 6174 on samalla myös Harshadin luku eli Nivenin luku, on siis jaollinen numeroidensa summalla (6174 = 343 * 18).

Asiasta enemmän: http://www.math.hmc.edu/funfacts/ffiles/10002.5-8.shtml
Lähettänyt klo Ei kommentteja:
Tunnisteet: ,

maanantai 29. syyskuuta 2008

Kaksi uutta Mersennen alkulukua

Syyskuun 16. pnä 2008 julkistettiin tieto 45. ja 46. Mersennen alkuluvun löytymisestä. The Great Internet Mersenne Prime Search (GIMPS) projekti tuotti jälleen tulosta. Pienemmän luvun löysi Hans-Michael Elvenich 06.09.2008 ja suuremman Edson Smith 23.08.2008.

Mersennen luvut ovat muotoa
M_{n}=2^{n}-1
ja muutamat ensimmäiset ovat siis 1, 3, 7, 15, 31, 63, 127. Mersennen alkuluvut ovat Mersennen lukuja, jotka ovat myös alkulukuja. Esimerkiksi
M_{7}=2^{7}-1=127
on Mersennen alkuluku.

Nyt löytyneet uudet Mersennen alkuluvut ovat
2^{37156667}-1
ja
2^{43112609}-1

Ensiksi mainitussa on 11 185 272 ja jälkimmäisessä 12 978 189 numeroa kymmenjärjestelmäesityksessä ja niinpä nämä ovat nyt kaksi suurinta tunnettua alkulkua (vrt kirjoitukseni 27.08.2008).

Asiasta enemmän: http://mathworld.wolfram.com/news/2008-09-16/mersenne-45-46/
Lähettänyt klo Ei kommentteja:
Tunnisteet: , , , , ,

sunnuntai 28. syyskuuta 2008

Esimerkki viestin salaamisesta ja purkamisesta

Nytpä sitten numeerinen esimerkki viime kerran teoriaan. Tässä mukana paljon kongruenssien pyörittämistä laskimella käsiteltävien kokoisiksi.

A1. Valitaan alkuluvuiksi (nyt pienet) p = 19 ja q = 23.
A2. m = pq = 437
A3. b = (p - 1)(q - 1) = 396
A4. Valitaan a = 7

Näin on saatu viestien salaamisen avain m = 437 ja a = 7

B1. Muodostetaan Diofantoksen yhtälö ax - by = 1
siis 7x - 396y = 1

Eukleideen algoritmilla
396 = 56*7 + 4
7 = 1*4 + 3
4 = 1*3 + 1
3 = 3*1 + 0

Ratkaistaan jakojäännökset
4 = 396 - 56*7
3 = 7 - 1*4
1 = 4 - 1*3

Ja nyt viimeisestä jakojäännöksiä edeltä sijoittaen saadaan
1 = 4 - 1*3
= 4 - 1*(7 - 1*4) = -1*7 + 2*4
= -1*7 + 2*(396-56*7) = -113*7 + 2*396

Siten 7*(-113) + 396*2 = 1 ja alkuperäise diofantoksen yhtälön yhtenä ratkaisuna on x = -113 ja y = 2.

Nyt saatu x:n arvo ei negatiivisena tarkoitukseemme käy ja siten joudun täydentämään 10. syyskuuta kirjoitettua Diofantoksen yhtälöiden teoriaa. Jos yhtälön eräät ratkaisut ovat x_{o} ja y_{o}, niin yleinen ratkaisu on
\begin{matrix} x=x_{o}+\frac{b}{syt(a,b)}*n\\ y=y_{o}-\frac{a}{syt(a,b)}*n \end{matrix}

Nyt tämän avulla löydämme x:lle ensimmäisen positiivisen ratkaisun -113 + 396 = 283 ja näin on nyt saatu purkuavain t = 283.

C1. Lähettäjä haluaa lähettää meille viestin 355, siis s = 355
C2. Viestin hän kryptaa saamillaan salausavaimilla muotoon
z=355^{7}(mod437)\equiv 355^{3}*355^{3}*355
josta edelleen jakoyhtälöa ja sen antamaa jakojäännöstä käyttäen saadaan
\equiv 126*126*355\equiv 565\: 5980\equiv 428(mod437)
ja näin hän lähettää meille salatun viestin z = 428.

D1. Viestin purkaminen tapahtuu kaavasta
s=z^{t}(mod\; m)

Nyt siis jakoyhtälöitä, jakojäännöksiä ja kongruensseja käyttäen saadaan
s=428^{283}\equiv \left(428^{2} \right)^{141}*428\equiv 81^{141}*428
\equiv \left(81^{2} \right)^{70}*81*428\equiv 6^{70}*81*428\equiv \left(6^{7} \right)^{10}*81*428
\equiv 256^{10}*81*428\equiv \left(256^{2} \right)^{5}*81*428\equiv 423^{5}*81*428
\equiv 423^{2}*423^{2}*423*81*428
\equiv 196*196*423*428*81
\equiv 204*81\equiv 355(mod\; 437)
ja niin lähettäjän lähettämä viesti 355 kulki välin niin salattuna, että se vieraisiin käsiin joutuessaankin pysyy salaisena.
Lähettänyt klo Ei kommentteja:
Tunnisteet: , ,

keskiviikko 24. syyskuuta 2008

Julkinen salakirjoitus RSA-menetelmällä

Nyt sitten edellä olleiden työkalujen esittelyn jälkeen itse salakirjoittamiseen ja sen purkamiseen.

A. Julkisen salakirjoitusavaimen muodostaminen
A1. Valitse kaksi suurta alkulukua p ja q
A2. Laske niiden tulo m = pq
A3. Laske Eulerin funktion arvo b = &phi(m)=(p-1)(q-1)
A4. Valitse jokin kokonaisluku a &ge 2, jolla ei ole yhteistä tekijää luvun b kanssa.

Luvut m ja a muodostavat sinulle lähetettävän viestin salausavaimen. Ne voidaan julkistaa vaikkapa lehdessä tai internetissä. Huomattavaa on, että julkistetun luvun m perusteella ei voida saada selville lukua b muutoin kuin löytämällä m:n tekijät p ja q. Tämä on taas ylivoimainen tehtävä tehokkaimmillekin tietokoneille jos p ja q ovat kyllin suuria. (Kts. teksti 27. elokuuta alkuluvuista)

B. henkilökohtaisen purkuavaimen muodostaminen
B1. Määritä Eukleideen algoritmilla yhtälölle ax - by = 1 jokin ratkaisu x = t ja y = u. (Kts. kirjoitukset 1. ja 10. syyskuuta)
- ratkaisu on olemassa, koska syt(a,b) = 1
- ratkaisu x = t toteuttaa yhtälön at = 1 bu = 1 + u&phi (m)

Luku t muodostaa purkuavaimen, jota ei anneta muilla vaan säilytetään tarkasti. Tämän purkuavaimen selvillesaaminen edellyttää yhtälön ax - by = 1 ratkaisemista, mikä taas edellyttää luvun b tuntemista, eikä tämä siis onnistu tietokoneellakaan, jos alun alkuluvut on valittu suuriksi.

C. Viestin salaaminen ja lähettäminen
C1. Lähettäjä kirjoittaa sanomansa luvuksi s, missä 0 &le s < m
C2. Lähettäjä kryptaa sanomansa s luvuksi
z=s^{a}\; (mod\; m)
- tämä onnistuu, koska luvut a ja m ovat julkisia
C3. Lähettäjä lähettää sinulle luvun z.

D. Vastaanotetun sanoman purkaminen
D1. Saatuasi viestin z laske potenssi
z^{t}\; (mod\; m)
käyttämällä henkilökohtaista purkuavaintasi t. Saat tulokseksi alkuperäisen sanoman s. Miksi? Siksi, että
z^{t}=(s^{a})^{t}=s^{at}=s^{1+u\varphi (m)}=s\cdot (s^{\varphi (m)})^{u}
ja Eulerin lauseen perusteella on
s^{\varphi (m)}\equiv 1\; (mod\; m), joten
z^{t}=s\; (mod\; m)

Seuraavalla kerralla vielä konkreettinen esimerkki yllä olevasta, tosin hyvin pienillä luvuilla, koska niilläkin siitä tulee käsin laskien aika työläs.
Lähettänyt klo Ei kommentteja:
Tunnisteet: , ,

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 Ei kommentteja:
Tunnisteet: ,

keskiviikko 10. syyskuuta 2008

Lukuteoriasta viestin salaamiseen 3

Diofantoksen yhtälöistä

Olkoot a, b ja c kokonaislukuja. Kun yhtälölle

ax + by = c

pyritään löytämään kokonaislukuratkaisut x ja y, puhutaan (ensimmäisen kertaluvun) Diofantoksen yhtälöstä. Ratkaisun olemasssaolo riippuu vakioista a, b ja c siten, että yhtälöllä on ratkaisu jos luku c on jaollinen luvulla syt(a,b). Ratkaisun etsiminen perustuu edellisen kirjoituksen (01.09.2008) Eukleideen algoritmiin. Ratkaistaan esimerkkinä yhtälö

95x + 51y = 1 (1)

Ratkaisun olemassaolo:

95 = 1*51 + 44
51 = 1*44 + 7
44 = 6*7 + 2
7 = 3*2 + 1
2 = 2*1 + 0

Siten syt(95,51) = 1 ja yhtälö (1) oikeapuoli 1 on jaollinen tällä suurimmalla yhteisellä tekijällä. Näin yhtälöllä (1) on ratkaisu. Itseasiassa aina kun Diofantoksen yhtälöllä on ratkaisu, niitä on samalla ääretön määrä.

Suurimman yhteisen tekijän etsimisen jakoyhtälöketjusta ratkaistaan seuraavaksi jokaiselta riviltä jakojäännös.

95 = 1*51 + 44 => 44 = 95 - 1*51
51 = 1*44 + 7 => 7 = 51 - 1*44
44 = 6*7 + 2 => 2 = 44 - 6*7
7 = 3*2 + 1 => 1 = 7 - 3*2
2 = 2*1 + 0.

Tämän jälkeen lähdetään liikkeelle pienimmästä nollasta poikkeavasta jakojäännöksestä 1 = 7 - 3*2 ja sijoitetaan tämän lopussa esiintyvän luvun 2 paikalle edelliseltä riviltä ratkaistu jakojäännös ja näin saatuun lausekkeeseen taas edelliseltä rivilt jakojännös j.n.e aina ketjun ylimmälle riville asti.

Siis
1 = 7 - 3*2
= 7 - 3*(44 - 6*7) = 7 - 3*44 + 18*7 = -3*44 + 19*7
= -3*44 + 19*(51 - 1*44) = -3*44 + 19*51 - 19*44 = 19*51 - 22*44
= 19*51 - 22*(95 - 1*51) = 19*51 - 22*95 + 22*51 = -22*95 + 41*51.

Näin yhtälöketjun ensimmäisen ja viimeisen lausekkeen avulla saamme

-22*95 + 41*51 = 1 (2)

Kun vertaamme tätä yhtälöön (1), voimme todeta, että yhtälön yhtenä ratkaisuna on x = -22 ja y = 41.

Jos meillä olisi ollut yhtälössä (1) oikealla puolella vakion 1 tilalla luku 3, siis

95x + 51y = 3 , (3)

olisi toimittu yllä olevan mukaisesti ja lopussa saatu yhtälö (2) olisi vielä kerrottu puolittain kolmella, jolloin olisimme saaneet

-66*95 + 123*51 = 3 (4)

ja nyt yhtälöitä (3) ja (4) vertaamalla olisimme saaneet ratkaisuksi x = -66 ja y = 123.
Lähettänyt klo Ei kommentteja:
Tunnisteet: ,

maanantai 1. syyskuuta 2008

Lukuteoriasta viestin salaamiseen 2

Suurin yhteinen tekijä

Jos a on positiivinen kokonaisluku, niin jokaista positiivista kokonaislukua, jolla luku a on jaollinen, sanotaan luvun a tekijäksi.

Kun luvut a ja b ovat positiivisia kokonaislukuja, niin lukujen a ja b yhteisistä tekijöistä suurin on lukujen a ja b suurin yhteinen tekijä, merkitään syt(a,b) (engl. gcd(a,b)).

Jos positiivinen luku a on jaollinen kokonaisluvulla b, on syt(a,b)= b.

Jos positiivinen luku a ei ole jaollinen kokonaisluvulla b, voidaan edellisen kirjoituksen (Lukuteoriasta viestin salaamiseen 1) mukaisesti kirjoittaa jakoyhtälö

a = qb + c .

Nyt voitaisiin kohtuullisen helposti todistaa, että jos luku k on lukujen a ja b yhteinen tekijä, se on myös lukujen b ja c yhteinen tekijä. Ja myös vastakkaiseen suuntaan: jos luku k on lukujen b ja c yhteinen tekijä, se on välttämmättä myös lukujen a ja b yhteinen tekijä.

Näin lukujen a ja b suurimman yhteisen tekijän etsiminen voidaan muuttaa pienempien lukujen b ja c suurimman yhteisen tekijän etsimiseen, joka taas voidaan edelleen muuttaa jakoyhtälön avulla yhä pienempien lukujen käsittelyyn, kunnes lopulta päädytään tilanteeseen, jossa löytyy keskenään jaolliset luvut. Jakoyhtälöiden ketjussa viimeinen nollasta poikkeava jakojäännös on alkuperäisten lukujen aja b suurin yhteinen tekijä. Tätä menetelmää sanotaan Eukleideen algoritmiksi.

Esimerkki Määritä lukujen 2064 ja 1572 suurin yhteinen tekijä.

Kirjoitetaan jakoyhtälöt

2064 = 1 * 1572 + 492
1572 = 3 * 492 + 96
492 = 5 * 96 + 12
96 = 8 * 12 + 0

Siten syt(2064,492) = 12.
Lähettänyt klo Ei kommentteja:
Tunnisteet: ,
Tilaa: Blogitekstit (Atom)