Próba przyspieszenia znajdowania dzielników

Każdą liczbę naturalną można jednoznacznie przedstawić jako sumę uporządkowanego ciągu iloczynów współczynnika i potęgi podstawy systemu 

\sum_{k>0} a_k*p^k

(budowa systemu pozycyjnego, dla p=10 dziesiątkowego). 

Nic nie stoi na przeszkodzie, by potęgi podstawy systemu (p_k)_k zastąpić losowym, lecz uporządkowanym ciągiem liczb, np. kolejnych liczb pierwszych.

Wtedy liczbę naturalną N jednoznacznie przedstawiamy wyrażeniem, np.
127 = ((1*7+1)*5+2)*3+1
 za pomocą ciągów [1,1,2,1] oraz ciągu liczb pierwszych [7,5,3].
Rozpatrując to wyrażenie w ogólnej postaci, kiedy N jest liczbą złożoną, uzyskujemy dla liczb p i q pierwszych oraz szukanych współczynników a,b,c,d,e,f następującą postać:

N = ((ap+c)q+e) * ((bp+d)q+f) =

[[abpq + (ad+cb)q + (af+eb)]p + (cdq+(cf+ed))]q + ef 

Zauważmy, że w każdym bardziej zewnętrznym nawiasie prostokątnym potrzeba coraz mniej współczynnikow. Zatem znalezienie pary (e,f), z jej pomocą pary (c,d) oraz ostatecznie pary (a,b) wyznaczy nam ciągi zapisu dzielników N. 

Wyrażenie jest przedstawione jednoznacznie (własności działań po utożsamieniu wyrażeń przemiennych ab = ba).

Kiedy wylosujemy dowolną liczbę q, wyznaczamy parę (e,f). Wstawiamy 

n_1 = (N- ef)/q 

oraz kontynuujemy z mniejszą wartościa n_2 = n_1*p+(cdq+cf+ed) = n_1*p+w(), w której nieznane są tylko c i d. Z niej wyznaczamy parę (c,d) kongruencjami 

w() = (n mod p) modulo p. 

Wielomiany w() dla kolejnych poziomów modyfikują się w bardzo specyficzny sposób. Są to równania kongruencyjne nieliniowe dla największego indeksu k, kiedy to mamy iloczyn obu współczynników oraz wszystkich liczb pierwszych ciągu. Do tego składnika dodawane są liniowe fragmenty (a_k*b_i + a_i*b_k) mnożone przez iloczyn liczb pierwszych na pozycjach nie przekraczajacych i<k. Współczynniki a_i oraz b_i zostały już wyznaczone wcześniej. 

Jeśli liczba p jest pierwsza, znajdziemy p-1 par (c,d) takich, że c*d = n%p (mod p) dla kolejnych wartości c. Jedna z kongruencji jest w praktyce sprzeczna.

Przemienność może nam popsuć wybór, dlatego reszta z dzielenia przez pierwszą z ciągu liczb pierwszych nie powinna być kwadratem a^2. W przeciwnym przypadku mamy dwie możliwości: (a,a) oraz (-a,-a). Zapewni to jednoznaczność wyboru par (c,d) dla różnych c, z których w przypadku liczby złożonej dokładnie jedna staje się częścią ciągów dzielników N. 

W klasycznej metodzie dzielenia przez kolejne liczby mamy przeszukiwanie liczb pierwszych. Tutaj ten proces został przerzucony na znajdywanie rozwiązań równań kongruencyjnych, co odbywa się na stosunkowo małych liczbach - zależnych od wyboru q.
W ogólności tworzymy drzewo z krotnością gałęzi danego poziomu nie wiekszą niż wybrana liczba pierwsza. Drzewo to przyda się przycinać przez wybór odpowiedniej pary.

Aby zapobiec kłopotom z wyborem, warto uzywać liczb pierwszych jeszcze nie występujacych w ciągu. W przeciwnym przypadku kongruencje będą się upraszczać kosztem większych kłopotów z doborem pary. Tak działał jeden z wcześniejszych algorytmów faktoryzacji.

Zauważyłem pewne kryterium, działające dla początkowego wyboru par.
Wartość n modulo kwadrat wybranej liczby pierwszej jest najbliższe reszcie z dzielenia różnicy n-w() przez iloczyn początkowych liczb pierwszych ciagu  z niedomiarem, lecz to kryterium w pewnym momencie staje się fałszywe. Nie udaje mi się znaleźć lepszego, wszystie w pewnym momencie zaczynają wskazywać inne pary niż właściwa.

Przykład numeryczny N = 8934053.

Ciąg podstaw w kolejności od cyfr bardziej znaczących: [13, 11, 7, 5, 3].

Ponieważ N = 2 (mod 3), przyjmujemy A=[2], B=[1], czyli para (a,b) = (2,1).

Do dalszego przebiegu używamy n = (8934053-2*1)/3.

Pobieramy nową liczbę pierwszą q=5, modyfikujemy wielomian 

w() = 3ab+(a+2b) 

i szukamy kolejnych par w() = n%5 (mod 5). Wybieramy tę, która jest najlepsza, tu okazała się nią para (4,2). Wstawiamy wartości (a,b) = (4,2) wyznaczając wartość wielomianu w(), którą odejmujemy od n. Kontynuujemy.

Podsumowując cały rozkład.

Tablice dla dzielników są postaci: 

A = 8219 = [7, 1, 1, 4, 2]; 

B = 1087 = [0, 10, 2, 2, 1].

Ostatnia para (a,b) = (7,0) (zapisana jako pierwsze elementy w tablicach ciągów) jako jedyna wsród kandydatek byla równa n przez wstawienie do wielomianu tego poziomu

w() = 11*7*5*3ab + 105(10a+b) + 15(2a+b) + 3(2a+4b) + (a+2b)

Zakończyła ona proces znajdowania ciągów przez wyzerowanie n.

Liczby pierwsze nie wyzerują n, oraz dla kongruencji nie znajdziemy rozwiązań w małych liczbach naturalnych, ograniczonych liczbami pierwszymi.

Nie potrafię policzyć złożoności, czy proces jest szybszy niż standardowe dzielenia. Czy przycinanie drzew jest wystarczająco dobre.

Jest to po prostu kolejny sposób spojrzenia na faktoryzację.