Faktoryzacja metodą różnicy kwadratów

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.

Najkrótsze sieci a plaster miodu

Lev Kurlyandchik napisał książkę pt. Najkrótsze sieci. Są tam tematy, które poruszam na tym blogu, ułamki egipskie. Rozdział pierwszy jest poświęcony drzewom Steinera - w grafie szukamy połaczeń węzłów, by suma krawędzi była jak najmniejsza. W odróżnieniu od najkrótszego drzewa rozpinającego, do grafu tego można, a nawet czasem należy dołączać nowe węzły.
Autor pisze językiem matematyki skupiając się na szczególnych przypadkach, mam podejście nieco bardziej inżynieryjne. Jest opis 'gotowego' algorytmu, ale nie podchodzi mi on. Polega na połączeniu dwu wejściowych wierzchołków z nowo wyznaczanym wierzchołkiem w jeden 'wierzchołek' dla rekursji. Mamy wtedy graf o mniejszej liczności wierzchołków. Ale wyczuwam pewny kłopot związany z kolejnością wierzchołków grafu.
Widzę inne rozwiązanie.
Najpierw jednak powtórzę za autorem własności najkrótszej sieci:
- z każdego węzła wychodzą co najwyżej 3 krawędzie, zaś kąty między nimi wynoszą nie mniej niż 120 stopni;
- nie istnieje łamana zamknięta.

Przyjmując te własności za punkt wyjścia, istnieje zanurzenie grafu w plaster miodu mające podane własności. Plaster miodu jest parkietem sześciokątów foremnych, w którym suma przeciwległych krawędzi jest stała. Usuwając którąkolwiek dostajemy dobre przybleżenie drzewa Steinera. Zatem sposób konstrukcji byłby następujący (płaszczyzna Euklidesowa analitycznie):
- pierwsze dwa wierzchołki wejsciowe są połączone krawędzią równoległą do plastra miodu (np. pionową, w razie potrzeby wystarczy obrócić);
- pobieram wierzchołek, oraz prowadzę z niego do 6 półprostych w kierunkach plastra miodu;
- półproste przecinają najbliższe krawędzie grafu, szukam wierzchołków grafu wyznaczonych tymi krawędziami W, mogą być wejściowe (zbiór D) lub Steinera (wyznaczone łamanymi);
- z każdego wskazanego wierzchołka W prowadzę dwie łamane po krawędziach plastra do nowo przyłączanego wierzchołka D, wyznaczają one po dwa nowe wierzchołki Steinera S, część z nich może należeć do generowanego docelowo drzewa;
- po uwzględnieniu wszystkich wierzchołków wejściowych następuje druga faza
- eliminacja cykli - łamanych zamkniętych przez kasowanie najdłuższej pojedynczej krawędzi (suma długości krawędzi przeciwległych plastra miodu jest stała); czasem można skasować także pomocniczy wierzchołek S;
- warunek trzech wychodzących krawędzi nachylonych względem siebie o 120 stopni przesuwa niektóre wierzchołki S; modyfikacje są w obrębie 7 najbliższych plastrów, nie mają one wpływu na resztę grafu;
- finalizacja, jeśli dwa wierzchołki sa połączone łamaną z wierzchołkiem S, jest on kasowany, zaś łamana jest zastępowana krawędzią je łączącą.

Uzyskamy w ten sposób drzewo, które ma małą sumę długości krawędzi. Nie orientuję się do końca, czy jest to drzewo Steinera, ale jest mu bardzo bliskie.