Ostatni algorytm faktoryzacji, jeszcze raz z przykładem i złożonością

-->

Opiszę jeszcze raz dokładnie ostatni algorytm faktoryzacji, z próbą policzenia złożoności. 

-->

Nieparzystą liczbę rozkładaną n spełniającą warunek 2²ⁱ < n <2²ⁱ⁺¹ dla pewnego i zapisujemy jako iloczyn dwu wartości n = a*b+c, gdzie a²=(2ⁱ)² < n, c<a.

Szukamy z założenia dzielników nieparzystych wykorzystując konwersję do podstawy parzystej o 2 większą, eliminując dzielnik 2 na początku algorytmu. Liczby złożone n mające dzielniki z przedziału (2ⁱ, 2ⁱ⁺¹) mają następującą postać:

a*b+a = a*(b+1)

dla podstaw p=b+1 parzystych. Mamy 2^i-1 przypadków złożoności konwersji zmiany systemu o 2.

Przygotowanie do faktoryzacji to przekształcenie liczby n w trójkę [a,b,c], w której a=2ⁱ jest największe możliwe, b jest częścią całkowitą n/a oraz c jest resztą z dzielenia n/a.

Jeden z procesorów konwertuje liczbę n na systemy o coraz większych podstawach, oraz przesyła postać [a, b, c] drugiemu procesorowi. Drugi dokonuje konwersji na systemy o coraz mniejszych podstawach.

Konwersja liczby n = [a,b,c], gdzie n = a*b+c na system o 2 większy. Praktycznie cyfra setek oraz cyfra dziesiątek są złączone w jedną liczbę dla zastosowania tożsamości

[a, b, c] = [a+2, b-e, c-2b+e(a+2)]

oraz a:=a+2; b:=b+e; c:=c-2b+e(a+2). Wartość e jest dobierana empirycznie w taki sposób, by c-2b+e(a+2) miała wartość dodatnią nie większą niż a+2. Złożoność konwersji zwiększania systemu o 2.

a = a+2, złożoność bitowa i = O(log n), gdyż a ma długość i oraz i=log n;

c = c+[(a+2)]^*-b-b, dwa odejmowania oraz do 6 dodawań, złożoność nie przekracza 6*log n, zwiększanie e jest w czasie stałym bitowo; dochodzą porównania możliwości odjęcia przy zachowaniu znaku, wykonywane w czasie liniowym bitowo, razem O(log n);

b = b-e, jedno odejmowanie małej liczby zawierającej co najwyżej 3 bity, prawie stałe;

a==c, porównania wykonywane w czasie liniowym O(log n).

Podsumowując, konwersja wykonywana jest O( log n * 2^{-1+log n}) = O(n log n) bitowo.

Konwersja liczby n = [a, b, c] gdzie n = a*b+c na system dwukrotnie mniejszy. Postać liczby a = 2^kd, gdzie 2 i d są względnie pierwsze.

[2*a, b, c] = [a, 2*b + f, c-f*a] .

Współczynnik sterujący f przyjmuje wartość 1, kiedy c>a, w przeciwnym przypadku 0. Procedurę kontynuujemy, dopóki a będzie parzyste. Krotność pętli jest równa k < i = log n.

Wyliczona wartość c jest porównywana z zerem, gdyż wtedy a oraz b są dzielnikami. Mamy do czynienia z dużą licznością przypadków, ale istnieje ograniczenie, gdyż szereg 1 + ½ + ¼ + ... +2^-i jest zbieżny do 2. Współczynniki szeregu wskazują liczność przypadków z k=1, k=2, ..., k=i odpowiednio dla wszystkich pobranych argumentów przedziału [2ⁱ, 2ⁱ⁺¹).

Złożoność konwersji podwajania podstawy.

a = a/2, przesunięcie bitowe liczby mniejszej niż pierwiastek z n, O(log n)

b = 2b + f, przesuniecie bitowe liczby zwiększanej do n, z ewentualnym dodaniem 1, O(n)

c = c-f*a, przy ustawionej fladze odejmowanie O(log n), w przeciwnym razie O(1).

Podsumowując, konwersja ta wykonywana jest k razy dla danych wejściowych, liczność z wykorzystaniem pierwszej z konwersji sumuje się do O( n 2^i-1 ) * O( 2*2^i-1*n ) = O( n² log n * 2^i-1*2*2^i-1 ) = O( n² log n 2^2i-1 ) = O(n² (log n)³ ) = O( 2^{2log n} (log n)³ ) .

Przykład n = 8934053, rozkład całkowity

Początek każdej linii: wyrażenie powstałe z konwersji z systemu o 2 większej, po ‘=’ konwersje z połowioną podstawą.

Inicjacja (znajdowanie najmniejszej potęgi 2ⁱ większej niż pierwiastek):

1*8934053+0 = 2*4467026+1 = 4*2233513+1 = 8*1116756+5 = 16*558378+5 = 32*279189+5 = 64*139594+37 = 128*69797+37 = 256*34898+165 = 512*17449+165 = 1024*8724+677 = 2048*4362+677

2048*4362+677 Start algorytmu

2050*4358+153 = 1025*8716+153

2052*4353+1697 = 1026*8707+671 = 513*17415+158

2054*4349+1207 = 1027*8699+180

2056*4345+733 = 1028*8690+733 = 514*17381+219 = 257*34762+219

2058*4341+275 = 1029*8682+275

2060*4336+1893 = 1030*8673+863 = 515*17347+348

2062*4332+1469 = 1031*8665+438

2064*4328+1061 = 1032*8657+29 = 516*17314+29 = 258*34628+29 = 129*69256+29

2066*4324+669 = 1033*8648+669

2068*4320+293 = 1034*8640+293 = 517*17280+293

2070*4315+2003 = 1035*8631+968

2072*4311+1661 = 1036*8623+625 = 518*17247+107 = 259*34494+107

2074*4307+1335 = 1037*8615+298

2076*4303+1025 = 1038*8606+1025 = 519*17213+506

2078*4299+731 = 1039*8598+731

2080*4295+453 = 1040*8590+453 = 520*17180+453 = 260*34361+193 = 130*68723+63 = 65*137446+63

2082*4291+191 = 1041*8582+191

2084*4286+2029 = 1042*8573+987 = 521*17157+466

2086*4282+1801 = 1043*8565+758

2088*4278+1589 = 1044*8557+545 = 522*17115+23 = 261*34230+23

2090*4274+1393 = 1045*8549+348

2092*4270+1213 = 1046*8541+167 = 523*17082+167

2094*4266+1049 = 1047*8533+2

2096*4262+901 = 1048*8524+901 = 524*17049+377 = 262*34099+115 = 131*68198+115

2098*4258+769 = 1049*8516+769

2100*4254+653 = 1050*8508+653 = 525*17017+128

2102*4250+553 = 1051*8500+553

2104*4246+469 = 1052*8492+469 = 526*16984+469 = 263*33969+206

2106*4242+401 = 1053*8484+401

2108*4238+349 = 1054*8476+349 = 527*16952+349

2110*4234+313 = 1055*8468+313

2112*4230+293 = 1056*8460+293 = 528*16920+293 = 264*33841+29 = 132*67682+29 = 66*135364+29 = 33*270728+29

2114*4226+289 = 1057*8452+289

2116*4222+301 = 1058*8444+301 = 529*16888+301

2118*4218+329 = 1059*8436+329

2120*4214+373 = 1060*8428+373 = 530*16856+373 = 265*33713+108

2122*4210+433 = 1061*8420+433

2124*4206+509 = 1062*8412+509 = 531*16824+509

2126*4202+601 = 1063*8404+601

2128*4198+709 = 1064*8396+709 = 532*16793+177 = 266*33586+177 = 133*67173+44

2130*4194+833 = 1065*8388+833

2132*4190+973 = 1066*8380+973 = 533*16761+440

2134*4186+1129 = 1067*8373+62

2136*4182+1301 = 1068*8365+233 = 534*16730+233 = 267*33460+233

2138*4178+1489 = 1069*8357+420

2140*4174+1693 = 1070*8349+623 = 535*16699+88

2142*4170+1913 = 1071*8341+842

2144*4167+5 = 1072*8334+5 = 536*16668+5

2146*4163+255 = 1073*8326+255

2148*4159+521 = 1074*8318+521 = 537*16636+521

2150*4155+803 = 1075*8310+803

2152*4151+1101 = 1076*8303+25 = 538*16606+25 = 269*33212+25

2154*4147+1415 = 1077*8294+338

2156*4143+1745 = 1078*8287+667 = 539*16575+128

2158*4139+2091 = 1079*8279+1012

2160*4136+293 = 1080*8272+293 = 540*16544+293 = 270*33089+23 = 135*66178+23

2162*4132+669 = 1081*8264+669

2164*4128+1061 = 1082*8256+1061 = 541*16513+520

2166*4124+1469 = 1083*8249+386

2168*4120+1893 = 1084*8241+809 = 542*16483+267 = 271*32966+267

2170*4117+163 = 1085*8234+163

2172*4113+617 = 1086*8226+617 = 543*16452+617

2174*4109+1087 = 1087*8219+0 

Dzielniki 8934053 = 1087*8219

Modyfikacje:

Najgorsze dla złożoności jest sprawdzanie przypadków dzielników mniejszych niż 2ⁱ. Dużo można zdziałać modyfikując ten fragment. Można to zrobić przez eliminację złożoności, kosztem utraty znajomości drugiego z dzielników, lub zmniejszając krotność przypadków do sprawdzenia.

1) mniejsza złożoność.

Nie musimy znać kolejnego dzielnika, gdyż znajdziemy go później dzieląc n przez znaleziony. Dlatego dla drugiego procesora nie przysyłamy trójki [a, b, c], ale parę [a, c]. Wewnątrz znika nam warunek mnożenia 2 przez b złożoności bitowej O(n) zastąpiony operacjami złożoności bitowej O( log n). Łącznie uzyskujemy złożoność bitową

O( n log n * (log n)³ ) = O( n (log n)⁴ ).

2) wielokrotność reszty daleko od dzielnika.

Aby uzyskać przypadek, że dla danego a uzyskamy c-a=0, wartości c zbyt małe lub zbyt duże będą skutkowały niepotrzebnym sprawdzaniem. Aby go chociaż częściowo eliminować, do procesora drugiego dołączamy informację o k, czyli czwórkę [a, b, c, k],

Kiedy mamy połowić podstawę systemu a=2^kd przy odpowiednio małej wartości c, sprawdzamy, czy a > 2^kc. Jeśli tak, pętlę można opuścić, c nie będzie na tyle duże, aby wskazać dzielnik.

Podobna sytuacja jest dla c=a-1. Tu w każdej iteracji c będzie malało, lecz za mało, by wskazać dzielnik.

3) szybkie wskazanie małych dzielników.

Podejście 2) potrafi zmniejszyć liczność rozpatrywanych przypadków. Lecz małe dzielniki można wykryć jeszcze szybciej, obliczając nwd(a,c) spośród wartości [a, b, c] przesyłanych do procesora drugiego. Algorytm ten mocno pogarsza złożoność, i działa dobrze zwłaszcza przy istnieniu małych dzielników. Czasem policzenie nwd(b,c) wskaże dzielnik jeszcze szybciej, lecz z uwagi na duże wartości nie jest zalecany.

4) wiele procesorów

Dotychczas rozważane było użycie dwu procesorów. Nic nie stoi na przeszkodzie, by przedział [2ⁱ, 2ⁱ⁺¹) podzielić na kilka przedziałów oraz rachować w każdym z nich niezależnie. Wystarczy odpowiednio wcześnie podczas przygotowania wyznaczyć podstawy dla granic przedziałów.

Algorytm faktoryzacji, jak on działa?

Kiedy nie wiadomo co robić, zaczynam szukać innych form, to było granie w gry na sucho, w edytorze tekstu. Gdyż myślałem, że z teorii liczb nic już nie wycisnę. Myliłem się.

Powstał nowy algorytm. Jest bardzo dobry na maszyny wieloprocesorowe, ma stosunkowo mało przypadków do sprawdzenia, i do końca nie wiem jak działa.

Ustalmy 3 procesory. Pierwszy delikatnie przekształca liczbę faktoryzowaną n zapisaną w postaci trójki
n = a*b+c ,
przy czym a rośnie od parzystej liczby ograniczajacej pierwiastek z n z góry do podwojonej tej wartości po liczbach parzystych. Ma zatem 2^i przypadków, gdzie 2^(2i) < n < 2^(2i+1).
Przekształcenie polega na konwersji na system o 2 wyższy, czyli dany tożsamościami:
a*b+c = (a+2)*d+e, gdzie d in {b-2, b-1, b} w zależności od znaku (c-2b).
Dokładniej:
a*b+c = (a+2)*b + (c-2b), -1 < c-2b;
a*b+c = (a+2)*(b-1) + (c-2b+a+2), -a-3 < c-2b <0;
a*b+c = (a+2)*(b-2) + (c-2b+2(a+2)), c-2b < -a-2.
Np. jeśli n jest postaci n = 12441^2+987, to a=12442, b=12440, c=987-12441+12442 = 988; następna wartość jest równa a=12444, zaś b i c są znajdowane według wzoru (tu jest b=12438).
Dla n postaci n=12442^2+c przyjmujemy a=12444, pozostałe są odpowiednio dopasowane, by b było bliskie a, zaś c jest resztą.
Wartości (a,b,c) są przekazywane drugiemu procesorowi.

Drugi z procesorów przyjmujący (a,b,c), gdzie a jest parzyste, usiłuje dokonać konwersji, w której a jest połowione, b jest podwajane, zaś c w zależności od znaku (c<a) jest albo pozostawiane, albo zmniejszane o a, z równoczesnym zwiększeniem b o 1. Wzorami
(2a)*b+c = a*(2b)+c, c<a;
(2a)*b+c = a*(2b+1)+(c-a), c>a-1.
Pętlę kończymy, gdy wartość zmniejszana a jest nieparzysta. Mamy do czynienia co najwyżej z logarytmem binarnym z a przypadków (b jest nie większe niż podwojony sufit pierwiastka kwadratowego z n). Ciąg wartości c jest ciągiem nierosnącym.
Watości (a,c) oraz (b,c) są przesyłane do trzeciego z procesorów. Jedna z tych wartości jest stosunkowo mała.

Trzeci procesor ma najwięcej roboty. Sprawdza największy wspólny dzielnik przesłanych wartości, jeśli jest on większy od 1, znaleziona wartość jest zarazem dzielnikiem liczby n.
Bardzo podobnie wygląda cecha podzielności przez 9 lub 11, która stała się prekursorem algorytmu. Jeśli cyfry liczby dwucyfrowej zapisanej w systemie niedziesiątkowej są równe, to podstawa systemu zwiększona o 1 jest dzielnikiem liczby.

W praktyce nie zawsze musimy przesyłać dane do trzeciego procesora. Ale musimy je przesłać, gdy następuje zmiana wartości c, które nie jest zbyt małe. Przy c=1 możemy zignorować ten krok, przy c pierwszych przyspieszyć sprawdzanie testując podzielność przez c.

Przykładowy fragment rozkładu znajdujący dzielnik: 
n = a*b+c = (2990 * 2987 + 2923) = 8934053
Procesor pierwszy: przelicza od a=2990 do a=5980:
(2990 , 2987 , 2923 ) = (2992 , 2985 , 2933) = ...
= (4348 , 2054 , 3261) = ... 
Procesor drugi (4348, 2054, 3261):
(4348 , 2054 , 3261) = (2174 , 4109 , 1087) = (1087 , 8219 , 0)
Procesor trzeci:
nwd(4348, 3261) = 1;
nwd(2054, 3261) = 1;
nwd(2174, 1087) = 1087, znaleziony dzielnik 1087
Zaś 8934053 = 1087 * 8219.

Pętla działania procesora drugiego tworzy 'grzebień'. Tzn. dla połowy przypadków jest jedna iteracja, każda dłuższa pętla sąsiaduje z dwoma najkrótszymi. Krotność iteracji tworzy podciągi (1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, ... ).

Algorytm powstał, kiedy połączyłem cechy podzielności przez liczby sąsiadujące z podstawą systemu, konwersje o potęgi dwójki oraz konwersje o 2.