Wspomniałem o szybkiej heurystyce rozkładu liczb.
Liczbę szacuję za
pomocą potęg 4. Oraz zapisuję N jako parabolę
a*p*p + b*p + c = N,
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 nie większe niż p.
Będziemy to modyfikować
pilnując, by p było jak największe, zaś b i c stosunkowo małe.
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. 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 oraz a-b+c=0 odległe 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łądowo 259 zwraca swój dzielnik dla [4, 0, 3, 8].
