YUTECHME

Početkom septembra geografski distribuirana računarska mreža PrimeGrid je pronašla novi najveći prost broj. U pitanju je 919444¹⁰⁴⁸⁵⁷⁶ + 1. Ovaj broj je dugačak 6,253,210 cifara i trenutno se nalazi na prvom mestu Kris Kodvelove (Chris Caldwell) liste najvećih poznatih prostih brojeva.

Da se podsetimo, prosti brojevi su nedeljivi, ili što bi profesor matematike rekao deljivi jedino sa 1 i sa samim sobom. Njih treba posmatrati kao gradivne blokove ostalih brojeva. Ukoliko neki broj nije prost, iterativno se može deliti na manje brojeve sve dok se ne dođe do prostih. Na primer, 30 na dva puta 15, pa 15 na 3 puta 5, ali dalje neće moći. Dakle broj 30 mogu da izgradim množenjem prostih brojeva 2, 3 i 5, ali da stvar bude bolja, ovo je ujedno i jedina kombinacija prostih brojeva koja daje broj 30. Oni su ključevi za sve druge brojeve. Ukoliko broj 30 zamislimo kao bravu, ona može biti otključana samo ključevima 2, 3 i 5. Ne postoji druga kombinacija.

Prostih brojeva ih ima beskonačno puno. Trenutno najveći poznati prost broj je 919444¹⁰⁴⁸⁵⁷⁶ + 1, ali računari širom sveta neprestano tragaju za novim i neminovno je da će kad-tad biti otkriven. Ova potraga više liči na sportski lov, nego li na glad za što većim prostim brojem. Budimo realni, trenutno nam poznavanje ovog broja i nije toliko neophodno, a ako to postane upogonićemo dostupne super-računare pa će ga naći.

Pustiti računar da traži prost broj ima smisla, ali raditi to na papiru sa olovkom, moram da priznam da ne razumem. Očigledno propuštam nešto veoma bitno pošto su najveći umovi ovome davali veliki značaj. Euklid je pre 2,500 godina shvatio da su prosti brojevi gradivni i dokazao ih ima beskonačno puno. Znam da je ovaj dokaz elegantan i da se ovako nešto može pokazati u par linija. Međutim, dokazati da je 2³¹ – 1 = 2,147,483,647 prost broj mi deluje apsolutno suludo. Ojler je to uradio sa perom pre nekih 300 godina. Ali ovo je ništa spram Lukasa koji je pre 200 godina dokazao da je 2¹²⁷ – 1 (39 cifara dug broj) prost. Ovo je ujedno i poslednjih ručno izračunati najveći prost broj. Verujem da je šale radi pokazao da 2⁶⁷ – 1 nije prost broj, ali nije znao proizvod koja dva prosta broja ga daje. Posle nekih 40 godina Frenk Nilson Kol je pronašao ta dva broja. Kako je sam rekao, za ovo su mu bile potrebne sve nedelje u tri godine (“three years of Sundays”).

U računarskoj nauci veliki prosti brojevi su svoje mesto našli na prvom mestu u kriptografiji, algoritmima za enkripciju (šifrovanje) podataka. Što su veći to je enkripcija sigurnija i teža za dešifrovanje ili “razbijanje”. Lukasov broj 2⁶⁷ – 1 su “razbijali” 40 godina jer je proizveden množenjem dva velika prosta broja. Ukoliko ovo nije slučaj, stvari idu dosta lakše. Naravno u kriptografiji i treba da idu teže, pa se algoritmi oslanjaju na proizvod dva veoma velika prosta broja. Ukoliko je on poznat, veoma je teško rekonstruisati njegove činioce, proste brojeve čijim množenjem je nastao. Pošto su prosti, oni su ujedno i jedini koji ga mogu proizvesti. Na ovome se zasniva jedan od danas najpopularnijih i najprimenjenijih algoritama za kriptovanje podataka – RSA. Ime je dobio od prvih slova imena ljudi koji su ga napravili: Ronald Rivest (Ronald Rivest), Adi Šamir (Adi Shamir) i Leonard Ejdlman (Leonard Adleman).

RSA je tehnička realizacija genijalne ideje kriptovanja javnim ključem koju su predložili Difi (Whitfield Diffie) i Helman (Martin Hellman). Oni su napravili jednostavan algoritam kojim pošiljalac poruke može da je šifruje, ali ne može da je dešifruje. Šifrovanjem poruka dobija vlasnika, ali to nije pošiljalac već primalac. Samo onaj kome je poruka namenjena može da je dešifruje i pročita. U RSA algoritmu on to uradi tako što uzme dva velika prosta broja, pomnoži ih, a proizvod obelodani. Par prostih brojeva se zove privatni ključ, a njihov proizvod je javni ključ. Pošto je javan svako može da ga upotrebi, pripremi poruku, enkriptuje i pošalje, a samo vlasnik privatnog ključa može da je dekriptuje i pročita. U ovome je genijalnost algoritma. Šifrovanje poruke javnim ključem je veoma jednostavno, a dešifrovanje bez privatnog ključa praktično nemoguće.

Algoritam radi i u suprotnom smeru. Ako tekst šifrujete privatnim ključem, možete da ga dešifrujete samo javnim ključem. Ali zašto bi to neko radio? Pa zar javni ključ nije dostupan svima? Dakle svako može da dešifruje poruku. Jeste, upravo zbog toga se ovaj pristup koristi za proveru identiteta. Vlasnik privatnog ključa ume da enkriptuje poruku tako da dekriptovanjem svi drugi mogu da provere da ju je baš on poslao. Zapravo RSA implementacija koristi obe osobine algoritma. Svaka poruka se prvo šifruje privatnim ključem pošiljaoca, pa javnim ključem primaoca. Na ovaj način poruka se bezbedno može poslati preko Interneta, a onaj kome je namenjena može biti siguran u njenu verodostojnost. Impresivno, zar ne?