-
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ć.
