Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2013 mgr
Jerzy Wałaszek
|
Na dzień dzisiejszy nie istnieje powszechnie znany żaden szybki algorytm rozkładu dużej liczby naturalnej na czynniki pierwsze (ang. prime factorization). Na tym fakcie opierają swoje bezpieczeństwo współczesne systemy szyfrowania informacji – np. RSA. Dla przykładu rozkład 200 cyfrowej liczby zajął 18 miesięcy wielu komputerom pracującym w sieci – w sumie czas obliczeń dla pojedynczej maszyny wyniósł ponad pół wieku!
Zasadnicze twierdzenie arytmetyki (ang. fundamental theorem of arithmetic) mówi, iż każda liczba naturalna większa od 1 może być jednoznacznie zapisana jako iloczyn liczb pierwszych. Na przykład:
1200 = 24 × 3 × 52 i nie istnieje żaden inny rozkład dla liczby 1200
Znając rozkład liczby na czynniki pierwsze można dla niej określić wszystkie możliwe podzielniki. Na przykład każdy podzielnik liczby 1200 da się zapisać jako:
p1200 = 2a × 3b × 5c, gdzie a {0,1,2,3,4}, b {0,1}, c {0,1,2}
Zatem wszystkich możliwych podzielników jest tyle ile wynosi iloczyn liczebności możliwych wartości a, b i c:
5 x 2 x 3 = 30
Podstawowe twierdzenie arytmetyki mówi nam, iż rozkład na czynniki pierwsze jest zawsze możliwy i jednoznaczny, lecz nie mówi, jak tego mamy dokonać.
Pierwsze podejście do znalezienia rozkładu liczby p na jej czynniki pierwsze jest bardzo prymitywne, chociaż daje oczywiście poprawny wynik. Nazywa się ono bezpośrednim poszukiwaniem rozkładu na czynniki pierwsze (ang. direct search factorization lub trial division) Będziemy sprawdzać podzielność liczby p przez kolejne liczby naturalne od 2 do pierwiastka z p. Jeśli liczba p będzie podzielna przez daną liczbę, to liczbę wyprowadzimy na wyjście, a za nowe p przyjmiemy wynik dzielenia i próbę dzielenia będziemy powtarzać dotąd, aż nie będzie to już możliwe. Wtedy przejdziemy do następnego dzielnika.
Przykład:
Rozłożyć liczbę 44100 na czynniki pierwsze.
Podział | Reszta | Czynnik | Znalezione czynniki | Uwagi |
44100 : 2 = 22050 | 0 | 2 | 2 | dzieli się |
22050 : 2 = 11025 | 0 | 2 | 2 2 | dzieli się |
11025 : 2 = 5512 | 1 | X | 2 2 | nie dzieli się |
11025 : 3 = 3675 | 0 | 3 | 2 2 3 | dzieli się |
3675 : 3 = 1225 | 0 | 3 | 2 2 3 3 | dzieli się |
1225 : 3 = 408 | 1 | X | 2 2 3 3 | nie dzieli się |
1225 : 4 = 306 | 1 | X | 2 2 3 3 | nie dzieli się |
1225 : 5 = 245 | 0 | 5 | 2 2 3 3 5 | dzieli się |
245 : 5 = 49 | 0 | 5 | 2 2 3 3 5 5 | dzieli się |
49 : 5 = 9 | 4 | X | 2 2 3 3 5 5 | nie dzieli się |
49 : 6 = 8 | 1 | X | 2 2 3 3 5 5 | nie dzieli się |
49 : 7 = 7 | 0 | 7 | 2 2 3 3 5 5 7 | dzieli się |
7 : 7 = 1 | 0 | 7 | 2 2 3 3 5 5 7 7 | dzieli się |
Kończymy, ponieważ wynik ostatniego dzielenia jest równy 1 |
44100 = 2 × 2 × 3 × 3 × 5 × 5 × 7 × 7
p | – | liczba rozkładana na czynniki pierwsze, p N, p > 1 |
Czynniki pierwsze liczby p.
g | – | granica sprawdzania podzielności liczby p. g N |
i | – | kolejne podzielniki, i N |
K01: | g ← [√p] | ; granica sprawdzania czynników pierwszych |
K02: | Dla i = 2,3,...,g wykonuj kroki K03...K06 | ; w pętli sprawdzamy podzielność liczby p przez kolejne liczby |
K03: | Dopóki p mod i = 0 | ; dopóki dzielnik dzieli p |
K04: | Pisz i | ; wyprowadzamy go i |
K05: | p ← p div i | ; dzielimy przez niego p |
K06: | Jeśli p = 1, to zakończ | ; pętlę przerywamy, gdy stwierdzimy brak dalszych dzielników |
K07: | Jeśli p > 1, to pisz p | ; p może posiadać ostatni czynnik większy od pierwiastka z p |
K08: | Zakończ |
Pierre de Fermat podał prosty sposób znajdowania czynników (liczb dzielących p bez reszty) liczby nieparzystej p. Opiera się on na spostrzeżeniu, iż jeśli potrafimy znaleźć dwie liczby naturalne x i y, takie że:
p = x2 - y2,
to
p = (x + y) × (x - y),
zatem czynnikami liczby p są:
m = x + y
n = x - y
Znalezione czynniki m i n nie muszą być liczbami pierwszymi, zatem metodę Fermata stosujemy również do ich rozkładu. Jest to możliwe, ponieważ czynniki liczby nieparzystej są również nieparzyste. Czynniki 2 można wyeliminować z p przed zastosowaniem metody Fermata, zatem nie jest to żadne ograniczenie.
Metoda Fermata jest szczególnie efektywna w przypadku czynników leżących w pobliżu pierwiastka z p. W przeciwnym razie jej efektywność jest taka sama lub nawet gorsza jak dla metody próbnych dzieleń. W praktyce metoda Fermata nie jest używana – podajemy ją ze względów dydaktycznych oraz z powodu jej wagi dla innych, bardziej zaawansowanych metod poszukiwań rozkładu liczby na czynniki pierwsze.
Algorytm wykorzystuje bezpośrednio własność p = x2 - y2 do znalezienia liczb x i y. Poszukiwania rozpoczynamy od x równego pierwiastkowi z p zaokrąglonemu w górę do najbliższej liczby całkowitej. Obliczamy:
y2 = x2 - p
Następnie sprawdzamy, czy y jest liczbą całkowitą. Jeśli tak, to znaleźliśmy odpowiednie liczby x i y. Ponieważ liczba p z założenia jest nieparzysta, to wszystkie jej dzielniki są nieparzyste. Obliczamy dzielniki m i n i jeśli są różne od 1, to wywołujemy rekurencyjnie procedurę Fermata do znalezienia ich rozkładu. Jeśli jeden z czynników jest równy 1, to drugi musi być równy p i p jest liczbą pierwszą – wypisujemy p i kończymy.
Ponieważ czynnik musi być mniejszy lub równy p, to:
m = x + y ≤ p
Przy wzroście x rośnie również y lub pozostaje takie samo. Zatem gdy suma x + y przekroczy p, to nie znajdziemy już żadnego dzielnika liczby p i algorytm można zakończyć przyjmując, iż p jest pierwsze.
p | – | liczba rozkładana na czynniki pierwsze, p N, p jest nieparzyste |
Czynniki pierwsze liczby p.
x,y,z | – | zmienne do rozkładu p. x,y,z N |
m,n | – | czynniki p, m,n N |
K01: | x ← ⌈√p⌉ | ; obliczamy wartość początkową dla x |
K02: | z ← x2 - p | ; z = y2 |
K03: | y ← ⌊√z⌋ | ; sprawdzamy, czy z jest kwadratem liczby naturalnej |
K04: | Jeśli z ≠ y2, to idź do K11 | |
K05: | m ← x + y | ; obliczamy czynniki |
K06: | n ← x - y | |
K07: | Jeśli n = 1, to idź do K13 | ; przerywamy przy n = 1, gdyż p jest pierwsze |
K08: | Fermat(m) | ; rozkładamy rekurencyjnie czynniki m i n |
K09: | Fermat(n) | |
K10: | Zakończ | |
K11: | x ← x + 1 | ; następne x |
K12: | Jeśli x + y < p, to idź do K02 | ; kontynuujemy pętlę |
K13: | Pisz p | ; p jest pierwsze |
K14: | Zakończ |
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe