Zagadnienie logarytmu dyskretnego

Potrzebowaliśmy procedury liczbowej, łatwej do przeprowadzenia w jedną stronę i trudnej w przeciwną. A to prowadzi nas do arytmetyki modularnej, niekiedy zwanej zegarową. Np. żeby wyznaczyć 46 mod 12, możemy wziąć sznurek długości 46 jednostek i owinąć go wokół zegara z 12 jednostek, zwanego modułem. Punkt, w którym sznurek się kończy, jest rozwiązaniem. Mówimy więc, że 46 mod 12 jest przystające do 10. Proste! A teraz, żeby to działało, używamy modułu – liczby pierwszej, np. 17, i wyznaczamy pierwiastek pierwotny z 17, w tym przypadku 3. Ma on tę ważną własność, że gdy podniesiemy go do różnych potęg, rozwiązania rozłożą się równomiernie wokół zegara. Liczba 3 jest generatorem. Jeśli podniesiemy 3 do dowolnej potęgi x, to rozwiązaniem, z równym prawdopodobieństwem, może być każda liczba całkowita od 0 do 17. Procedura odwrotna jest znacznie trudniejsza. Znajdźcie dla liczby 12 potęgę, do której trzeba podnieść 3. Nazywa się to problemem logarytmu dyskretnego. I mamy jednokierunkową funkcję, którą łatwo wykonać, a trudno odwrócić! Dla 12 wykładników musielibyśmy szukać metodą prób i błędów. Czy to trudne? Przy małych liczbach - proste, ale jeśli stosujemy moduł kilkusetcyfrowy, rozwiązywanie staje się niepraktyczne. Choćbyście mieli dostęp do całej mocy obliczeniowej na świecie, zbadanie wszystkich możliwości potrwałoby tysiące lat. Zatem siła funkcji jednokierunkowej zależy od czasu, którego potrzeba, aby ją odwrócić.