i i “1519-Petkovsek-0” — 2010/8/25 — 10:34 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 30 (2002/2003) Številka 3 Strani 155, X Marko Petkovšek: REŠITEV PROBLEMA PRAŠTEVIL Ključne besede: teorija števil, računalništvo, praštevila. Elektronska verzija: http://www.presek.si/30/1519-Petkovsek.pdf c© 2002 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno. I Računalništvo Nadaljevanje s str. 155 . Profesor Manindra Agraval (skrajno desno) in njegova podiplomska študenta Nitin Saksena in Niradž Kaja!. Računski postopek treh indijskih znanstvenikov bomo morda opisali kdaj drugič. Za zdaj povejmo le, da čas, ki ga novi postopek v najslabšem primeru potrebuje za preskus praštevilskosti števila n, zanesljivo ni večji od CIn12 n , kjer je C neka konstanta. Avtorji domnevajo, da potrebni čas v resnici ni večji od C In6 n. Za ilustracijo vzemimo, da njihova domneva drži in da je vrednost kon- stante C enaka času, ki ga naš računalnik potrebuje za eno deljenje. Potem bo za preskus praštevilskosti števila n = 10100 + 267 porabil približno 149 sekund oziroma dve minuti in pol. No , toliko bomo pa že počakali! . Novi postopek ima velik teoretičen pomen. V praksi pa se bodo za reševanje problema praštevil še vedno uporabljali verjetnostni algoritmi, ki so neprimerno hitrejši, kar dosežejo z žrtvovanjem absolutne pravilnosti odgovora. Verjetnostni algoritmi se namreč lahko včasih zmotijo in kakšno število razglasijo za praštevilo, čeprav je v resnici sestavljeno. Ker pa je verjetnost napake izredno majhna (veliko manjša od verjetnosti glavnega dobitka na loteriji) , so ti algoritmi za potrebe kriptografije zaenkrat povsem ustrezni. Marko Petkovšek IRačunalništvo REŠITEV PROBLEMA PRAŠTEVIL V začetku avgusta 2002 je časopis New York Times objavil novico, ki je vznemirila matematike in računalnikarje po vsem svetu. Indijski znanstve- niki Manindra Agraval, Niradž Kajal in Nitin Saksena so namreč odkrili učinkovit računski postopek za reševanje naslednjega problema. Problem praštevil. Dano je naravno število n, Ali je ti praštevilo? Seveda znajo ta preprosti problem rešiti že osnovnošolci. 1. METODA. Število ti po vrsti delimo z 2,3, . .. , n - 1. Če se deljenje nikoli ne izide, je n praštevilo, sicer je sestavljeno število. Zakaj torej takšno vznemirjenje? V kriptografiji, ki se ukvarja s šifriranjem sporočil, potrebujemo zelo velika praštevila, takšna s sto ali več des etiškimi mesti. Tipičen problem je npr. ugotoviti, ali je število n = 10100 + 267 praštevilo. Koliko časa bomo potrebovali s prvo metodo? Recimo, da je naš računalnik zelo hiter in opravi 1012 deljenj na sekundo. Na odgovor bomo torej v najslabšem primeru (če je število n zares praštevilo in je treba opraviti vsa delj enja) čakali približno 1088 sekund oziroma 3.17 x 108 0 let. Hmm ... Ali ne bi šlo hitreje? Bi . Če je število ti produkt dveh faktorjev, je vsaj eden od njiju manjši ali enak yTi. Torej zadošča n deliti s števili, ki ne presegajo yTi. Poleg tega je dovolj deliti le s praštevili. 2 . METODA. Število n po vrsti delimo s praštevili od 2 do P, kjer je p največje praštevilo, ki ne presega yTi. Če se deljenje nikoli ne izide, je ti praštevilo, sicer je sestavljeno število. Pri oceni časovne zahtevnosti druge metode upoštevajmo le čas, potreben za deljenja, saj lahko tabelo praštevil do YTi pripravimo vnaprej. Vedeti moramo torej, koliko je praštevil , ki ne presegajo yTi. Po znamenitem Gaussovem izreku o praštevilih je praštevil do N približno N / ln N, kjer ln označuje naravni logaritem. Torej bo po drugi metodi treba opraviti približno YTi/ ln yTi;:::;:; 8.69x 1047 deljenj, kar bo trajalo 8.69x 1035 sekund oziroma 2.75 x 1028 let. Tudi z drugo metodo ne bomo dočakali rezultata (10 100 + 267 je namreč v resnici praštevilo) . Nadaljevanje na III. strani ovitka.