Rabin-Millerjev test praštevilskosti

Iz MaFiRaWiki

Rabin-Millerjev verjetnostni algoritem za preverjanje praštevilskosti

Iskanje praštevil je zelo zapleten postopek. Še do nedavnega ni obstajal algoritem s polinomsko časovno odvisnostjo za preverjanje, ali je število praštevilo ali ne. Zato so se velikokrat uporabljali t.i. verjetnostni algoritmi, ki so z veliko verjetnostjo zelo hitro povedali, ali je število praštevilo ali ne. Včasih pa se zmotijo in sestavljeno število označijo za praštevilo. Taka števila imenujemo dobri lažnivci. Rabin-Millerjev algoritem je eden izmed teh algoritmov.


Praštevila so naravna števila, ki so deljiva s številom 1 in s samim sabo. Naravna števila, ki imajo več kot dva delitelja, imenujemo sestavljena števila. Hitro vidimo, da je edino sodo praštevilo, število 2. Zatorej vzemimo poljubno liho število n, za katerega želimo ugotoviti ali je praštevilo.

Liho število n zapišimo kot n=2r⋅s+1, kjer je s liho število. Izberimo poljubno naravno število a, za katerega velja 1≤a≤n-1. Če je as≡1(mod n) ali a2j⋅s≡-1 (mod n) za nek j, 0≤j≤r-1, potem je n po Rabin-Millerjevem testu z veliko verjetnostjo praštevilo. Vsa praštevila ustrezajo Rabin-Millerjevem testu.

Algoritem

En izmed možnih načinov algorita za določanje praštevilskosti po Rabin Millerju bi bil:
Vhodni podatki:

  • n>1; naravno število, za katerega ugotavljamo ali je praštevilo;
  • k; parameter, ki določa natančnost testa;
Izhodni podatki:
  • sestavljeno število v primeru, da je n sestavljeno število;
  • verjetno praštevilo, v primeru, da n uspešno prestane Rabin-Millerjev test;
       Zapiši n-1 kot 2s⋅d s faktorizacijo števila n-1 s potencami števila 2. 
Ponovi k-krat:
  izberi poljuben a z intervala [1,n-1]
  x0←ad mod n
  for r=1...s
    xr←xr-12 mod n
    if xr in xr-1≠1 in xr-1≠n-1 potem
    return sestavljeno;
  if xr≠1 potem
  return sestavljeno;
return verjetno praštevilo;

Časovna odvisnost algoritma je O(k×log3n), kjer je k število različnih vrednosti števila a, ki ga preverjamo.


Primera

Najprej poglejmo delovanje algoritma na številu, za katerega vemo, da je praštevilo. Izberimo n=29. Vemo, da lahko zapišemo:
n-1=28=22⋅7
Zato je s=2 in d=7.
Sedaj moramo vzeti poljubno število z intervala [1, 28]
107≡17 (mod 29) ≠ 1 ali -1
Poskusimo še:
(107)2≡1 (mod 29); rezulatat nam pove, da je 29 verjetno praštevilo. Ker smo poskusili samo z enim številom z intervala [1, 28], je verjetnost, da je odgovor pravilen 3/4. Zato poskusimo še z drugim nakjlučnim številom npr. a=19.
197≡12 (mod 29) ≠ 1 ali -1
(197)2≡1 (mod 29);
Podobne odgovore bi dobili za vsa števila z intervala [1, 28], zatorej lahko z gotovostjo trdimo, da je 29 praštevilo.

Oglejmo si sedaj primer malo večjega sestavljenega števila:

Želimo preveriti, ali je število 221 praštevilo. Zapišimo n-1=220 kot 22⋅55. Torej je s=2 in d=55. Poljubno izberemo število 174, saj moramo izbrati poljuben a<n. Računamo:
ad (mod n) = 17455 (mod 221) = 47 ≠ 1
Nadaljujemo s postopkom:
a20⋅d (mod n) = 17455 (mod 221) = 47 ≠ n-1
Tudi na podlagi tega ne moremo sklepati še ničesar, zato nadaljujemo:
a21⋅d (mod n) = 174110 (mod 221) = 220 = n-1
Ker je 220 ≡ -1 (mod n), je 221 praštevilo ali pa je 174 dober lažnivec za 221. Zato ponovimo poskus za nakjučen a<n (npr. 137):
ad (mod n) = 13755 (mod 221) = 188 ≠ 1
a20⋅d (mod n) = 13755 (mod 221) = 188 ≠ n-1
a21⋅d (mod n) = 137110 (mod 221) = 205 ≠ n-1
V drugem koraku smo videli, da število 221 ne izpolni pogojev Rabin-Millerjevega testa in je zato sestavljeno število. Kljub temu, da nam algoritem potrdi, da je število 221 sestavljeno, nikjer v postopku ni omenjene faktorizacije števila 221 = 13 ⋅ 17.

Osebna orodja