Mersennova praštevila in Lucas-Lehmerjev algoritem

Mersennova praštevila in Lucas-Lehmerjev algoritem

Avtor: Urban Kržan

Učni cilji: Bralec se seznani, kako algoritem deluje

Uvod

Kaj je praštevilo?
S pojmom praštevila se dijaki srečajo že v prvem letniku srednje šole, ko obravnavajo deljivost naravnih števil. Naravna števila delimo glede na število njihovih deliteljev v tri skupine:

  1. V prvi skupini je število 1, ki ima natanko enega delitelja, to je samega sebe.
  2. V drugi skupini so praštevila, ki imajo natanko dva delitelja, to je število 1 in samega sebe.
  3. V tretji skupini so sestavljena števila, ki imajo več kot dva delitelja.

S praštevili so se ukvarjali že v antični Grčiji. Vedeli so, da je praštevil neskončno, kljub temu pa prav velikih praštevil niso poznali.
Definicija praštevila je razmeroma enostavna, zato je presenetljivo, da je še vedno veliko odprtih vprašanj, ki so povezana z njimi. Eno izmed takih vprašanj je, ali je izbrano število praštevilo. Težava je, če je izbrano število zelo veliko.
Danes si iskanja zelo velikih praštevil ne moremo zamisliti brez pomoči računalnika, uporabljamo pa jih predvsem v kriptografiji.

V srednji šoli dijaki spoznajo, da je praštevil neskončno. Dokaz si lahko ogledate tukaj.
Odgovor

Zakaj potrebujemo velika praštevila?
Odgovor

Dokaz

Trditev bomo dokazali s protislovjem. Denimo, da je praštevil končno, recimo : . Oglejmo si število . Glede na našo predpostavko mora biti število sestavljeno. To pomeni, da je deljivo z nekim praštevilom od do . To pomeni, da bi to praštevilo delilo tudi število 1, kar pa je protislovje.

Uporaba praštevil

Danes uporabljamo praštevila predvsem v kriptografiji, za varno prenašanje podatkov v omrežju. Z večjimi praštevili lahko zagotovimo tudi večjo varnost. Algoritmi za kodiranje podatkov temeljijo namreč na predpostavki, da je iz zmnožka dveh velikih praštevil težko ugotoviti, kateri praštevili ga sestavljata.

Eratostenovo rešeto

Eratostenovo rešeto je preprost postopek za iskanje praštevil, manjših od izbranega števila . Postopek je sledeč:

  1. Zapišemo vsa števila od 2 do .
  2. Naj bo najmanjše število, ki ni prečrtano. Prečrtamo vse večkratnike števila .
  3. Če je , se vrnemo na drugi korak, sicer postopek končamo. Števila, ki ostanejo neprečrtana, so vsa praštevila med 2 in .

Eratostenovo rešeto - animacija

Primer algoritma v pythonu: def eratosten(n): #funkcija vrne seznam praštevil med 2 in n
    precrtano = [False] * (n + 1) #na začetku so vsa števila neprečrtana
    prastevila = []
    for i in range(2, n+1):
        if not precrtano[i]:
            prastevila.append(i)
            for j in range(i, n+1, i): #prečrtamo vse večkratnike
                precrtano[j] = True
    return prastevila

eratosten.py

Kdo je bil Eratosten? Odgovor

Eratosten(276 - 194 pr. n. št.)

Rojen je bil v današnji Libiji, nekaj časa je deloval v Atenah, kasneje pa se je preselil v Aleksandrijo v Egiptu, kjer je bil imenovan za vodjo znamenite Aleksandrijske knjižnice. Tam je tudi umrl.

Mersennova števila

Mersennova števila so oblike . Če je število praštevilo, ga imenujemo Mersennovo praštevilo.
Velja trditev:
Če je število praštevilo, potem je tudi število praštevilo.
Na tem mestu je potrebno opozoriti, da trditev obratno ne drži. Če je število praštevilo, ne pomeni, da je tudi število praštevilo.
Primer: Število 11 je praštevilo, pa je sestavljeno število, saj je

Malo zgodovinskega ozadja o Marin Mersennu Marin Mersenne

Marin Mersenne(1588 - 1648)

Bil je francoski mislec, filozof, fizik in matematik. Izobraževal se je na jezuitskem kolegiju v La Flecheju, kjer je bil Descartesov sošolec in prijatelj.

(mersenne.jpg)

Najbolj znan je po Mersennovih številih. V predgovoru svoje knjige Cogita physico - mathematica je zapisal, da je praštevilo za in sestavljeno število za vse druge manjše od 257. Kako je prišel do tega, danes ne ve nihče, zanimivo pa je, da je bil blizu resnici.

Lucas-Lehmerjev algoritem

Lucas-Lehmerjev algoritem deluje le za Mersennova števila, je pa razmeroma učinkovit, če upoštevamo, da so največja znana praštevila Mersennova praštevila. Tako je bilo 25. januarja 2013 odkrito novo največje praštevilo , ki ima, če ga zapišemo v desetiškem sestavu, 17425170 mest.

Z Lucas-Lehmerjevim algoritmom preverimo, ali je število oblike praštevilo. Če je, nam algoritem vrne "True", sicer nam vrne "False". Zakaj je algoritem tako učinkovit, si bomo ogledali v nadaljevanju.

Preden si bomo ogledali, kako algoritem deluje, definirajmo zaporedje: in . Prvih nekaj členov zaporedja je . Zaporedje je podano rekurzivno, imenujemo pa ga Lucas-Lehmerjevo zaporedje.

Algoritem temelji na naslednjem izreku:
Naj bo praštevilo večje od 2. Če je , potem je število praštevilo.

Opomba

Da bomo lažje razumeli kako algoritem deluje, si bomo v nadaljevanju pogledali nekaj primerov.

Kongruenca

Zapis preberemo takole: Števili in sta kongruentni po modulu .
Števili in sta kongruentni natanko takrat, ko deli razliko .
Na primer: .

Lucas-Lehmerjev algoritem

Prvi primer: Z Lucas-Lehmerjevim algoritmom preveri, ali je število praštevilo.

. Izračunamo Lucas-Lehmerjevo zaporedje do po modulu .

kako računamo člene zaporedja


Iz tabele vidimo, da je , kar pomeni, da je število res praštevilo.

Lucas-Lehmerjev algoritem

Drugi primer: Z Lucas-Lehmerjevim algoritmom pokaži, da je število sestavljeno število.

. Najprej izračunamo Lucas-Lehmerjevo zaporedje do po modulu .

kako računamo člene zaporedja


Ker je , pomeni, da je število sestavljeno število, kar je res, saj lahko število zapišemo kot produkt dveh faktorjev: .

Lucas-Lehmerjev algoritem

Tretji primer: Z Lucas-Lehmerjevim algoritmom preveri, ali je število praštevilo.

. Izračunamo Lucas-Lehmerjevo zaporedje do po modulu .

kako računamo člene zaporedja


Vidimo, da je . S tem smo pokazali, da je število praštevilo.

Lucas-Lehmerjev algoritem

Čas je, da sestavimo algoritem. Vhodni podatek je poljubno praštevilo večje od 2. Če je število praštevilo, nam algoritem vrne vrednost "True", sicer pa nam vrne vrednost "False".

  1. Prvi člen zaporedja je .
  3. Računamo člene zaporedja :
    Vrednost delimo z vrednostjo . Pri deljenju dobimo nek ostanek, ki ga bomo označili z . Številu priredimo novo vrednost, to je .
    Postopek ponavljamo, dokler je .
  4. Na koncu pogledamo vrednost člena . Če je vrednost enaka 0, pomeni, da je število praštevilo. V tem primeru nam algoritem vrne vrednost "True".
    Če vrednost člena ni enaka 0, pomeni, da število ni praštevilo, algoritem pa nam v tem primeru vrne vrednost "False".

Algoritem bi v pythonu zgledal takole:
def LucasLehmer(p):
    if p == 2: #Lucas-Lehmerjev test deluje samo za praštevila večja od 2
        return True
    else:
        s = 4 #prvi člen Lucas-Lehmerjevega zaporedja
        m = 2**p - 1 #število m je Mersennovo število
        i = 0
        while i <= p - 2: #v zanki računamo člene Lucas-Lehmerjevega zaporedja
            o = s % m
            s = o**2 - 2
            i = i + 1
        if o == 0: #če je na koncu vrednost enaka 0, je število m praštevilo
            return True
        return False 

LucasLehmer_algoritem.py

Lucas-Lehmerjev algoritem

Zakaj je Lucas-Lehmerjev algoritem tako učinkovit?

Vzemimo število . Poglejmo si, koliko časa bi potrebovali, če bi hoteli preveriti, ali je število praštevilo, s sledečim algoritmom:
Število po vrsti delimo z vsemi praštevili od do . Če se deljenje nikoli ne izide, je praštevilo.

Predpostavimo, da imamo računalnik, ki lahko v eni sekundi opravi deljenj. Po Gaussovem izreku je vseh praštevil do približno . To pomeni, da bi s tem algoritmom potrebovali približno deljenj, kar znaša deljenj. Za tolikšno število deljenj bi po naši predpostavki potrebovali sekund, kar je okoli ur, kar je nekaj manj kot dni.

Z Lucas-Lehmerjevim algoritmom število operacij bistveno zmanjšamo. V našem primeru bi morali opraviti deljenj po modulu in kvadriranj, ker v vsakem koraku računamo še člene zaporedja. Skupaj je to operacij, kar je bistveno manj, kot v prejšnjem primeru.

Časovna analiza algoritma

  • Velikost problema:

    • velikost števila .

  • V zanki imamo dve tipični operaciji:

    • računanje ostanka
    • kvadriranje

  • Število primerjanj:

    • .


Če število podvajamo, vidimo, da raste čas kot , okvirno . Torej je Lucas-Lehmerjev algoritem polinomske časovne zahtevnosti. Podrobnejšo in bolj matematično časovno analizo lahko najdete na spletnem naslovu:

http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Time_complexity

Kviz: Kaj je praštevilo?

Preveri

Pravilno!

Naprej

Narobe!

Ponovno

Kviz: Izberi pravilne trditve:

Preveri

Pravilno!

Naprej

To pa ne bo držalo! Poskusi znova.

Ponovno

Kviz: Katero zaporedje predstavlja Lucas-Lehmerjevo zaporedje?

in
in
in
in

Pravilno!

Naprej

To pa ne bo držalo! Poskusi znova.

Ponovno

Kviz: Ali so spodnje trditve pravilne ali nepravilne? Pravilno poveži.

Pravilno.
Napačno.

Preveri

Odlično, rešitev je pravilna!

To pa ne bo držalo! Rešitev je:

Pravilno.
Pravilno.
Napačno.
Napačno.

Kviz: Ali je število praštevilo?

Z Lucas-Lehmerjevim algoritmom preveri, ali je število praštevilo. Zaporedne člene vpisuj v prazne okvirčke:

Dopolni: Ker je = , je po Lucas-Lehmerjevem izreku število .

Preveri

Rešitev je pravilna!

To pa ne bo držalo!
Zaporedni členi so: , , , , in . Ker je , je po Lucas-Lehmerjevem izreku število praštevilo.

Zaključek

Algoritem Agrawal-Kayal-Saxsena (Algoritem AKS)

Za zaključek omenimo še algoritem, ki so ga odkrili trije Indijci: Agrawal, Kayal in Saxsena. Algoritem je bil prvič objavljen leta 2002, gre pa za prvi pravi polinomski deterministični algoritem.

Osnovna ideja

Naj bo , , , kjer sta si števili in tuji.
Število je praštevilo natanko takrat, ko velja:


Ker je preverjanje te enakosti zahtevno, se omejimo na približek

za nek primerno majhen . Algoritem AKS preverja to enakost za majhno množico -jev.

Komentar

Več o tem algoritmu lahko najdete na povezavi Algoritem AKS

komentar

Kaj pomeni zapis ?
Primer: in , kar lahko na kratko pišemo .

Viri in literatura

  1. http://eprints.fri.uni-lj.si/2208/1/Slosu_A-1.pdf
  2. http://rosettacode.org/wiki/Lucas-Lehmer_test
  3. https://dk.um.si/Dokument.php?id=49827
  4. http://www.famnit.upr.si/files/zakljucna_dela_repo/239
  5. http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
  6. http://sl.wikipedia.org/wiki/Mersennovo_%C5%A1tevilo
  7. http://www.presek.si/31/1575-Petr.pdf
  8. http://www.presek.si/28/1458-Potocnik.pdf
  9. http://videolectures.net/solomon_vuk_patp/
  10. http://www2.nauk.si/materials/382/out/#state=1
  11. https://slo-tech.com/novice/t555397
0%
0%