W rodzinie faktoryzacji zwiazanych z rozwinięciem liczby N w szereg odkryłem sposób, który ma bardzo specyficzne wartości, i jest łatwy do wyznaczenia złożoności.
Niech p[k] oznacza k-tą liczbę pierwszą. Współczynniki rozwinięcia w szereg są iloczynami początkowych kolejnych liczb pierwszych oraz
2*3*5*...*p[k] <= N < 2*3*5*...*p[k]*p[k+1] .
Rozwinięcie w szereg polega na odejmowaniu kolejnych w[k] wielokrotności iloczynów początkowych liczb pierwszych, z których każdy kolejny powstaje przez mnożenie przez coraz mniej wartości, kolejne iloczyny powstają przy zmniejszaniu się k, przedostatni byłby 2*3=6, ostatni przez 2.
Każdy taki iloczyn zabiera jak największą wartość nieujemną z N generując współczynniki w[i], i<k. Wtedy N miałoby przedstawienie:
N = 2*...*p[k]*w[k] + 2*...*p[k-1]*w[k-1] + ... + 2*3*w[2] + 2*w[1] ,
tylko - możemy zacząć od liczby pierwszej d=p[k+1], sprawdzamy, który z iloczynów 2*...*p[i] > d, oraz pozostałe łączymy w jedną wartość r zapisaną w systemie o podstawie p[k+1]. Iloczyn 2*...*p[i] podobnie zapisujemy w systemie o podstawie d=p[k+1], a pozostałe -- wystarczą tylko współczynniki w[i], ..., w[k] wyznaczane w tej kolejności. Wartości te będziemy wyliczali po drodze, każdy mnożony przez małą liczbę pierwszą p[k-j] dla j=k-i+1 malejące do 0.
Szereg ma tę własność, że jeśli modyfikowane d będzie liczbą p[i]-gładką, to począwszy od wyrazu i+1 uzyskamy 0, które będzie sie propagowało w kierunku w[k]. Podzielność przez początkowe liczby pierwsze sprawdzimy np. bezpośrednio licząc największy wspólny dzielnik iloczynu 2*...*p[k] z N.
Zatem pamiętamy: współczynniki w[k],...,w[i] rozwinięcia w szereg z przypisanymi im liczbami pierwszymi, liczby p[i] oraz r, zapisane w systemie o podstawie d, samo d.
Szukamy wartości d, dla której szereg przystaje do 0 modulo p. Zaś wszystkie współczynniki są małymi liczbami, i tylko p[i] oraz r są większe. Aby znaleźć wartość reszty N modulo d, reszta z dzielenia przez 2*...*p[i] jest dana jawnie, zaś by uzyskać resztę z dzielenia przez 2*...*p[i]*p[i+1] mnożymy ją przez p[i+1] modulo d. Kontynujemy aż do p[k]. Wyznaczone reszty w kombinacji liniowej z w[j] liczone modulo d dają resztę N%d.
Jeśli iloczyn 2*...*p[i] = 1*d+1, na końcu iteracji przemieszczamy go do reszty r = r+w[i]*(d+1), oraz zaczynamy z wcześniejszym iloczynem w[i+1]*(2*...*p[i]*p[i+1]) = w[i+1]*(p[i+1]*d + p[i+1]) pamiętając od teraz tę wartość.
Przebieg iteracji: zwiększamy d+2, konwersje p[i] oraz r postaci
a*(d-2)+b = a*d+(b-2a)
z możliwym przeniesieniem a*d+b = (a-1)*d+(a+b), wyznaczamy współczynniki u[j]=2*...*p[j] modulo d, obliczamy kombinację liniową sum w[j]*u[j], k>=j>=i i przyrównujemy ją do 0. wszystko na liczbach rzadko nieco większych niż d, czyli złożoności maksymalnej obliczeń O(log n).
Wyrazów nie jest zbyt dużo. Dla RSA 200 okazało się, że wystarczy mniej niż 95 kolejnych liczb pierwszych, które powoli przemieszczają sie do r, czyli jakieś O(log log n) dla wyznaczenia wartości kombinacji liniowej. Tłumienie wartosci w r jest szybkie - staje się stałą wartością mniejszą od d.
Jeśli zauważymy, że musimy z d dla liczby N pierwszej dotrzeć do pierwiastka kwadratowego sqrt N, nasuwa się złozoność wykładnicza. Policzymy inaczej, kryterium stopu nie jest tutaj widoczne, powstaje, gdy suma szeregu rozbieżnego o wyrazie 4*d+4 staje sie większa niż N. Takich sumowań jest mniej niż N, zaś jeśli N ma dzielniki (wszystkie większe niż p[i]), krotność iteracji jest zmniejszonym o p[i+1] rzędem najmniejszego z dzielników właściwych w grupie addytywnej, zatem O(n). Podobnie jest w teście pierwszości AKS, gdzie w analogicznej grupie muliplikatywnej (małe twierdzenie Fermata) można czasem otrzymać rząd dzielnika równy N, tu nawet nie docieramy to tej wartości.
Łącznie szacuję złożoność na O(n * log n * log log n). Wielomianowe.
Lecz algorytm jest jednym z wolniejszych, mimo że ma automatyczne ograniczenie stosowanych wielkości. Niewidoczne jest kryterium stopu. Propagowanie reszt powoduje, że niejako 'przy okazji' rozpoznajemy część wartości d jako złożonych, przy których kombinacja liniowa i tak nie będzie zerem choćby ze względu na dodatnie r.
Inną ciekawostką jest bardzo mało 'pamiętania', współczynniki w[] są wielkości liczb pierwszych, tylko dwie 'większe' wartości 'dwucyfrowe', z których używamy 'cyfr jedności' oraz podstawa systemu odpowiadająca dziesiątce d może osiągać wartość sqrt N -- wtedy lepiej jest stosować inny algorytm tej rodziny. Uzyska mniejszą złożoność dla tego zakresu.
Praktyczny zapis szeregu od d=3:
7387= 3*[210*11] + 2*[30*7] + 1*[6*5] + 1*[2*3] + 1
