Uusi suuri alkuluku löydetty

Lokakuun 22. päivänä LiveSience-lehti ilmoitti, että jälleen on suurin tunnettu alkuluku vaihtunut. Uusi luku lyö aiemman ennätysluvun pituudessa 16 miljoonalla numerolla!

Nyt löytynyt luku on 2^136 279 841 - 1, siis jälleen ns. Mersennen alkuluku eli on muotoa 2^p - 1. Luvussa on 41 024 320 numeroa. Edellinen ennätysluku oli 2^82 589 933 - 1. Jos tämän uuden luvun kirjoittaisi näkyviin 3 numeroa senttimetrillä, luvulle tulisi pituutta noin 137 kimolmetriä. Merkkeinä tämä vastaa noin 12 raamatun kaikkien kirjoitettujen merkkien määrää.

Tämä uuden luvun löytämiseen matematiikan amatööri Luke Durant käytti avoimesti saatavaa ohjelmaa Great Internet Mersenne Prime Search eli GIMPS. Hän hyödynsi tuhansia grafiikkaa prosessoivaa yksikköä 24 datakeskuksessa 17 eri maassa.

Löydöstään Luke Durant kuittasi 3000 dollarin palkkion GIMPS-yhteisöltä. 150 000 dollarin palkkio odottaa ensimmäistä sadan miljoonan numeron ylittävän luvun löytäjää ja vastaavasti biljoonan nuemron ylitys tuottaa 250 000 dollaria!

Matematiikan historiassa 21. kesäkuuta

Vuonna 1976 kesäkuun 21. päivänä Kenneth Appel ja Wolfgang Haken ilmoittivat, että he olivat tietokeneen avustamana todistaneet neliväriongelman. Koska todistamisessa käytettiin tietokonetta, kaikki eivät heti hyväksyneet todistusta, mutta nykyään matemaatikot pitävät todistusta oikeana. Nykyäänkään kunnollista "vanhan ajan todistusta" asialle ei ole voitu esittää.

Vuonna 1963 Donald B Gillies löysi kolme uutta alkulukua. Kun tulokset oli vahvistettu, UIUC matematiikan laitos (jolla oli oma postitoimisto) käytti yllä olevaa postileimaa kaikessa postissaan vuosina 1964 - 1976. Kun Appel ja Haken todistivat neliväriongelman, luotiin uusi postileima.

Matematiikan historiassa 16. huhtikuuta

Vuonna 1866 huhtikuun 16. päivän kokouksessa professori Cayley kiinnitti huomiota teoreemaan, jonka mukaan kahden peräkkäisen alkuluvun väli voi ylittää minkä tahansa annetun luvun N - 1. Koska jos a, b, c, ... k ovat alkulukuja, jotka eivät ole suurempia kuin N, niin luvuista abc ...k+1 ja abc ...k+1+N voi toinen tai molemmat olla alkulukuja, mutta kaikki välillä olevat luvut ovat yhdistettyjä lukuja, joten ero kahden peräkkäisen alkuluvun välillä on vähintään N.

Kuva: Wikipedia

Matematiikan historiassa tänään 15. marraskuuta

Näyttää siltä, että Rene Descartes oli ensimmäinen matemaatikko, joka esitti, että parittomiakin täydellisiä lukuja voi olla olemassa. Kirjessään Mersennelle 1. marraskuuta 1638 hän toteaa, että hän voisi osoittaa että jokaisen parittoman täydellisen luvun on oltava muotoa p*s^2, jossa p on alkuluku. Edelleen hän totesi ettei hän näe mitään syytä, joka estäsi parittomien täydellisten lukujen olemassaolon ja mainitsee esimerkkinä p = 22021 ja s = 3 * 7 * 11 * 13. Tällöin ps^2 olisi pariton täydellinen luku jos leikittäisiin, että 22021 on alkuluku. Näin siis Descartes (luku 22021 ei ole alkuluku vaan 22021 = 19 *19* 61).

Eukleides osoitti, että 2^(n-1)*(2^n - 1) on täydellinen luku aina kun 2^n - 1 on Mersennen alkuluku. Vasta vuonna 1747 Leonhard Euler todisti, että kaavalla voidaan tuottaa kaikki parilliset täydelliset luvut. Ei kuitenkaan tiedetä, onko olemassa parittomia täydellisiä lukuja. Tiedetään kuitenkin, että parittoman täydellisen luvun täytyy olla suurempi kuin 10^300 ja sillä täytyy olla vähintään 8 alkulukutekijää, mikäli se on olemassa. Jos luku ei ole kolmella jaollinen, alkulukutekijöitä on vähintään 11.

Kuva: Wikipedia

Matematiikan historiassa tänään 10. marraskuuta

Marraskuun 10. päivänä 1951 julkistettiin useita "suurimpia" alkulukuja Naturessa. Edelliset 75 vuotta suurin tunnettu alkuluku oli 2^127 - 1. Luvun löysi Edouard Lucas, ranskalainen matemaatikko, joka tunnetaan parhaiten tutkimuksistaan Fibonaccin lukujonosta. Lucas osoitti löytämänsä luvun alkuluvuksi käsin laskemalla. Testaamiseen kului aikaa 19 vuotta!

Kuva:Wikipedia

Uusia havaintoja alkulukujen maailmasta

Tällä viikolla ilmestyneessä Tekniikan Maailman uutiskirjeessä kerrottiin uusia, merkittäviä havaintoja alkulukuihin liittyen. Alkulukujen esiintyminen näyttää noudattavaan samaa kaavaa kuin ns. kvasikiteiden piikkien esiintyminen.

Princetonin yliopiston tutkijat ovat havainneet alkulukujen ja kidemäisten materiaalien atomirakenteen välillä yllättävän yhteyden. Tutkijoiden mukaan havainto voi johtaa alkulukujen aiempaa tarkempaan ennustamiseen.

Alkuluvut ovat lukua 1 suurempia luonnollista lukuja, jotka ovat jaollisia vain yhdellä ja itsellään. Alkulukuja on äärettömästi, ja niistä ensimmäiset ovat 2, 3, 5, 7, 11, 13, 17, 19, 23 ja 29. Viime aikoihin asti on ajateltu, ettei alkuluvuilla ole mitään varsinaista järjestystä, vaan että niitä esiintyisi satunnaisesti.

Tutkijoiden uusi havainto on, että näennäisesti sattumanvaraisesti ilmaantuvat alkuluvut muodostavatkin pidemmissä lukujonoissa järjestelmällisen rakenteen.

Asiasta lisää Tekniikan Maailman uutissivuilta tai suoraan tutkimustiedotteesta.

Jutun kuva tutkimustiedotteesta.

Suurin tunnettu alkuluku kasvoi taas

Edellisen kerran uuden suuren alkuluvun löytymistä juhlittiin vuonna 2015. Se oli 2^74 207 281 - 1, jossa on numeroita 22 338 618. Nyt tämän hetken suurin tunnettu alkuluku on 2^77 232 917 – 1. Tämän uuden luvun löysi löysi yhdysvaltalainen Jonathan Pace, joka on metsästänyt alkulukuja yli 14 vuoden ajan. Hän on osana internetin kaikille avointa GIMPS (Great Internet Mersenne Prime Search) -matematiikkaprojektia, jonka päämääränä on etsiskellä uusia Mersennen alkulukuja. Pace lunasti löydöksestä itselleen 2 600 euron löytöpalkkion. Löytö tehtiin 26.12.2017. Asiasta uutisoi New Scientist. Asiasta kertoo myös Tekniikan Maailma

Tässä uudessa löydössä on numeroita 23 249 424 kappaletta. Jos se kirjoitettaisiin näkyviin kolme numeroa senttimetrille, luku olisi noin 77,5 km pitkä!

Suurin tunnettu alkuluku kasvoi taas

Edellisen kerran uutisoitiin uuden suuren alkuluvun löytymisestä helmikuussa 2013. Tässä linkki tuohon uutiseen. Tuolloin löytyi luku 2^57 885 161 - 1, jossa on 17 425 170 numeroa. Nyt alkulukuja etsivä, yksityisten ihmisten koneitä käyttävä verkosto GIMPS löysi 7. tammikuuta 2016 alkuluvun 2^74 207 281 - 1, jossa on numeroita 22 338 618 kappaletta, siis viisi miljoonaa numeroa enemmän kuin edellisessä tunnetussa suurimmassa alkuluvussa.

Tämä uusin luku käsin auki kirjoitettuna, 3 numeroa senttimetrille, olisi pituudeltaan runsaat 74 km pitkä. Hyvin pienellä kirjasimella painettuna se täyttää kolme vahvaa kirjaa, ks. linkki , tai vertailukohtana tarvittaisiin seitsemän raamatun kaikki kirjaimet, jotta saataisiin sama määrä merkkejä.

GIMPS-verkosto, joka käyttää siis yksityiseten koneiden laskentatehoa, pystyy suorittamaan 450 tuhatta miljardia laskutoimitusta sekunnissa. Ja toistaiseksi ei tunneta muuta keinoa luvun alkuluvuksi varmistamiseen kuin että kokeillaan jaollisuutta alkuluvuilla, jotka ovat korkeintaan tutkittavan luvun neliöjuuren suuruisia. Laskentatehoa siis tarvitaan.

Asiasta lisää seuraavista linkki2 ja linkki3

Kuva sivulta www.kirjavinkit.fi

Pii ja alkuluvut

Mitä tekemistä luvulla Pii ja alkuluvuilla on keskenään? Siitä asiaa seuraavassa linkissä

Taas uutta alkulukujen rintamalla

Huhtikuun 17. päivänänä 2013 hyvin arvostettu matemaattinen aikakauskirja Annals of Mathematics sai postia kutakuinkin tuntemattomalta Hampshiren yliopiston matemaatikolta Yitang Zhangilta. Kirjoittaja oli saavuttanut huiman tuloksen alkulukujen tutkimiksen maailmassa. Alkulukujen jakautuminen kokonailukujen joukossa on tällä hetkellä yksi aktiivisimmin tutkittavia matematiikan alueita. Usein Annalsin saamat kirjoitukset saavat odottaa kommentteja ja vastauksia pitkäänkin, vuosiakin, mutta nyt kesti vain kolme viikkoa kun Zhang sai jo innostuneen raportin paperistaan.

Zhang on tutkinut niinsanottuja alkulukukaksikoita. Alkulukukaksikoiksi tai -kaksosiksi sanotaan alkulukuja, jotka poikkeavat toisistaaan vain kakkosen verran. On helppoa osoittaa, että alkulukuja voi esiintyä lukujen 2 ja 3 jälkeen vai n kuudella jaollisten lukujen vieressä, esim. 5 ja 7, 11 ja 13, 17 ja 19. Kuitenkaan kaikki kuudella jaollisten vieressä olevat luvut eivät ole alkulukuja, esim. 23 ja (25) tai (119) ja (121). Näiden alkulukukaksikoiden esiintymistiheydestä on ollut toistaiseksi suurinpiirtein yhtävähän tietoa kuin yleensäkin alkulukujen jakaantumisesta. Nyt Zhang on pytynyt osoittamaan, että näiden alkulukukaksikoiden välimatka on korkeintaan 70 miljoonaa. Tulosta pidetään erittäin merkittävänä.

Enemmän asiasta sivulla http://www.wired.com/wiredscience/2013/05/twin-primes/
Kuvassa Yitang Zhang (Kuva: University of Hampshire)

Uusi suuri alkuluku löytyi

Alkulukujen rintamalla on ollut muutaman vuoden hiljaista. Edellinen löytö tehtiin syyskuussa 2008, jolloin löydettiin peräkkäin kaksi "isomusta".

Nyt suurimmaksi tunnetuksi alkuluvuksi nousi 48. ns. Mersennen luku 2^57 885 161 - 1. Tässä luvussa on 17 425 170 numeroa. Luvun suuruudesta saa jonkinlaisen käsityksen, jos ajattellee että kolme numeroa senttimetrille kirjoitettuna luvun pituus on yli 52 km! Luvun löysi University of Central Missourin Curtis Cooper käyttäen GIMPS verkostoa (Great Internet Mersenne Prime Search). Asiasta lisää seuraavassa.

Alkulukujen vuosi

Alkanut uusi vuotemmme 2011 on alkulukujen vuosi.Vuosiluku on itse alkuluku ja se voidaan esittää peräkkäisten alkulukujen summana, jopa kahdella tavalla:

2011 = 157 + 163 + 167 + 173 + 179 + 181 + 191 + 197 + 199 + 211

2011 = 661 + 673 + 677

Milloin tämä tapahtuu seuraavan kerran?

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

ja muutamat ensimmäiset ovat siis 1, 3, 7, 15, 31, 63, 127. Mersennen alkuluvut ovat Mersennen lukuja, jotka ovat myös alkulukuja. Esimerkiksi

on Mersennen alkuluku.

Nyt löytyneet uudet Mersennen alkuluvut ovat

ja


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/

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 ja , niin yleinen ratkaisu on


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

josta edelleen jakoyhtälöa ja sen antamaa jakojäännöstä käyttäen saadaan

ja näin hän lähettää meille salatun viestin z = 428.

D1. Viestin purkaminen tapahtuu kaavasta


Nyt siis jakoyhtälöitä, jakojäännöksiä ja kongruensseja käyttäen saadaan






ja niin lähettäjän lähettämä viesti 355 kulki välin niin salattuna, että se vieraisiin käsiin joutuessaankin pysyy salaisena.

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

- 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

käyttämällä henkilökohtaista purkuavaintasi t. Saat tulokseksi alkuperäisen sanoman s. Miksi? Siksi, että

ja Eulerin lauseen perusteella on
, joten


Seuraavalla kerralla vielä konkreettinen esimerkki yllä olevasta, tosin hyvin pienillä luvuilla, koska niilläkin siitä tulee käsin laskien aika työläs.

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.