Prosojnice si lahko ogledate ali pa jih izpišete (po 8 na eno stran).
S praštevili, ki so "osnovni gradniki" matematike, so se ukvarjali učenjaki vse od antičnih časov dalje. Leta 240 pr. n. št. se je grški matematik in filozof Eratostenes, bibliotekar aleksandrijske knjižnice, domislil prve neoporečne metode, s katero je mogoče ugotoviti, ali je neko število praštevilo. Vendar čas, ki ga ta metoda zahteva, narašča eksponentno z velikostjo števila, tako da bi v primeru zelo dolgih števil potrebovali več časa kot je staro vesolje za rešitev tega problema. Od tedaj so matematiki poskušali najti algoritem, ki bi dal odgovor v smiselnem času.
Raziskave so postale še posebej intenzivne v zadnjih desetletjih, saj so praštevila ključnega pomena v kriptografiji. Šifrirni sistem, ki se uporablja za zavarovanje internetnih transakcij, temelji na dejstvu, da je izjemno težko določiti prafaktorje nekega velikega števila. Algoritmi, ki jih računalničarji trenutno uporabljajo za iskanje teh prafaktorjev, so sicer hitri, vendar izračunajo samo kolikšna je verjetnost, da je neko število praštevilo. Čeprav je verjetnost lahko zelo velika, ti algoritmi ne tvorijo dokaza.
Sedaj pa so Manindra Agarwal in njegova sodelavca uspeli rešiti problem, ki ga tudi najboljši duhovi matematike niso uspeli rešiti. Odkrili so algoritem, ki daje odgovor v smiselnem času. Njihov uspeh temelji na novem pristopu k reševanju tega problema. Namesto, da bi zastavili eno samo veliko vprašanje, ali je to število praštevilo, so postavili celo zaporedje manjših vprašanj oziroma "enačb" glede števila, ki so ga želeli preveriti. "Če enačbe veljajo, potem je število praštevilo, če pa katerakoli od teh enačb ne velja, potem število ni praštevilo," pravi Agarwal.
Dokaz, ki so ga indijski znanstveniki objavili na spletnih straneh svojega inštituta (www.cse.iitk.ac.in), so preverili že številni matematiki. Vsi, ki so Agarwalu poslali povratno informacijo, so algoritem ocenili kot pravilen. Strokovnjaki so domnevali, da je algoritem s polinomskim časom sicer mogoč, vendar niso predvidevali izjemne preprostosti trinajstvrstične rešitve, ki so jo predstavili Agarwal, Kayal in Saxena.
"To je bil eden od velikih nerešenih problemov v teoretski računalniški znanosti in računalniški teoriji števil," je o odkritju dejal Shafi Goldwasser, profesor računalništva na Massachusetts Institute of Technology v ZDA in na Weizmannovem inštitutu znanosti v Izraelu. "To je najboljši rezultat v zadnjih desetih letih," pravi Goldwasser.
"Teoretski napredek je pomemben že sam zase, vendar bo ta metoda pomagala matematikom rešiti tudi nekatere probleme, kjer so zaradi uporabe drugih tehnik zašli v slepo ulico," meni o rešitvi treh indijskih znanstvenikov matematik Ian Stewart z Univerze v Warwicku v Veliki Britaniji. Ekspert za praštevila Carl Pomerance, matematik v Bellovih laboratorijih v New Jerseyu, ZDA, pa pravi, da nas ta preprosta in elegantna rešitev znova opozarja, kako lahko je spregledati preproste stvari.