Zmniejszenie krotności przypadków rozkładu dla bardzo dużych liczb

Ten pomysł nie jest najlepszy obliczeniowo, ale w pobliżu pierwiastka z liczby rzadko natrafia się na dzielniki. Znalazłem sposób zmniejszenia krotności przypadków, szacuję, że nawet do pierwiastka sześciennego z rozkładanej liczby. Ale koszt jest duży.
Stosując konwersję odwrotną dla liczby N=(a*p+b)*p+c, gdy p^2<N<(p+1)^2, a=1, b jest zerem lub jedynką, normalnie przenosiłem nadmiar z c do b.
Można tego zaniechać. Wtedy współczynniki dla kolejnych iteracji p-k są funkcjami rosnącymi, a właściwie szeregami
c[0] = N-(p+b)*p;
c[k+1] = b[k]+1 + c[k];
b[0] = 0 | 1; (zależy od liczby N)
b[k+1] = 2*k+b[0];

Dosyć szybko c[k]>p-k. Z dzielnikiem mamy do czynienia wtedy, gdy p-k dzieli c[k]. Wyrazy ciągu c[k] można łatwo wyznaczyć, interesują nas tylko te, kiedy c[k] ma resztę bliską p-k. 
Najciekawszy efekt jest wtedy, gdy zapisujemy c[k] w systemie o podstawie p-k.
Mamy wtedy przekształcenia kroku iteracji k:
dec p;
konwersja c[k] na system o podstawie 1 mniejszą;
c[k] + b[k]_p; (b[k]_p oznacza liczbę b[k] w systemie o podstawie p)
sprawdzenie, czy cyfra jedności c[k] jest zerem.

Korzystając z monotoniczności c[k] można wyznaczyć sumę ciągu (b[i]+1)  tak, by wyznaczyć kolejną wartość przy występującym skoku cyfry jedności c[k], oraz wyznaczyć c[k], p. 

W pewnym momencie c[k] zaczyna być liczbą trzycyfrową. Wtedy lepiej zmienić algorytm. Gdyż kontynuacja spowoduje, że c[k] będzie się rozrastać do wielkości rzędu liczby N.

Przykładowo dla N=8934053 mamy jak niżej. Zapis [1,2]_7 oznacza liczbę zapisaną siódemkowo 1*7+2
b[0] = 1, c[0] = 2921, p = 2988
b[7] = 15, c[7] = 2977; p = 2981
b[8] = 17, c[8] = 2993 = [1,13]_2980; p = 2980
b[9] = 19, c[9] = 3011 = [1,32]_2979; p = 2979
następne można pominąć aż do b[53], gdyż jest skok cyfry jedności c[k]_p
b[54] = 109; c[54] = 5891 = [2,23]_2934; p = 2934
b[1901] = 3803; c[1901] = 3618623 = [3,68,0]_1087; p=1087  dzielnik
b[2981] = 5963; c[2981] = 8892263; p=7

Podnoszenie do kwadratu lub mnożenie

Podobny sposób, który był użyty do znajdowania pierwiastka kwadratowego w ostatnim poście, może też być użyty do podnoszenia liczby do kwadratu.
Są jednak pewne komplikacje - albo pracuje się na dużych liczbach, albo odcina się reszty, które są wyznaczonymi już cyframi wyniku.

Podczas badania odcinania reszt, wpadłem na pewną metodę. Każdy z czynników mnożenia zawiera 'schemat' dojścia konwersjami do potęgi 10, drugi czynnik podążając za tym schematem modyfikuje się w bardzo specyficzny sposób. Kiedy pierwszy stanie się już potęgą 10, drugi staje się wartością iloczynu.
Najciekawsze jest to, że krotność konwersji jest nie większa niż podwojona liczność cyfr liczby, z której pobieramy schemat. 
Rozpracowałem już mnożenie, ale zanim je opublikuję, chcę je skonsultować z naukowcami. Powód jest prosty, szacując złożoność, uzyskuję że jest ona logarytmiczna. Zaś mnożenie nie powinno być mniej pracochłonne niż dodawanie czy odejmowanie. Tym bardziej, że przy mnożeniu korzystam z kilku dzieleń.