-
Potřebujeme číselnou operaci,
-
která je jednoduchá v jednom směru a obtížná v opačném.
-
To nás přivádí k modulární aritmetice,
-
kterou dobře známe z principu fungování hodin.
-
Například ...
-
Abychom našli 46 modulo 12,
-
tak vezmeme provázek dlouhý 46 jednotek
-
a obalíme ho okolo hodin, které mají obvod 12 jednotek ...
-
Čemuž se říká modulus.
-
... a tam, kde provázek končí, leží řešení.
-
Takže 46 modulo 12 je kongruentní s 10.
-
Jednoduché.
-
Aby postup fungoval, tak musíme použít jako modulus prvočíslo.
-
Například 17.
-
Pak najdeme primitivní kořen sedmnácti.
-
V tomto případě je to 3 a má jednu důležitou vlastnost,
-
protože všechny mocniny budou rovnoměrně rozmístěny na hodinách.
-
Primitivnímu kořenu 3 se říká generátor.
-
Pokud ji umocníme jakýmkoliv exponentem 'x',
-
tak bude pro každé číslo mezi 0 a 17 stejně pravděpodobné, že bude řešením.
-
Inverzní operace je ale náročná.
-
Například ...
-
Jakou mocninu tří potřebujeme, aby nám vyšlo číslo 12?
-
Toto je takzvaný problém diskrétního logaritmu.
-
Nyní máme vhodnou jednosměrnou funkci.
-
Snadno proveditelnou v jednom směru, ale náročnou v opačném.
-
S daným číslem 12 bychom museli hledat výsledek metodou pokus-omyl.
-
Jak těžké by to bylo?
-
S malými čísly to je jednoduché,
-
ale pokud si vezmeme prvočíselný modulus, který má stovky cifer,
-
tak řešení metodou pokus-omyl bude prakticky nemožné.
-
I kdybyste mohli využít veškerou výpočetní kapacitu na Zemi,
-
tak by trvalo tisíce let, než byste prošli všechny možnosti.
-
Takže síla jednosměrné funkce je založena na čase potřebném pro získání její inverze.
