Praštevila:
Praštevilo je naravno število, ki ima natanko dva pozitivna delitelja: število 1 in samega sebe. Obstaja neskončno mnogo praštevil.
Testi praštevilskosti:
Testi praštevilskosti so testi, ki za neko naravno število določijo, če je praštevilo ali sestavljeno število.

• Deterministične metode
  Te metode zagotovo določijo, če je testirano število praštevilo ali sestavljeno število.
  Najbolj znana je naivna metoda pregled potencialnih deliteljev. Pri tej metodi 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
  

• Verjetnostne metode
  To so metode, ki določijo, če je testirano š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. Obstajajo psevdopraštevila - to so sestavljena števila, ki imajo določene lastnosti vezane na praštevila. Verjetnost napake lahko zmanjšamo s tem, da testiramo z več različnimi naključnimi števili .

• 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 .

• Ali je število 341 praštevilo?
  
  Rešitev
  
  

• Ali je število 87 praštevilo?
  
  Rešitev
  
  

• Ali je število 223 praštevilo?
  
  Rešitev
  
  

Za posamezno Carmichaelovo število ne poznamo verjetnosti, da nam algoritem vrne napačen odgovor, saj ima vsako Carmichaelovo število lastno porazdelitev njemu 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

• Natančnost: 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.
• Časovna zahtevnost:
  

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 velja 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.
• 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:

Za 5 praštevil v naraščujočem vrstnem redu izmerimo trajanje izvajanja posameznega algoritma.

• Za testiranje manjših števil se najbolj splača uporabljati deterministične metode, saj so natančne in za majhna števila dovolj hitre.

• Za testiranje večjih (več kot petmestnih) števil se splača uporabljati verjetnostne metode. Najhitrejša metoda je Fermatova, ampak ni najbolj natančna. Najpogosteje se v kriptografiji uporablja Miller-Rabinov test, ker je od verjetnostnih testov najbolj natančen in dokaj hiter.
  
  
  

  Vprašanja?