To nie heurystyka, działa bardziej ogólnie korzystając z cech podzielności

Wspomniałem o szybkiej heurystyce rozkładu liczb. 

 

Liczbę szacuję za pomocą potęg 4, oraz zapisuję N jako parabolę o równaniu
a*p*p + b*p + c = N = q*r,

gdzie początkowo a jest jedną z trzech wartości power(4,k). 2*power(4,k), 3*power(4,k), a<p, Podstawa p też poczatkowo jest potęgą 4 bliską a, współczynniki b i c nieujemne są bliskie p, najlepiej z przedziału (-p, 3p).

 

Będziemy to modyfikować pilnując, by p było jak największe. Przy b i c stosunkowo niewielkich małe dzielniki mogą być niewykrywalne - iloraz dzielników r/q, r>q jest zbyt dużą wartośc ią, zaś algorytm czynimy zbieżnym do tego ilorazu. W tym przypadku należy sprawdzić, czy można doprowadzić do istnienia wspólnego dzielnika wszystkich współczynników.

 

Przekształcenie niezmiennicze dla wartości N przesuwa podstawę

[a, b, c, p] = [a, b-2k, c-2k*b+k*k*a, p+k]  (jak np. (1, 4, 4, 8] = [1, 0, 0, 10]

dla dowolnego k całkowitego. Dla tego przekształcenia c ze wzrostem p jest malejace, oraz szukamy jednej z dwu wartości, gdzie a+b+c  albo a-b+c sa całkowitymi wielokrotnościami p-1, p+1. Warto poszukać zmian znaku c dla jednego, lub niezależnie obu funkcji liniowych. Nie zwracają jednej wartości.

Kolejne przekształcenia niezmiennicze wartości N:

[a, b, c, p] = [a, b+1, c-p, p]  np. [5, 3, -1, 10] = [5, 2, 9, 10] = 529

[4a, 2b, c, p] = [a, b, c, 2p] np. [12, 2, 3, 10] = [3, 1, 3, 20]

płaszczę nieco parabolę przesuwając znalezioną wartość. Wymaga znów szukania miejsca, gdzie c ze zmianą p zmienia znak.

Kiedy spłaszczymy parabolę na tyle, że a+b+c=(p-1)*const, dzielnikiem liczby N jest p-1; Gdy a-b+c=0 + p*const, dzielnikiem N jest p+1. Przypomina to cechy podzielności przez 9 oraz 11 w dziesiątkowym - wszak to jest uogólnienie tych przypadków. 

Jęsli dopasujemy wartości a+b+c=p-1 oraz a-b+c=0 odległe dokładnie o 2, między nimi jest postać [a,b,0,p], skąd odczytujemy rozkład N = p * (a*p+b).

Teoretycznie jest to bardzo szybkie. Dla wyboru a oraz jednej funkcji mamy nie więcej niż 3*220 płaszczeń i wyszukiwań liniowych w przypadku RSA 200.

 

Przykładowo 259 zwraca swój dzielnik dla [4, 0, 3, 8] (suma 4+0+3=8-1=7, suma naprzemienna o wspólnym dzielniku [7, 35, 7, 4]).
Niektóre dzielniki można wychwycić dla dwu różnych wartości a - funkcje wykażą je od 'przeciwnych' stron, mniejszej albo większej.