Znam dokładną złożoność algorytmu faktoryzacji publikowanego na tym blogu z początku roku. Algorytm posługuje się konwersjami na kolejny system.
Jego złożoność tworzą dla liczby faktoryzowanej n:
Pętla sqrt n systemów;
konwersje wymagające (log n)^2 kroków wymagające operacji odejmowania i dodawania;
operacje działań na liczbach rzędu sqrt n .
Łącznie algorytm ma złożoność:
O( n log^2 n )
Dla porównania, najlepszy algorytm faktoryzacji podany u Knutha ma złożoność
O( e^{(1+epsilon) (log n)^{1/3} (log log n)^{2/3} )
