Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 2
Lekcja 6: Test pierwszości- Wprowadzenie
- Wyzwanie: test pierwszości
- Metoda próbnych dzieleń
- Czym jest pamięć komputera?
- Wydajność algorytmu
- Poziom 3: Wyzwanie
- Sito Eratostenesa
- Poziom 4: Sito Eratostenesa
- Test pierwszości z sitem Etastotenesa
- Poziom 5: Próba podziału za pomocą sita
- Twierdzenie o liczbach pierwszych
- Spirala Ulama liczb pierwszych
- Odległość pomiędzy liczbami pierwszymi
- Kompromis czasu i pamięci
- Podsumowanie (co dalej?)
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Podsumowanie (co dalej?)
Dlaczego rozkład na czynniki jest trudny a generowanie liczb pierwszych łatwe? Dokąd pójdziemy dalej z tego miejsca? Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
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.