Diskrétní logaritmy

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.