V teoriji računske zahtevnosti algoritmov se problemi uvrščajo v različne težavnostne razrede glede na to, koliko resursov je potrebnih za rešitev (n.pr. časa reševanja, korakov v algoritmu, velikosti spomina računalnika itd.). Najlažji problemi so tisti, za katere obstaja algoritem, s katerim pridemo do rešitve v času, ki je omejen z neko fiksno potenco dolžine vhoda (s polinomom) - ti spadajo v razred P (polynomial time class).

Naslednji razred je NP (nondeterministic polynomial time class). Za te probleme se da v času, omejenem s polinomom, preveriti, ali je neka rešitev pravilna, medtem ko se časa, potrebnega za rešitev, ne da omejiti s polinomom.
Primer problema iz razreda NP: Hitro lahko preverimo, ali je sestavljanka (jigsaw puzzle) pravilno sestavljena - za vsak košček pogledamo sosednje, za kar potrebujemo približno (število sosednjih koščkov) x (število koščkov sestavljanke) enot časa. Pri reševanju pa imamo toliko kombinacij, da ni mogoče najti algoritma, ki bi imel število korakov omejeno z neko fiksno potenco števila koščkov.

Verjamemo, da sta razreda P in NP različna, ni pa dokazano. Pravzaprav je za dokaz tega razpisana nagrada v višini milijon dolarjev.

Predpostavki pri RSA sta, da spada razstavljanje velikega števila v razred NP, iskanje velikega praštevila pa v razred P.

Prva predpostavka še ni dokazana. Če število n delimo po vrsti z vsemi števili, ki so manjša od njegovega kvadratnega korena, vidimo, da je število potrebnih korakov eksponentno odvisno od dolžine števila: Označimo n = 10^N (N pomeni število cifer števila n), potrebujemo torej (10^N)^1/2 korakov.
Problem bi uvrstili v razred NP, če bi imeli dokaz za to, da ne obstaja algoritem z manj koraki.

Drugo predpostavko so avgusta letos (2002) dokazali trije indijski znanstveniki M. Agrawal, N. Kayal, and N. Saxena v članku PRIMES is in P. Iz "malega Fermat-ovega izreka" so izpeljali algoritem, s katerim ugotovimo, ali je število n praštevilo v času, ki je omejen s polinomsko funkcijo dolžine števila n: O(N)¹²f(log N).
To je velik teoretičen dosežek, ali pa bo tudi praktično uporaben, je zaenkrat težko reči.

V praksi bomo še naprej uporabljali sedaj uveljavljene postopke:

V zadnjih 30 letih so predstavili več postopkov, ki temeljijo na "malem Fermat-ovem izreku":

Če je p praštevilo, potem za vsako število a, ki ni deljivo s številom p, velja:
a^p-1 - 1 0 (mod p)

Če enačba velja za vsa števila a (a < p), je izpolnjen potreben pogoj za to, da je število p praštevilo, žal pa ni zadosten. Obstajajo namreč števila, ki pogoj izpolnjujejo, pa niso praštevila (Carmichaelova števila, n.pr. 561).

Število, ki naj bi bilo praštevilo, mora biti liho, in ga lahko zapišemo v obliki

Iz tega se da izpeljati sklep, da je p praštevilo z veliko verjetnostjo glede na osnovo a, če velja

a^d 1 (mod p)   ali   a^d.2r -1 (mod p), kjer je r večji ali enak 0 in manjši od s (test Rabin - Miller).

Če število ne ustreza testu, je gotovo sestavljeno, v nasprotnem primeru pa je verjetnost napake 1/4^t, kjer t pomeni število ponovitev testa za različne osnove. Število, ki ustreza testu za 6 osnov, bi torej z verjetnostjo 1/4⁶ = 0,00024 bilo sestavljeno število. Napaka se manjša z večanjem števila p. Pri 256-bitnem številu p ocenjujejo verjetnost napake na 1/2⁵¹ pri 6 testih. Za običajno uporabo je taka možnost napake sprejemljiva.

V praksi je postopek takle:

• naključno izberemo N-bitno liho število n;
• preverimo, da ni deljivo z najmanjšimi praštevili - vsaj do 256;
  (ocenjujejo, da tako izločimo 80% sestavljenih števil)
• izvedemo Rabin-Millerjev test za vsaj pet naključno izbranih osnov a, manjših od n:

  Izračunamo m a^d (mod n)
  Če je 1, sledi, da je n praštevilo in test je končan.
  (z) Sicer pa nadaljujemo: m -> m² (mod n)
  Če je m -1 (mod n), sledi, da je n praštevilo in konec testa, sicer pa se vrnemo v zanko (z).
  Postopek končamo, ko pridemo do m^s.

Več o iskanju praštevil: Distinguishing prime numbers from composite numbers

Oktober 2002