-
Potrebujeme číselnú operáciu, ktorá je jednoduchá a rýchla v jednom smere
-
a komplikovaná v druhom.
-
To nás vedie k modulárnej aritmetike, ktorú si vieme predstaviť ako aritmetiku na hodinách.
-
Napríklad, aby sme našli 46 modulo (zvyšok) 12, zoberieme špagát dlhý 46 jednotiek
-
a obalíme ho okolo hodín, ktoré majú obvod 12 jednotiek.
-
Tam kde sa špagát končí, leží riešenie.
-
Takže 46 modulo 12 je zhodné s 10.
-
Jednoduché. Aby mohol postup fungovať musíme použiť prvočíslo napr. 17.
-
Potom nájdeme primitívny koreň sedemnástich, tu to je 3.
-
3 má dôležitú vlastnosť. Jej rôzne mocniny budú rozmiestnené
-
po hodinách rovnomerne.
-
3 tu funguje ako generátor. Ak ju umocníme akýmkoľvek exponentom,
-
bude pre každé číslo medzi 0 a 17 rovnako pravdepodobné, že bude riešením.
-
Ale opačná operácia je teraz náročná.
-
Napríklad koľkú mocninu troch musíme vziať aby nám vyšlo číslo 12?
-
Toto je takzvaný problém diskrétneho logaritmu.
-
Teraz máme vhodnú jednosmernú funkciu.
-
Ľahká v jednom smere, náročná v opačnom.
-
S daným číslom 12 by sme museli hľadať výsledok metódou pokus-omyl.
-
Aké ťažké to je?
-
S malými číslami to je jednoduché, ale ak si vezmeme zvyšok po delení niekoľko sto ciferným číslom,
-
pokus-omyl sa stane nepraktickým.
-
Ak by ste mali prístup ku všetkej výpočtovej sile na Zemi, trvalo by vám stovky rokov,
-
kým by ste prešli všetky možnosti.
-
Takže sila jednosmernej funkcie je založená na čase potrebnom na jej otočenie.
