i i “Kovic” — 2021/2/19 — 8:20 — page 197 — #1 i i i i i i NOVE KNJIGE L. Rempe-Gillen, R. Waldecker, Primality testing for beginners, Student Mathematical Library Vol. 70, American Mathematical Society, 2014, 244 strani. S praštevili se srečamo že zelo zgodaj. Učimo se, da lahko poljubno naravno šte- vilo, različno od ena, zapǐsemo kot pro- dukt potenc praštevil. Torej so prašte- vila osnovni gradnik naravnih števil, in po tej svoji lastnosti so tudi dobila ime. Pri iskanju prafaktorjev danega števila kaj hitro ugotovimo, da na vprašanje, ali je neko število praštevilo, ne znamo ve- dno enostavno odgovoriti. Problem poi- skati algoritem, ki bi v polinomskem ča- su glede na število znakov v zapisu da- nega števila (učinkovit algoritem) pri enakem številu vedno podal enak odgo- vor (determinističen algoritem), ali je število res praštevilo, je dolgo časa mučil matematike. Že v 70. letih so obstajali nedeterministični algoritmi, ki testi- rajo praštevilskost z visoko verjetnostjo pravilnega odgovora. Leta 2002 pa so Agrawal, Kayal in Saxena odkrili učinkovit in determinističen test pra- številskosti, ki je danes znan kot AKS algoritem. Najava rezultata je kmalu pritegnila veliko pozornosti, objava v prestižni reviji Annals of Mathematics pa je sledila dve leti kasneje. Osrednji namen knjige je predstaviti natanko tiste koncepte, ki so potrebni za razumevanje smisla in dokaza omenjenega rezultata, pri čemer se predpostavlja poznavanje le srednješolske matema- tike. Iz predgovora je mogoče razbrati, da je knjiga nastala po predavanjih avtorjev na nemški poletni akademiji za srednješolce leta 2005. Povod za izvedbo takih predavanj je bila izjemna dostopnost do tako pomembnega in lepega dosežka, kar je v matematiki prava redkost. Knjiga je namenjena predvsem mladim matematikom in bolj amaterskim entuziastom z matematično žilico, ki želijo podrobneje spoznati paradigmo Obzornik mat. fiz. 67 (2020) 5 197 i i “Kovic” — 2021/2/19 — 8:20 — page 198 — #2 i i i i i i Nove knjige in prakso modernega matematičnega raziskovanja, v katerem poleg dobrega poznavanja teorije igrajo (že pri samem oblikovanju hipotez, kot tudi pri njihovem testiranju in dokazovanju) nepogrešljivo vlogo tudi računalniki, algoritmi in eksperimentiranje, podobno eksperimentiranju v drugih znano- stih. Toda to nikakor ne pomeni, da knjiga ni zanimiva tudi za bolj izkušene matematike. Knjiga je napisana in oblikovana zelo pregledno, z algoritmi v okvirčkih, ter z definicijami in izreki na osenčenih poljih. V uvodu je poleg privlačnega opisa celotne vsebine pojasnjen tudi koncept matematičnega dokaza, razlo- žen pa je tudi pomen definicij, lem in izrekov. Prav tako so opisani pogosti simboli in pojmi, ki so stavljeni krepko. Vsi algoritmi so zapisani v prepro- sti psevdokodi, kar olaǰsa branje programiranja neveščemu bralcu. Knjiga je razdeljena na dva dela, Osnove in AKS algoritem. Sledita dodatka, na- menjena odprtim problemom in rešitvam pomembneǰsih nalog, prav tako seznam literature in uporabljenih simbolov ter stvarno kazalo. Skoraj vsako poglavje se zaključi z navedbo in kratkim opisom dodatne literature. Ve- čina podpoglavij na koncu vsebuje naloge, ki pomagajo pri utrjevanju in razumevanju snovi iz pripadajočega podpoglavja ter poudarjajo lastno ak- tivnost bralca (angl. learning by doing). Pogosto nalogam sledi še razdelek z dodatnimi napotitvami na ustrezno literaturo in zgodovinskimi pojasnili ter zahtevneǰsimi nalogami. Na kratko preglejmo vsebino knjige. Prvi del, Osnove, vsebuje štiri poglavja. Prvo obravnava osnovne lastnosti naravnih števil in praštevil. Spoznamo princip matematične indukcije, pojem deljivosti, osnovni izrek aritmetike, Evklidov algoritem in Eratostenovo rešeto. Že res, da je Era- tostenovo rešeto determinističen algoritem za odločitveni problem prašte- vilskost (angl. primes), ki naj z da ali ne odgovori na vprašanje, ali je dano število n praštevilo. Toda ta algoritem je daleč od učinkovitega, saj je njegova časovna zahtevnost polinomska v n, ne pa tudi v log n. Drugo poglavje je namenjeno algoritmom in računski zahtevnosti. Že uvodne besede nakazujejo, da na preprosto vprašanje, kaj je algoritem, ni lahko najti dobrega odgovora. Za ponazoritev pojma algoritem avtorja posrečeno navedeta algoritma za peko palačink ter za pisanje kriminalnih uspešnic, nato pa v obliki algoritma zapǐseta še znano Collatzovo funkcijo, ki sodo število n zamenja z n/2, liho število n pa s 3n + 1. Mimogrede 198 Obzornik mat. fiz. 67 (2020) 5 i i “Kovic” — 2021/2/19 — 8:20 — page 199 — #3 i i i i i i Primality testing for beginners je predstavljena še slavna in nedokazana Collatzova domneva, ki pravi, da se ta postopek vselej konča s številom 1. V nadaljevanju sta definirana in s kopico primerov ilustrirana razreda P in NP, poglavje pa se zaključi z definicijama nedeterminističnih algoritmov tipov Monte Carlo in Las Vegas, ki spadata v razred verjetnostnih algoritmov. Metoda Monte Carlo daje pravilne rezultate le z določeno verjetnostjo, metoda Las Vegas pa vselej daje pravilen rezultat, toda njen računski čas je lahko neomejen. Cilj knjige je dokaz trditve praštevilskost ∈ P. Tretje poglavje je jedro knjige, saj tu spoznamo pojme in orodja iz teorije števil, na katerih temeljijo vsi moderni testi praštevilskosti. Najpomem- bneǰsa rezultata sta mali Fermatov izrek ap−1 ≡ 1 (mod p), ki velja za vsako celo število a tuje praštevilu p, in Eulerjeva posplošitev aϕ(n) ≡ 1 (mod n) za n ≥ 2, kjer je D(a, n) = 1, ϕ(n) pa je število tistih elementov množice {1, . . . , n−1}, ki so tuja številu n. S tem je povezan tudi red števila a po modulu n z oznako orda(n), ki je definiran kot najmanǰsi tak eksponent k ∈ N, za katerega velja ak ≡ 1 (mod n). Izrek lahko uporabimo za nasle- dnji Fermatov test. Naključno izberimo a iz množice {1, . . . , n − 1}. Če je D(a, n) 6= 1, odgovorimo »n je sestavljeno število«. V nasprotnem izraču- namo an−1 po modulu n, za kar obstaja učinkovit algoritem. Če dobljeno število ni 1, ponovno odgovorimo »n je sestavljeno število«, v nasprotnem pa »n je morda praštevilo«. Mali Fermatov izrek zagotavlja, da v primeru pra- števila n algoritem vrne rezultat »n je morda praštevilo«, toda to se lahko zgodi tudi za sestavljena števila n, npr. za n = 15 in a = 11. Taka števila n se imenujejo psevdopraštevila glede na osnovo a. Izkaže se, da je število ti- stih osnov, za katera je n psevdopraštevilo, lahko ϕ(n) ali pa največ ϕ(n)/2. Če bi vedno veljalo le slednje, bi bil Fermatov test učinkovit algoritem tipa Monte Carlo (RP) za odločitveni problem sestavljenost (ang. composi- tes). Žal pa obstajajo Carmichaelova števila, ki so psevdopraštevila glede na vsako možno bazo. Prvo tako število je 561. Vseeno lahko Fermatov test popravimo do verjetnostnega algoritma. Gary L. Miller je leta 1976 doka- zal posebno verzijo malega Fermatovega izreka, ki ga je štiri leta kasneje Michael O. Rabin uporabil pri konstrukciji Miller-Rabinovega algoritma, ki dokazuje pripadnost problema sestavljenost razredu RP. V knjigi je pravilnost delovanja algoritma dokazana v četrtem poglavju, kjer pred tem spoznamo še osnove kriptografije in RSA metode šifriranja, najpomembnej- Obzornik mat. fiz. 67 (2020) 5 199 i i “Kovic” — 2021/2/19 — 8:20 — page 200 — #4 i i i i i i Nove knjige šega primera kriptografije z javnim ključem. Pri tej metodi odločilno vlogo igrajo javno znana števila, ki so produkt dveh velikih in naključno generi- ranih praštevil, skriti tudi uporabnikoma RSA šifriranja. Varnost metode temelji na principu, da je bistveno lažje ugotoviti, da je neko število se- stavljeno, kot pa ga faktorizirati. Prvi del odlično opravi Miller-Rabinov algoritem, ki je popularen tudi zaradi svoje hitrosti. Čeprav sta računski zahtevnosti AKS in Miller-Rabinovega algoritma enaki, je njuna hitrost na konkretnih primerih težko primerljiva. Učinkovitost izbora naključnega pra- števila zagotavlja šibka verzija praštevilskega izreka x  π(x) log x, ki je v knjigi dokazana pred Miller-Rabinovim algoritmom. Do sedaj še nikomur ni uspelo najti učinkovitega algoritma, ki bi podal faktorizacijo poljubnega števila, in splošno prepričanje je, da tak algoritem ne obstaja. Bi se pa to z iznajdbo delujočega kvantnega računalnika spremenilo, saj taki kvantni algoritmi obstajajo. Drugi del knjige ima tri poglavja in je namenjen AKS algoritmu. V pr- vem poglavju izvemo, da prava pot k determinističnemu testu praštevilskosti pelje preko polinomske različice malega Fermatovega izreka: za praštevilo p velja (P (X))p ≡ P (Xp) (mod p), kjer je P (X) celoštevilski polinom. Osnovne lastnosti polinomske modularne aritmetike se obravnavajo že v za- dnjih dveh podpoglavjih tretjega poglavja v prvem delu knjige. Toda take kongruence še niso dovolj, potrebno je študirati (P (X))n ≡ P (Xn) (mod n,Q), kjer je tudi Q celoštevilski polinom. Ta zapis pomeni, da pri deljenju leve in desne strani s Q dobimo enak ostanek po modulu n. Posledica Fermatovega izreka je, da če za neka polinoma P in Q kongruenca ne velja, je n sestav- ljeno število. Obratno ni vedno res, kot kaže primer (X − 1)24 ≡ X24 − 1 (mod 24, X2−1), ki je bralcu prepuščen v samostojno reševanje. Vprašanje je, ali obstajata taki majhni množici polinomov P in Q, za katere veljav- nost pripadajočih kongruenc implicira praštevilskosti števila n. Agrawal, Kayal in Saxena so dokazali, da takšni množici obstajata. Koraki njihovega algoritma so presenetljivo enostavni, toda preverba učinkovitosti delovanja je bistveno težja. V prvem koraku preverimo, ali je n popolna potenca, za kar obstaja učinkovit algoritem. Če je odgovor negativen, se v drugem koraku z r sprehodimo po naravnih številih na naslednji način. Najprej se 200 Obzornik mat. fiz. 67 (2020) 5 i i “Kovic” — 2021/2/19 — 8:20 — page 201 — #5 i i i i i i Primality testing for beginners z Eratostenovim rešetom prepričamo, da je r praštevilo. Če velja r < n in r deli n, odgovorimo »n ni praštevilo«. Če je r ≥ n, odgovorimo »n je praštevilo«. Če ne velja nič od tega, izračunamo ordr(n). Drugi korak ponavljamo, dokler ne dobimo enega od gornjih dveh odgovorov ali dokler ne velja ordr(n) > (2 log2 n) 2. Če se zgodi slednje, začnemo z izvajanjem tretjega koraka, kjer preverjamo veljavnost kongruence (X + a)n ≡ Xn + a (mod n,Xr − 1) za vsak a ∈ {1, . . . , r}. Če katera od kongruenc ni izpolnjena, odgovorimo »n ni praštevilo«, sicer pa »n je praštevilo«. Seveda se porajata ključni vprašanji, ali pravilnost vseh kongruenc res zagotavlja praštevilskost števila n, in ali lahko vedno učinkovito poǐsčemo tak r, pri čemer mora njegova ve- likost naraščati kvečjemu polinomsko v log n. Na prvo vprašanje odgovori osrednji izrek Agrawala, Kayala in Saxene, ki je dokazan v drugem poglavju. Zahtevane lastnosti števila r so dokazane v zadnjem poglavju knjige, kjer je pravilnost delovanja AKS algoritma pregledno dokazana po korakih. V zaključku sledijo še diskusije o hitrosti algoritma, nekaterih odvečnih ome- jitvah in nadaljnjem razvoju. Knjigo, ki daje celovit pregled vsega, kar je potrebno za razumevanje AKS algoritma, zaokrožajo nekateri izreki in odprti problemi s področja teorije števil in reference za nadaljnji študij. Mnogi slavni odprti problemi iz teorije števil so navdihnili tudi popularne knjige, kot je npr. Doxiadisova Uncle Petros and Goldbach’s Conjecture. Vsem, ki jih zanimajo prašte- vila in odprti problemi v zvezi z njimi ter odkrivanje zelo velikih prašte- vil, avtorja svetujeta ogled spletne strani The Prime Pages, dostopne na https://primes.utm.edu/. Knjiga izpolnjuje uvodne obljube in ponuja številne priložnosti za njeno uporabo. Na gimnazijskem matematičnem krožku bi se jo lahko predelalo v enem letu, program bi bilo mogoče izvesti tudi v obliki delavnic in pro- jektov na kakšnem od matematičnih taborov. Ker je vsebina knjige na stičǐsču elementarne in računske teorije števil, je vsebina zagotovo zanimiva za nadarjene dijake. Vsekakor imamo pred seboj odlično napisano strokovno matematično knjigo. Jurij Kovič in Aleksander Simonič Obzornik mat. fiz. 67 (2020) 5 XIX