Faktorizacija - Metoda verižnog razlomka

[Prethodno poglavlje] [Sljedeće poglavlje] [Sadržaj]

4.6. Metoda verižnog razlomka

Neka je α₀ realan broj. Njegov verižni razlomak se definira na sljedeći način. Za i = 0, 1, 2, ... , neka je a_i = ⌊α_i⌋, te α_i = a_i + 1/α_i+1. Ako je a_n = α_n za neki n, onda se postupak završava. Može se pokazati da će se to dogoditi ako i samo ako je α₀ racionalan. Pišemo:

a0+1/a1+...

ili jednostavnije α₀ = [a₀, a₁, a₂, ...].
Razlomak

p_n/q_n

zovemo i-ta konvergenta od α₀. Vrijedi:

p_n = a_n p_{n -1} + p_{n -2}, p₀ = a₀, p₁ = a₀a₁ + 1;
q_n = a_n q_{n -1} + q_{n -2}, q₀ = 1, q₁ = a₁.

U slučaju kada je α₀ = √n, gdje je n prirodan broj koji nije potpun kvadrat, poznato je da je njegov raznoj u verižni razlomak periodičan. Preciznije

n^(1/2)

i vrijedi a_i = a_{r -i} za i = 1, ... , r - 1. Npr. √7 = [2, 1, 1, 1, 4].

U tom slučaju, razvoj u verižni razlomak može se dobiti primjenom sljedećeg algoritma:

a₀ = ⌊√n⌋, s₀ = 0, t₀ = 1,
s_i+1 = a_i t_i - s_i, t_i+1 = (n - s_i+1²)/t_i, a_i = ⌊(a₀ + s_i)/t_i⌋ za i ≥ 0.

Uz ove oznake, vrijedi:

p_i² - n q_i² = (-1)ⁱ⁺¹ t_i+1 (4.4)

za i ≥ 0, te također s_i < √n, t_i < 2√n.

Metodu faktorizacije pomoću verižnih razlomaka uveli su Lehmer i Powers, a usavršili Brillhart i Morrison.

Uvedimo oznaku t_i* = (-1)ⁱ t_i. Pretpostavimo da smo pronašli produkt t^*_k₁+1 t^*_k₂+1 · · · t^*_{k_m+1} koji je potpun kvadrat, recimo jednak z². Tada iz (4.4) slijedi

p²_k₁ p²_k₂ · · · p²_{k_m} ≡ z² (mod n). (4.5)

Naravno, u (4.5) možemo svaki p_{k_i} zamijeniti s (p_{k_i} mod n) ili s njegovim najmanjim ostatkom po apsolutnoj vrijednosti.
Promotrimo brojeve (p_k₁ · · · p_{k_m} - z, n) i (p_k₁ · · · p_{k_m} + z, n). To su sigurno faktori od n. Ukoliko je barem jedan od njih različit od n, naš je zadatak dovršen.

Primjer 4.6: Neka je n = 9073. Računamo:

i 0 1 2 3 4 5

s_i 0 95 49 90 92 82

t_i 1 48 139 7 87 27

a_i 95 3 1 26 2 6

p_i 95 286 381 1119 2619 16833

Očito je t₁* · t₅* = 36². Stoga je

p₀² p₄² = (95 · 2619)² ≡ 3834² ≡ 36² (mod 9073).

Računamo: (3834 + 36, 9073) = (3870, 9073) = 43. I zaista, 9073 = 43 · 211.

Jasno je da metodu verižnog razlomka možemo shvatiti kao specijalni slučaj metode faktorske baze. Ovdje u bazu B uzimamo broj -1, te sve proste brojeve koji se pojave u faktorizaciji t_i-ova. U ovom slučaju je b_i² mod n = p_i² mod n = t^*_{i +1} < 2√n.

Brillhart i Morrison su 1970. godine metodom verižnog razlomka faktorizirali Fermatov broj

2² + 1 = 59 649 589 127 497 217 ^. 5 704 689 200 685 129 054 721.

U stvari, oni su koristili jednu modifikaciju originalne metode. Naime, umjesto razvoja od √n, oni su koristili razvoj od √(λn) za prikladno odabrani prirodni broj λ. U konkretnom slučaju za n = 2² + 1, uzeli su λ = 257.

[Prethodno poglavlje] [Sljedeće poglavlje] [Sadržaj]

Web stranica kolegija Kriptografija

Andrej Dujella - osobna stranica

i	0	1	2	3	4	5
s_i	0	95	49	90	92	82
t_i	1	48	139	7	87	27
a_i	95	3	1	26	2	6
p_i	95	286	381	1119	2619	16833