Informatyka dla klas II

Na dzień dzisiejszy nie istnieje żaden powszechnie znany, 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 = 2⁴ × 3 × 5² 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:

p₁₂₀₀ = 2^a  × 3^b  × 5^c, 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.

44100 = 2 × 2 × 3 × 3 × 5 × 5 × 7 × 7
 

Metoda bezpośrednia

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:	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

 

Metoda Fermata

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  = x² - y²,

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  = x² - y² 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:

y² = x² - 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.

Algorytm rozkładu liczby naturalnej na czynniki pierwsze metodą Fermata

Wejście

p

–

liczba rozkładana na czynniki pierwsze, p N, p  jest nieparzyste

Wyjście:

Czynniki pierwsze liczby p.

Elementy pomocnicze:

x,y,z	–	zmienne do rozkładu p. x,y,z N
m,n	–	czynniki p, m,n N

Lista kroków dla procedury rekurencyjnej Fermat(p)

K01:	x ← ceil(√p)	; obliczamy wartość początkową dla x
K02:	z ← x2 - p	; z = y2
K03:	y ← floor(√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   
im. Kazimierza Brodzińskiego
w Tarnowie
©2024 mgr Jerzy Wałaszek