Mam już napisany program do faktoryzacji z rodziny rozwiązań odwracających działania. Nie wydaje się mi się bardzo szybki, ale to dlatego, że każę mu wypisywać w każdej iteracji drzewo możliwości, aby móc obserwować jego działanie. To wypisywane jest właśnie bardzo wolne.
Algorytm do działania potrzebuje listy początkowych liczb pierwszych primes = [3,5,7,...] oraz iloczynów początkowych liczb pierwszych product = [6,30,210,...] = [2*3, 2*3*5, 2*3*5*7, ...]. Liczba pierwsza 2 nie jest uzwględniona w tablicy primes, ale w product już tak.
Tablice te w razie potrzeby trzeba rozszerzać, choć dla testowanych przypadków kilkunastucyfrowych wystarczy naledwie kilka liczb pierwszych oraz ich iloczynów. Rozszrzerzanie tych tablic w razie potrzeby o kolejną liczbę pierwszą, jej iloczyn z pozostałymi, stanowi część funkcji.
Zasada iteracji jest następująca: na drzewie mam już odłożone iloczyny a*b mające tę samą resztę co product[i-1]. Pobieram jeden. Rozszerzenie do iloczynu product[i] o liczbę pierwszą p ma specyficzną budowę:
a = a+k*product[i-1], k=0..p-1
b = b+j*product[i-1], j=0..p-1
Jest ich p^2. Spośród nich wybieram te a*b, które mają tę samą resztę co liczba rozkładaną n modulo product[i], oraz nie mogą być zbyt duże. Te odkładam do drzewa (a,b,i), chyba, że iloczyn pokrywa sie z n, wtedy następuje koniec funkcji, zwrócenie wyniku n = a*b. W drzewie trzymam dodatkowo indeks i, będący zarazem poziomem drzewa. Przycinanie przepuszcza maksymalnie do p wartości, i to tylko na niższych poziomach. Inne wersje algorytmów tej rodziny mogą mieć mocniejsze przycinanie, kosztem poziomów. Po przekroczeniu pewnej wartości pojawia się bardzo mało nowych węzłów wstawianych do drzewa.
Inicjacja, gdy n modulo 6 jest 1, odkładam dwie pary (1,1, indeks 1), (5,5, 1), gdy n modulo 6 jest 5 odkładam (1,5, 1).
Dla liczb kilkunastocyfrowych poziom drzewa nie przekracza 10, a kiedy pisałem ten post, zanim zapisałem pierwsze dwa akapity, już uzyskałem rozkład:
9198491200007 = 197 * 109 * 428374759
poziom drzewa czyli długość tablic pomocniczych nie przekraczał 8.
Podstawowa trudność spowalaniająca przy odkładaniu a*b była tą, że te same obliczenia były wykonywane także dla równoważnej pary b*a. Niepotrzebnie. Po wyłapaniu tych przypadków program zyskał zauważalnie na szybkości. Oraz osobno sprawdzam podzielność przez 2, 3.
Program lepiej działa dla większych wartości. Liczby gładkie mają zbyt dużo równoważnych iloczynów, co powoduje mocny rozrost drzewa. Z kolei liczby pierwsze i półpierwsze są rozpoznawane znacznie szybciej.
Nie wiem dlaczego, ale intuicja podpowiada mi, że dopasowywanie par (a,b,) warto zacząć od większych wartości, a zmniejszać w kierunku wartości z poprzedniej iteracji odejmując product[i]. Elementy product[] mają wzrost wykładniczy,
Odwracanie systemów o podstawach będących liczbami złożonymi, jak np. dziesiątkowego, mają zawsze tendencję do powolnego rozrostu drzewa wydającego się wykładniczym. Jednak ten wzrost wykładniczy jest dla podstawy systemu, czyli nie przekracza m^(log _m n) = n, dla binarnego 2^(lg n), gdzie lg oznacza logarytm binarny liczby. Najmocniejsze przycinanie będące porównaniem reszt po konwersji do wielokrotności podstawy praktycznie blokuje rozrost wykładniczy w wielu przypadkach, zostaje kilka ścieżek prowadzących do różnych czynników. Z tego powodu ośmielam się nazywać tę rodzinę algorytmów wielomianowymi.
Praktycznie, kiedy ktoś mi podsuwa klucz publiczny RSA, jeżeli ostatnią 'cyfrą' jest 0xF, to nie ma innych możliwości modulo 8 niż iloczyny 0x3*0x5 albo 0x1*0x7.
