23 sierpnia 2015

Sito liczb złożonych

Czasem pojawia się pomysł, jak zmniejszyć krotność przypadków faktoryzacji zachłannej. Pomysł ten często jest chybiony. Podobnie jak poniższy.

Nieparzyste dzielniki liczby N są jednej z postaci: 4p+1 oraz 4p+3.
Liczba N także, lecz w jej przypadku łatwo ją znajdziemy.
Wtedy możemy dopasować a, b w taki sposób, by N = a+4b, stąd b=(N-a)/4.
Wykorzystując cechy podzielności, N jest podzielna przez a wtedy i tylko wtedy, gdy N = a*(4b)+a w przypadku dzielnika postaci 4p+1 (b=p); lub N=a*(4b)-a w przypadku dzielnika 4p+3 (b=p+1).
Sugeruje to, że możemy badać pary (a,b), w których mamy nie połowę, ale czwartą część wartości mniejszych niż pierwiastek z N. Niestety, znajdujemy tylko dzielniki określonej postaci. Dzielnik występuje gdy a dzieli b.

Ostatecznie uzyskujemy następujący sposób rozkładu:
załóżmy, że  N = 4b+1
tworzymy ciągi a=1+4k, b=(N-1)/4-k dla k dodatnich. Inicjacja a=5, b=(N-5)/4.
Dla każdej wartości b przypisujemy zbiór jego dzielników {d}, początkowo pusty.
Przekształcamy: a=a+4, b=b-1. Korzystając ze zbioru dzielników {d} znajdujemy częściowy rozkład b na czynniki. W rozkładzie tym z b są wyłączone dzielniki nie większe niż a, mnożone przez wartość c. Wartość c jest 1, liczbą pierwszą lub iloczynem liczb pierwszych większych niż a. Gdy c =1, nie mamy dzielników, do zbiorów przypisanych wartościom b-d dodajemy dzielniki d.
Gdy c jest liczbą większą niż a, obliczamy resztę s z dzielenia c przez a. Pozwala nam ona znaleźć resztę r z dzielenia b przez a. Teraz do zbioru przypisanego wartości b-r dokładamy jego dzielnik a. Nie musimy się przejmować pominiętymi liczbami pierwszymi. Mogą się jeszcze pojawić, albo są w danej gałęzi nieistotne.
Kontynuujemy z kolejnymi k, uzyskując zbiór liczb, które na pewno nie są dzielnikami N.
Występujące dzielenia operują na mniejszych wartościach jak zwykłe dzielenie N przez a, co najmniej 4 razy w przypadku, gdy zarówno a, jak i b są pierwsze.
Kończymy, gdy wartość a przekroczy pierwiastek z N.

Niestety, nie wyłapane są wszystkie dzielniki, do reszty należy zmienić znak, oraz zmodyfikować a=3, teraz b zwiększamy zamiast zmniejszać (b+d), oraz w przypadku c większych od a do zbioru dzielników wartości (b-r+a) dołączamy a.

Dla N = 4b+3 wartości inicjujące a są odwrócone. Mamy 3 zamiast 5 i na odwrót. Chodzi o to, żeby po odjęciu a wartość była podzielna przez 4.

Skomplikowane, przykład może nieco rozjaśni.
Liczba 8934053
a=5; b=(8934053-5)/4 = 2233512. Rozkład częściowy b = 2^3*279189. Liczba c=279189, jej reszta z dzielenia przez 5 jest 4. Różna od 0, zatem 5 nie jest dzielnikiem. Liczbą pierwszą 3 się nie przejmujemy.  
Znajdujemy resztę z dzielenia b przez a: r = 4*8 = 2 (5).
Uzupełniamy tabele dzielników dla wartości: [b=2233512-2, {2}] = [2233510, {2}]. c>a, zatem [b=2233512-2, {a}] = [2233510, {2,5}]

W następnym kroku mamy a=5+4=9, b = c = 2233511, reszta r=s=8, czyli [b=2233511-8, {9}]  nie jest dzielnikiem N. Najgorszy przypadek z największymi wartościami.

Kolejny krok a=9+4=13, b=2233510 mamy zbiór dzielników {2,5}, czyli b = 2*5*223351. Nie mamy dzielników, ale korzystając z reszty r=6 modyfikujemy zbiory dla wartości [2233508, {2}], [2233505, {5}] i [2233504, {13}]

W tej części nie znajdziemy dzielników. Zajrzyjmy do drugiej:
a=3, b=2233514
Tu pojawia się czynnik 3.
Przeskoczmy nieco przypadków:
a=411, b=2233616 = 2^4*7^3*11*37 jest pełnym rozkładem, czyli c=1, wprowadzając wartości do zbiorów [2233618, {2}], [2233623, {7}], [2233627, {11}, [2233653, {37}] nie modyfikujemy zbioru dla wartości b=2233616-242+411 = 2233785 wartością {a=411}. Nie musimy mając już  wszystkie dzielniki.

Dzielnik pojawia się dla a=1087, b= (8934053+1087)/4 = 2233785 = 5*411*1087. jest on równy 1087.