Rozkład liczb na czynniki pierwsze

Na dzisiejszych zajęciach rozwiążemy problem przedstawienia liczby p w postaci iloczynu liczb pierwszych. Posiada on duże znaczenie w wielu dziedzinach informatyki – szczególnie w kryptografii. 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ć.

 

Rozkład na czynniki pierwsze
(C)2013 mgr Jerzy Wałaszek

p =


...

Rozwiązanie 1

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

 

Algorytm rozkładu liczby naturalnej na czynniki pierwsze

Wejście
p     liczba rozkładana na czynniki pierwsze, p N, p > 1
Wyjście:

Czynniki pierwsze liczby p.

Elementy pomocnicze:
g    granica sprawdzania podzielności liczby p. g N
i  – kolejne podzielniki, i N
Lista kroków:
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:         pp 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  

 

Rozwiązanie 2

Poprzedni algorytm sprawdza podzielność liczby p przez wszystkie kolejne liczby naturalne, zawarte w przedziale <2,√p>. Tymczasem poszukiwane podzielniki muszą być liczbami pierwszymi. Jeśli nie mamy liczb pierwszych pod ręką, to przynajmniej możemy ograniczyć dzielenia do liczb 2, 3 oraz 6k±1, dla k = 1,2... wpadających w przedział <2,√p>. Prezentowany poniżej algorytm dokonuje takiej właśnie optymalizacji, redukując do 1/3 liczbę sprawdzanych podzielników.

 

Algorytm rozkładu liczby naturalnej na czynniki pierwsze

Wejście
p     liczba rozkładana na czynniki pierwsze, p N, p > 1
Wyjście:

Czynniki pierwsze liczby p.

Elementy pomocnicze:
g    granica sprawdzania podzielności liczby p. g N
i  – kolejne podzielniki, i N
k,d  – zmienne do generacji liczb postaci 6k±1, k N, d {-1, 1}
Lista kroków:
K01: g[√p] ; wyznaczamy granicę sprawdzania podzielności
K02: k ← 1;  d ← -1 ; współczynniki do generacji liczb postaci 6k±1
K03: i ← 2 ; początek sprawdzania podzielności
K04: Dopóki ig wykonuj kroki K05...K12  
K05:     Dopóki p mod i = 0 wykonuj kroki K06...K07 ; wyznaczamy dzielnik p
K06:         Pisz i  
K07:         pp div i ; modyfikujemy p
K08:     Jeśli p = 1, to idź do K14 ; p nie jest już podzielne
K09:     Jeśli i ≥ 3, to idź do K11 ; wyznaczamy następny podzielnik
K10:     ii + 1 i następny obieg pętli K04 ; podzielniki 2 i 3
K11:     i ← 6k + d ; pozostałe, postaci 6k±1
K12:     Jeśli d = 1, to d ← -1;   kk + 1
    inaczej           d ← 1
; modyfikujemy współczynniki dla następnego podzielnika
K13: Jeśli p ≠ 1, to pisz p ; ewentualny, ostatni podzielnik
K14: Zakończ  




List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.