-
Potrzebujemy numerycznej procedury, którą łatwo przeprowadzić w jedną stronę, a trudno w drugą.
-
Prowadzi nas to do arytmetyki modularnej, znanej również jako arytmetyka zegarowa albo arytmetyka reszt.
-
Na przykład, by obliczyć 46 modulo 12, możemy wziąć linę o długości 46 jednostek i owinąć wokół zegara, który ma obwód równy 12 jednostkom.
-
12 jest naszym modułem.
-
Miejsce w którym kończy się lina jest naszym rozwiązaniem.
-
Mówimy więc, że 46 modulo 12 jest kongruentne z 10. Proste.
-
By to wszystko działało musimy użyć modułu, który jest liczbą pierwszą.
-
Na przykład 17.
-
Następnie znajdujemy pierwiastek pierwotny 17, w tym przypadku będzie to 3.
-
Pierwiastek pierwotny ma tą ważną własność, że podniesiony do różnych potęg daje rozwiązania, które jednolicie rozkładają się po całym zakresie naszego zegara.
-
3 jest w naszym przypadku generatorem.
-
Jeżeli podniesiemy 3 do dowolnej potęgi X, rozwiązanie z równym prawdopodobieństwem będzie dowolną liczbą całkowitą z zakresu od 0 do 16.
-
Odwrotna procedura jes trudna. Znając 12, obliczenie potęgi do której musi być podniesiona 3 jest znane pod nazwą logarytmu dyskretnego.
-
Uzyskaliśmy w ten sposób naszą funkcję jednokierunkową. Łatwo ją obliczyć w jedną stronę, ale trudno ją odwrócić.
-
Mając 12 musielibyśmy poszukiwać metodą prób i błędów odpowiadający jej wykładnik.
-
Jak trudne jest to zadanie?
-
Dla małych liczb jest proste. Ale jeżeli użyjemy moduł, będący liczbą pierwszą, który składa się z setek cyfr, nasze zadanie urasta do rangi niepraktycznego.
-
Nawet jeżeli mielibyśmy dostęp do całej mocy obliczeniowej na Ziemi, przeglądnięcie wszystkich możliwości mogłoby to pochłonąć tysiące lat.
-
Siła funkcji jednokierunkowej opiera się na czasie potrzebnym do jej odwrócenia.
