Porównanie kodów programów rozkładu liczby na czynniki pierwsze

Porównanie sposobów rozkładu liczby na czynniki pierwsze

W filmie z sekcji „Implementacja algorytmu” przedstawiliśmy zoptymalizowany sposób rozkładu liczby na czynniki pierwsze.

Spróbujmy zapisać funkcję, która będzie wykonywać rozkład dowolnej liczby na czynniki pierwsze z jednoczesnym zliczaniem potencjalnych dzielników i obliczaniem czasu wykonania tych obliczeń. Skorzystamy w tym celu z funkcji time().

def rozklad(Q):
	from math import sqrt
	from time import time
	t0 = time()

	# górna granica sprawdzanych dzielników
	g = int(sqrt(Q))+1
	
	# tablica czynników pierwszych
	tab = []

	# licznik sprawdzonych dzielników
	dzielniki = 0

	for p in range(2,g):
		dzielniki += 1
		while Q % p == 0:
			tab.append(p)
			Q = Q // p
			if Q == 1:
				break
		if Q == 1:
			break

	if Q > 1:
		tab.append(Q)

	t1 = time()
	print(f'Znaleziono czynniki pierwsze: {tab}')
	print(f'Czas w sekundach: {t1-t0:.6f}')
	print(f'Sprawdzone dzielniki {dzielniki}')

Możemy przetestować program dla kilku liczb:

rozklad(44100)
# Znaleziono czynniki pierwsze: [2, 2, 3, 3, 5, 5, 7, 7]
# Czas w sekundach: 0.000015
# Sprawdzone dzielniki: 6

rozklad(44103241230)
# Znaleziono czynniki pierwsze: [2, 3, 5, 97, 587, 25819]
# Czas w sekundach: 0.003861
# Sprawdzone dzielniki: 25818 

rozklad(372036854775807)
# Znaleziono czynniki pierwsze: [3, 3, 13, 3179802177571]
# Czas w sekundach: 2.584548
# Sprawdzone dzielniki: 19288255

rozklad(13372036854775807)
# Znaleziono czynniki pierwsze: [13, 19, 271, 439, 5849, 77801]
# Czas w sekundach: 0.007574
# Sprawdzone dzielniki: 77800

rozklad(413372036854775807)
# Znaleziono czynniki pierwsze: [1051, 15263, 25769053939]
# Czas w sekundach: 87.726839
# Sprawdzone dzielniki: 642940149

Czas wykonywania obliczeń dla liczb, które mają duże czynniki pierwsze, wyniósł prawie 1,5 minuty. Sprawdzanie kolejnych liczb dopóki, dopóty znaleziony zostanie pierwiastek, nie jest najefektywniejszym możliwym sposobem. Jedną z lepszych metod przedstawimy poniżej.

Drugi sposób rozkładu liczby na czynniki pierwsze

Dla każdej liczby Q możemy określić wszystkie jej dzielniki, sprawdzając jej podzielność przez kolejne liczby pierwsze, a więc 2, 3 oraz liczby postaci:

$p=6 \cdot k \pm 1$

gdzie:

$k=1, 2, ..., g$

$g=\sqrt{Q}$

Za pomocą zmiennej d będziemy w stanie sprawdzić wszystkie dzielniki w jednej pętli (najpierw obliczymy $6 \cdot k - 1$ , a następnie $6 \cdot k + 1$ i zwiększymy k).

Linia 1. def rozklad podkreślnik 2 otwórz nawias okrągły Q zamknij nawias okrągły dwukropek. Linia 2. from math import sqrt. Linia 3. from time import time. Linia 4. t0 znak równości time otwórz nawias okrągły zamknij nawias okrągły. Linia 6. kratka granice sprawdzanych dzielników. Linia 7. p znak równości 2. Linia 8. g znak równości int otwórz nawias okrągły sqrt otwórz nawias okrągły Q zamknij nawias okrągły zamknij nawias okrągły. Linia 10. kratka zmienne do wyliczania p znak równości 6 asterysk k plus prawy ukośnik minus 1. Linia 11. k znak równości 1. Linia 12. d znak równości minus 1. Linia 14. kratka licznik sprawdzonych dzielników. Linia 15. dzielniki znak równości 0. Linia 17. kratka tablica czynników pierwszych. Linia 18. tab znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 20. while p otwórz nawias ostrokątny znak równości g dwukropek. Linia 21. dzielniki plus znak równości 1. Linia 22. while Q procent p znak równości znak równości 0 dwukropek. Linia 23. tab kropka append otwórz nawias okrągły p zamknij nawias okrągły. Linia 24. Q prawy ukośnik prawy ukośnik znak równości p. Linia 25. if Q znak równości znak równości 1 dwukropek. Linia 26. break. Linia 27. if p otwórz nawias ostrokątny 3 dwukropek. Linia 28. p plus znak równości 1. Linia 29. else dwukropek. Linia 30. p znak równości 6 asterysk k plus d. Linia 31. if d znak równości znak równości 1 dwukropek. Linia 32. d znak równości minus 1. Linia 33. k plus znak równości 1. Linia 34. else dwukropek. Linia 35. d znak równości 1. Linia 37. if Q zamknij nawias ostrokątny 1 dwukropek. Linia 38. tab kropka append otwórz nawias okrągły Q zamknij nawias okrągły. Linia 40. t1 znak równości time otwórz nawias okrągły zamknij nawias okrągły. Linia 41. print otwórz nawias okrągły f apostrof Znaleziono czynniki pierwsze dwukropek otwórz nawias klamrowy tab zamknij nawias klamrowy apostrof zamknij nawias okrągły. Linia 42. print otwórz nawias okrągły f apostrof Czas w sekundach dwukropek otwórz nawias klamrowy t1 minus t0 dwukropek kropka 6f zamknij nawias klamrowy apostrof zamknij nawias okrągły. Linia 43. print otwórz nawias okrągły f apostrof Sprawdzone dzielniki dwukropek otwórz nawias klamrowy dzielniki zamknij nawias klamrowy apostrof zamknij nawias okrągły.

def rozklad_2(Q):
	from math import sqrt
	from time import time
	t0 = time()

	# granice sprawdzanych dzielników
	p = 2
	g = int(sqrt(Q))

	# zmienne do wyliczania p = 6 * k +/- 1
	k = 1
	d = -1

	# licznik sprawdzonych dzielników
	dzielniki = 0

	# tablica czynników pierwszych
	tab = []

	while p <= g:
		dzielniki += 1
		while Q % p == 0:
			tab.append(p)
			Q //= p
		if Q == 1:
			break
		if p < 3:
			p += 1
		else:
			p = 6*k + d
			if d == 1:
				d = -1
				k += 1
			else:
				d = 1

	if Q > 1:
		tab.append(Q)
 
	t1 = time()
	print(f'Znaleziono czynniki pierwsze: {tab}')
	print(f'Czas w sekundach: {t1-t0:.6f}')
	print(f'Sprawdzone dzielniki: {dzielniki}')

rozklad_2(44100)
# Znaleziono czynniki pierwsze: [2, 2, 3, 3, 5, 5, 7, 7]
# Czas w sekundach: 0.000014
# Sprawdzone dzielniki: 4 

rozklad_2(44103241230)
# Znaleziono czynniki pierwsze: [2, 3, 5, 97, 587, 25819]
# Czas w sekundach: 0.003591
# Sprawdzone dzielniki: 8608

rozklad_2(372036854775807)
# Znaleziono czynniki pierwsze: [3, 3, 13, 3179802177571]
# Czas w sekundach: 1.642628
# Sprawdzone dzielniki: 6429420 

rozklad_2(13372036854775807)
# Znaleziono czynniki pierwsze: [13, 19, 271, 439, 5849, 77801]
# Czas w sekundach: 0.005434
# Sprawdzone dzielniki: 25935 

rozklad_2(413372036854775807)
# Znaleziono czynniki pierwsze: [1051, 15263, 25769053939]
# Czas w sekundach: 58.880058
# Sprawdzone dzielniki: 214313384

Jak widać, druga wersja rozkładu liczby na czynniki pierwsze jest dużo szybsza. Dla największej z testowanych liczb pierwszych czas obliczeń był o ponad 30% krótszy w stosunku do pierwszego sposobu. Sprawdzono również niemal trzy razy mniej dzielników.

Dla zainteresowanych

Algorytm szyfrowania RSA bazuje na wyniku mnożenia dwóch dużych liczb pierwszych. Aby go złamać, trzeba znaleźć dla danej liczby Q takie dwie różne liczby e oraz t, których iloczyn wynosi właśnie Q. Będzie wówczas można nazwać t oraz e faktorami liczby Q.

Przykładowo:

$4 295 229 443 = 65 537 \cdot 65 539$

Słownik

faktoryzacja liczby Q

proces, w którym dla liczby $Q > 1$ odnajdujemy takie liczby naturalne $f_1, f_2, f_3...$ , różne od $1$ oraz różne od $Q$ (nietrywialne czynniki rozkładu), których iloczyn $f_1 * f_2 * f_3 * ... = Q$ ; liczby te nazywamy faktorami

Implementacja algorytmu

Strefa wyzwań

Porównanie sposobów rozkładu liczby na czynniki pierwsze

Drugi sposób rozkładu liczby na czynniki pierwsze

Słownik