Podsumowanie (co dalej?)

Gratulacje. Dotarliśmy do rozgałęzienia. Wprowadziłem kilka różnych pojęć, więc zorientujmy się, na czym stoimy, zanim wyruszymy w różne strony. Co było motywem przewodnim tej lekcji? Uczyliśmy się już o szyfrowaniu RSA, a RSA opiera się na dwu sprawach. Po pierwsze, rozkład na czynniki pierwsze jest trudny. Jeśli mnożę dwie duże liczby pierwsze, P1 i P2, i podaję wam N, to mogę wierzyć… czuję się bezpieczny, bo długo szukalibyście tych liczb pierwszych. Może nie wystarczyłoby wam życia! Po drugie, RSA wymaga, by wygenerowanie tych dużych liczb pierwszych było łatwe. Żebym mógł szybko wygenerować dużą liczbę pierwszą. Wróćmy do pierwszego problemu. Trudność rozkładu na czynniki pierwsze. Co jest takiego w rozkładzie czy w samych liczbach pierwszych, że tak utrudniają zadania? Żeby się dowiedzieć, zacznijmy od początku. Stwierdźmy, czy x jest liczbą pierwszą czy złożoną. To test pierwszości. Opracowaliśmy kilka rozwiązań. Robiąc to, zorientowaliśmy się, że ten problem jest obliczeniowo kosztowny. Nie ma natychmiastowego rozwiązania. Gdy rosły liczby wejściowe, ilość czasu czy liczba kroków potrzebnych do znalezienia rozwiązania, także rosła. Jak bardzo? Określamy to, przewidując przestrzeń poszukiwań dzięki twierdzeniu o liczbach pierwszych. Prawdziwy kłopot można przedstawić na wykresie. Na osi pionowej jest liczba kroków wykonanych przez algorytm, czyli, poniekąd, czas. A na osi X jest wielkość wejściowa. Z jej wzrostem rósł także czas. Kłopot w tym, że kształt tej krzywej jest nie do zaakceptowania. W naszym przypadku, gdy N sięgnie 20 cyfr, nie zdołamy rozwiązać zadania w najgorszym scenariuszu. Przy kilkusetcyfrowej liczbie wejściowej nasz algorytm nie zadziała. Padnie. Praktycznie więc nie można sprawdzić pierwszości dużej liczby wejściowej przy użyciu naszych metod. Wróćmy do punktu pierwszego, rozkładu na czynniki pierwsze. Podczas tej lekcji zdążyliście się dowiedzieć, że rozkład na czynniki pierwsze musi być trudniejszy niż test pierwszości. Czyli trzeba więcej kroków, by wyznaczyć czynniki pierwsze danej liczby, niż aby powiedzieć, czy jest pierwsza. Pamiętajcie: rozkład na czynniki pierwsze wymaga, byśmy znaleźli wszystkie czynniki pierwsze liczby N… a test pierwszości wymaga tylko, byśmy znaleźli jeden podzielnik. Niektórzy użytkownicy zmienili testy pierwszości w algorytmy rozkładu na czynniki pierwsze, powtarzając je po znalezieniu pierwszego podzielnika. Test pierwszości jest zatem pod-metodą w głównym algorytmie rozkładu na czynniki pierwsze. Wróćmy do wykresu. Algorytm wyglądałby tak. Gdy liczby wejściowe rosną, algorytm rozkładu będzie nad tą linią testu pierwszości. W każdej sytuacji mamy granicę obliczeniową, czyli liczbę podstawowych kroków, do obliczenia, zależną od mocy obliczeniowej w każdej sytuacji oraz od ilości czasu, który mamy. Możecie o tym myśleć jako o linii poziomej, albo progu na tym wykresie. Wszystko powyżej tej linii jest poza zasięgiem, niemożliwe do rozwiązania. Podczas tej lekcji ograniczał nas komputer pokładowy łazika, dość powolny; nie dałoby się wykonać testów pierwszości dla liczb większych niż 20-cyfrowe. Jednak nawet gdybyśmy włączyli tysiąc komputerów na rok, tylko przesunęlibyśmy tę linię poziomą w górę. Próg byłby inny. To pozwoliłoby przeprowadzać test większych liczb, ale, jak widać, zawsze byłaby granica. Przy dużej liczbie nie moglibyśmy rozwiązać zadania. To wskazuje wiele ciekawych ścieżek. Określę dwie, które zbadam w następnej kolejności. Po pierwsze: nie omawiałem szczegółowo tych krzywych wzrostu. A pomogłoby, gdyby, dla każdego algorytmu, który mi dajecie, nieważne, co rozwiązuje, ani na jakiej maszynie działa, gdybyśmy mogli wykreślić krzywą wzrostu na tym wykresie, po prostu patrząc na opis algorytmu. Gdybyśmy mogli to zrobić, identyfikowalibyśmy kategorie pewnych kształtów krzywej wzrostu, co mówi nam, jak trudny będzie problem do rozwiązania. W ten sposób zrozumiemy algorytm, zanim go uruchomimy. To bardzo ważne. Możecie mi dać algorytm zapisany na kartce. Spojrzę i powiem: „To niewykonalne dla potrzebnej wielkości liczb wejściowych”. A to prowadzi do lekcji o złożoności czasowej. To bardzo ważne narzędzie, które będzie nam potrzebne. Jeśli słyszeliście o czasie wielomianowym lub wykładniczym… te terminy wiążą się ze złożonością czasową. Dalej. Wielu z was zastanawia się: „Jak w praktyce generować te losowe liczby pierwsze?”. To drugi punkt omawiany przy okazji RSA. Przypomnijmy sobie szybko. Żeby wygenerować dużą liczbą pierwszą, mającą kilkaset cyfr, musimy wykonać instrukcje. Wygenerować losową liczbę, sprawdzić, czy jest pierwsza, jeśli jest – to gotowe. Jeśli nie – próbujemy dalej, aż trafimy na liczbę pierwszą. W tej trzyetapowej procedurze najważniejszy jest etap 2.: sprawdzenie pierwszości. Bez tego nic się nie uda. Jak to działa dzisiaj? Najpierw musimy nieznacznie przedefiniować problem. Następnie, co ważniejsze, musimy użyć losowości. To prowadzi do kolejnej lekcji o algorytmach losowych. I w końcu, jeśli macie inne pytania, proszę, zamieśćcie je poniżej, to zaplanujemy lekcje. Np. musimy zagłębić się w matematykę, żeby przyspieszyć nasz test metodą próbnych dzieleń. Co jeszcze przychodzi wam do głowy? Napiszcie poniżej.