Ze wzorów skróconego mnożenia uzyskamy kolejny algorytm faktoryzacji. Cechuje się małymi wartościami roboczymi oraz brakiem mnożenia, dzielenia, Wykorzystuje za to dwukrotnie pierwiastkowanie całkowito-liczbowe.
Znany jest wzór dla n=p*q:
(p+q)^2 - (p-q)^2 = 4pq = 4n
Jeśli n jest nieparzyste, każdy składnik tego wzoru jest podzielny przez 4. Zatem istnieją takie a, b, że
a^2 - b^2 = n .
Odwracamy to rozumowanie: bierzemy różnicę kwadratów aproksymujących n z niedomiarem. Dodajemy po obu stronach różnicę do kolejnego kwadratu (tego mniejszego). Wartość ta zmniejsza niedomiar, a jak zamieni na nadmiar, łatwo policzyć kolejną wartość kwadratu.
Potrzebne sa: pierwiastek a, niedomiar r, pierwiastek b i niezmiennik
a^2 - r - b^2 =n
Zaczynamy pierwiastkując 4n dla uzyskania a (nadmiarowe), zaś resztę po drobnym dopasowaniu (połowienie dla możności wzięcia czwartej części) pierwiastkujemy ponownie dla uzyskania b i niedomiaru r.
Kiedy znajdziemy n jako różnicę pełnych kwadratów, dzielniki p, q liczymy z układu równań:
p + q = 2a
p - q = 2b
Pomijając rozwiązanie tego układu równań, Nie mamy więcej niż (p+q)+(p-q) = 2p modyfikacji polegających na dodaniu 2a+1, 2b+1 oraz równocześnie odpowiednio a++, b++. Wartość ta jest zmniejszana pierwiastkowaniami inicjującymi,
Złożoność nie przekracza O(P log n) gdzie stała P zależy od większego z dzielników n, złożoność arytmetyczna O(n).
Przykład: n=8934053, 2a = ceil sqrt(4n) > 5977, b policzymy po modyfikacji.
Mamy własność: suma dzielników nieparzystych jest parzysta podzielna przez 2, niepodzielna przez 4. Zatem jeszcze modyfikujemy a=(a+3)/2 uzyskując
a^2 - r - b^2 = 2990^2 - 118 - 77^2 = n
Następny kwadrat dla b to 78, większy o 2*77+1 = 155. Dodając tę wartość do niedomiaru 118 uzyskamy nadmiar 37, by uzyskać znów niedomiar dodajemy 2*2990+1 = 5981. Nowy niedomiar dla a=2991 to 5944.
2991^2 - 5944 - 78^2 = n
Postępując dalej w ten sposób uzyskamy a=4653, b=3566, z których jedno jest sumą połowy dzielników, drugie różnicą.
Wystąpiło (4653-2990)+(3566-77) = 5152 iteracji w porównaniu z 543 dzieleniami. Ale różnica między dzielnikami mająca wpływ na szybkość przekracza 7000.
Brak komentarzy:
Prześlij komentarz