Raskt BEVIS for at monstertallet er et primtall

Indiske forskere har laget en algoritme som raskt kan bevise hvorvidt et gitt enormt tall er primtall eller ikke.

Krypteringsalgoritmer krever tilgang til stadig større primtall. Algoritmer som kan fastslå med hundre prosent sikkerhet hvorvidt et monstruøst stort heltall er primtall eller ikke, krever for mange beregninger, og går for sakte, til å kunne brukes i praksis. Følgelig tyr man til raskere algoritmer som bare kan slå fast at det er stor sannsynlighet for at et gitt tall er et primtall.

Etter hvert som elektroniske nettverk skal håndtere en stadig økende flom av mer og mer følsomme tjenester, blir det mindre akseptabelt å ty til krypteringsnøkler som man ikke med sikkerhet vet bygger på ekte primtall. Følgelig jaktes det på en algoritme som kjapt og greitt slår fast med hundre prosent sikkerhet at et tall er et primtall.

En gruppe indiske forskere fra Computer Science Department ved Indian Institute of Technology, under ledelse av professor i kryptografi Manindra Agrawal har offentliggjort artikkelen PRIMES is in P.

Artikkelen presenterer en algoritme som langt kjappere enn tidligere kjente algoritmer kan bevise hvorvidt et monstruøst stort heltall er primtall eller ikke. Tallet på påkrevde beregninger er proporsjonalt med tolvte potensen til tallets logaritme. Under forutsetning av en hittil betrodd men ennå ikke-bevist forutsetning om fordelingen av primtall av typen "Sophie Germain", blir tallet på beregninger proporsjonalt med sjette potensen til tallets logaritme. Ikke begge tilfeller dreier det seg om enkle, algebraiske operasoner.

Likevel er ikke algoritmen i sin nåværende form rask nok til de praktiske kravene krypteringsalgoritmene setter. Agrawal innrømmer i et intervju med ZDNet at det ennå synes langt fram til en praktisk anvendelse av den nye algoritmen. Han mener framtidige forbedringer og et skjerpet krav til at man må være absolutt sikker på å bruke primtall som basis for krypteringsalgoritmer, vil bringe fram praktiske løsninger.

PRIMES is in P kan lastes ned i PS-format fra Agrawals nettsted (se lenken ovenfor). Dette formatet - ren Postscript - kan leses gjennom Acrobat Distiller, eller gjennom gratisprogrammet GhostScript (søk på Google gir flere kilder).

Til toppen