Verjetnostni algoritmi za preverjanje praštevilskosti

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Verjetnostni algoritmi za preverjanje praštevilskosti

Avtor: Vera Kabanova

Praštevila

Definicija:
Praštevilo je naravno število, ki ima natanko dva pozitivna delitelja: število 1 in samega sebe.

Število praštevil:
Obstaja neskončno mnogo praštevil.

Predpostvimo, da je praštevil končno mnogo. Če jih zmnožimo med sabo pa dobljenemu številu preštejemo 1, dobimo število, ki pri deljenju s katerim-koli praštevilom da ostanek 1. Torej tako dobljeno število ni deljivo z nobenim praštevilom obenem pa ni praštevilo. Pridemo do protislovja.

Primeri praštevil:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53...
393050634124102232869567034555427371542904833
največje znano praštevilo: 2^43112609 − 1
ima 12978189 števk

Uporaba:
Velika praštevila se uporabljajo v moderni kriptografiji. Kriptografija je veda, ki se ukvarja z kodiranjem in zaščito podatkov oz. informacije. Praštevila se uporabljajo za generiranje gesel in ključev.

Testi praštevilskosti - deterministične metode

To so metode, ki zagotovo določijo, če je neko število praštevilo ali sestavljeno.

pregled potencialnih deliteljev
Naj bo število, ki ga testiramo na praštevilskost. Preverimo, če je deljivo z celimi števili med 2 in . Če je deljivo z vsaj enim od teh števil, potem je sestavljeno, sicer je praštevilo. Gre za precej neefektivno metodo, saj za preverjanje praštevilskosti zelo velikih števil vzame zelo veliko časa.

Program v Pythonu
Izrek Wilsona
Število je praštevilo natanko tedaj, ko je deljivo z . V praksi je tudi ta metoda zelo neefektivna, saj izračun fakultete je precej zahteven.

Program v Pythonu

koda

def pregledDeljiteljev(število):
    if število < 2:
        return False
    i=2
    while i**2<=število:
        if število%i==0: #takoj ko naletimo na deljitelj
            return False #vrnemo false
        i+=1
    return True #če v zanki ne naletimo na nobenega deljitelja

Zapri

koda

def izrekWilsona(število):
return (math.factorial(število-1)+1)%število==0

Zapri

Testi praštevilskosti - verjetnostne metode

To so metode, ki določijo, če je neko število sestavljeno ali verjetno praštevilo. Pri teh testih razen testiranega števila uporabimo še naključno zgenerirano število . Nato preverimo, če velja neka enakost(značilna za posamezen test), ki vključuje in . Če ta enakost ne velja, je število sestavljeno, število pa priča sestavljenosti števila . Če enakost velja, pa ni še nujno, da je praštevilo. Verjetnost napake lahko zmanjšamo s tem, da testiramo z več različnimi naključnimi števili .

Obravnavali bomo :

Fetmatov test
Miller-Rabinov test
Solovay–Strassenov test

Fermatov test

Ta test temelji na Fermatovem malem izreku:
Za vsako praštevilo in velja, da je deljivo z oz. pri deljenju z da ostanek .
V testu generiramo naključna števila . Brž ko za katero izmed njih ne velja enakost , vemo, da je sestavljeno število in je priča njegove sestavljenosti.
Od tega na koliko različnih testiramo veljavnost enakosti je odvisna natančnost odgovora. Kot vhodni podatek algoritmu poleg testiranega števila podamo še število korakov, ki jih naj izvede.
Algoritem v pythonu:

Časovna zahtevnost:

Slabost: Fermatova psevdopraštevila - sestavljena števila, za katera velja enakost , za nekatera števila . Najbolj problematična med temi psevdopraštevili so Carmichaelova števila - za njih velja enakost za vsa števila , ki so tuja številu .

Fermatov test - primeri

Ali je število 341 praštevilo?
- izberemo naključni
- izračunamo
- nismo dobili 1, torej 341 je sestavljeno število in 11 je njegova priča sestavljenosti
Ali je število 87 praštevilo?
- izberemo naključni
- izračunamo
- dobimo 1 - ali imamo res praštevilo?
- izberemo še en naključni
- izračunamo
- nismo dobili 1, torej 87 je sestavljeno število in 23 je njegova priča sestavljenosti
- število 87 je psevdopraštevilo za osnovo 59
Ali je 223 praštevilo?
- izberemo pet naključnih -> 5,40,134,204,198
- po petih poskusih nismo našli priče sestavljenosti števila 223 - število je verjetno praštevilo

Fermatov test - primeri(2)

Za posamezno Carmichaelovo število ne poznamo verjetnosti, da nam algoritem vrne napačen odgovor, saj ima vsako Carmichaelovo število lastno porazdelitev njim tujih števil. V tem primeru delamo teste na številih 1729 in 321197185 pri različnih številih iteracij testa Fermata. Za vsako število, pri posameznem številu korakov izvedemo 100000 testov in štejemo kolikokrat se je algoritem zmotil.

Miller-Rabinov test

Vsako liho število n se da zapisati kot .
Naključno število je priča sestavljenosti, če ne veljata obe naslednji enakosti:
- za
Algoritem za prepoznavanje priče sestavljenosti:
1. n zapišemo kot
2. izračunamo
3. za i od 1 do s ponavljamo:
  2. če in in , potem vrni TRUE
4. če , potem vrni TRUE
5. vrni FALSE
Z zanko (3) pregledamo vse potencialne . in preverimo veljavnost zgoraj napisanih enakosti.
V vrstici (4) preverimo še veljavnost pogoja Fermata.
V algoritmu Millerja-Rabina večkrat ponovimo test za prepoznavo prič in na podlagi rezultatov teh testov podamo odgovor.

Miller-Rabinov test - algoritem v pythonu

Miller-Rabinov test - natančnost in časovna zahtevnost

Dokazano je, da so za vsako liho sestavljeno število vsaj 3/4 potencialnih priče njegove sestavljenosti. Torej ta algoritem razglasi sestavljeno število za praštevilo z največ verjetnostjo , kjer je k število korakov algoritma.
Opazimo, da natančnost ni odvisna od velikosti števila, kar pomeni da je dovolj testirati velika števila tolikokrat, koliko testiramo manjša števila. Če test izvedemo 20-krat, je verjetnost napake največ .
Časovna zahtevnost:

Primer uporabe

Ali je 1363005552434666078217421284621279933627102780881053358473 praštevilo?

Ali je 1363005552434666078217421284621279933627102780881053358477 praštevilo?

Solovay–Strassenov test

Solovay–Strassenov test temelji na malem izreku Fermata in na lastnostih Jacobijevega simbola.
Jacobijev simbol
Dokazano je, da za vsako praštevilo in vela enakost: .
V Solovay–Strassenovem testu preverjamo veljavnost te enakosti za naključno zgenerirane vrednosti . Takoj ko naletimo na tak , pri katerem enakost ne velja, vemo, da je testirano število sestavljeno in je priča njegove sestavljenosti.
Za pisanje algoritma, rabimo npisati funkcijo za iskanje Jakobijevega simbola. Pri tem si pomagamo z lastnostmi Jacobijevega simbola: Lastnosti Jacobijevega simbola

Natančnost: dokazano je, da je za vsako liho sestavljeno število vsaj polovica potencialnih priče njegove sestavljenosti. Verjetnost napake na vsakem koraku algoritma je tako 1/2. Torej ta algoritem razglasi sestavljeno število za praštevilo z največ verjetnostjo , kjer je k število korakov algoritma.
Časovna zahtevnost: