A diszkrét logaritmus probléma

Egy olyan numerikus eljárás kell nekünk, ami könnyű az egyik irányban, de visszacsinálni nehéz. Ez elvezet a moduláris aritmetikához, amit óra-aritmetikának is hívnak. Például ahhoz, hogy megkapjuk 46 modulo 12-t, vehetünk egy 46 egységnyi kötelet, és körbetekerjük egy 12 egység kerületű órán. Ezt modulusnak (maradékos osztásnak) hívjuk, és a kötél vége mutatja az eredményt. Azt mondjuk, hogy 46 modulo 12 kongruens 10-zel. Könnyű. Ahhoz, hogy ez működjön, prím számok modulusát használunk, például 17-et, majd megkeressük 17 egyik primitív gyökét, ez esetben 3-at, ami rendelkezik azzal a fontos tulajdonsággal, hogy különböző hatványokra emelve, az eredmény egyenletesen oszlik el az óra körül. A 3-at generátornak hívjuk. Ha kiszámoljuk a 3 tetszőleges x hatványát, akkor az eredmény azonos valószínűséggel 0 és 17 közötti tetszőleges egész lehet. De a visszaalakítás nehéz. Mondjuk adott a 12, találd meg 3-nak a megfelelő hatványát! Ezt diszkrét logaritmikus problémának hívják. Most megvan az egyirányú függvényünk, könnyű elvégezni, de visszacsinálni nehéz. Ha adott 12, csak próbálkozással juthatunk el a megfelelő kitevőkhöz. Mennyire nehéz ez? Kis számokkal könnyű, de ha több száz számjegyű prím modulust használunk, gyakorlatilag nem lesz megoldható. Még ha rendelkeznél a Föld összes számítási kapacitásával, akkor is több ezer évig tartana az összes lehetőség végigpróbálása. Az egyirányú függvény ereje a visszaállítás időigényén alapul.