-
Potrebna nam je numerička procedura koja je laka u jednom pravcu,
-
a teška u drugom.
-
To nas dovodi do modularne aritmetike, takođe poznate kao aritmetika sata.
-
Na primer, da nađemo 46 mod 12, možemo uzeti uže dužine 46 jedinica,
-
i obmotati ga oko sata od 12 jedinica koji se zove 'modulist',
-
rešenje je tamo gde je kraj užeta.
-
Dakle, kazemo da je 46 mod 12 kongruentno 10.
-
Da napravimo ovo da radi, uzećemo prosti 'modulist', kao što je 17.
-
Tada nalazimo primitivni koren od broja 17, u ovom slučaju to je 3.
-
On poseduje veoma važnu osobinu, a to je da kada se podigne na različite stepene
-
rešenje se raspoređuje ravnomerno oko sata.
-
3 je poznato kao generator. Ako podignemo 3 na bilo koji stepen x,
-
tada je rešenje jednako verovatno da bude bilo koji ceo broj između 0 i 17.
-
Sada, obrnut postupak je težak.
-
Na primer, za dato 12, naći stepen na koji 3 treba da bude podignuto.
-
Ovo se naziva problemom diskretnog logaritma.
-
I sada imamo našu funkciju u jednom pravcu.
-
Laka za izvršiti, ali teška u suprotnom smeru.
-
Za dato 12, treba da pokušamo svaku mogućnost dok ne dođemo do odgovaraujćeg stepena.
-
Koliko je ovo teško?
-
Za male brojeve je lako, ali ako koristimo prost 'modulist' koji je se satoji od stotina cifara,
-
postaje nepraktično za rješavanje.
-
Čak i ako biste imali pristup svoj kompjuterskoj moći na Zemlji, moglo bi potrajati hiljadama godina
-
dok se ne ispitaju sve mogućnosti.
-
Dakle snaga funkcije u jednom smeru se zasniva na vremenu koje je potrebno da se ona reši u drugom smeru.
