Czy istnieje wzór na dzielniki?

Przyglądajac się przekształcanej w różnych systemach pozycyjnych liczbie, zacząłem się zastanawiać, czy istnieje gotowy wzór, aby, mając postać liczby w jakimś systemie, dowiedzieć się, o ile należy dokonać konwersji, aby uzyskać dzielnik.
W teorii sprawa wydaje się prosta. Dla liczb co najmniej dwucyfrowych (czyli jednej z najczęściej spotykanych postaci) szukany wzór można podać jawnie (a0, a1 to 'cyfry' liczby w systemie o podstawie p):

przekształcić tak, aby cyfra najmniej znacząca a0 stała się zerem,
a0 - x * a1 = 0  (modulo p+x )
lub
a0 + x * a1 = 0 ( modulo p-x )

Równanie rekurencyjne liniowe, które za pomocą równania diofantycznego np.
x * a1 - py - xy = a0
w wielu przypadkach uda się rozwiązać mimo nieliniowości. Rozwiązanie zawsze istnieje. Istnieje dokładnie jedno dla liczb pierwszych.

Praktyka jest gorsza. Otóż wzór działa w bardzo wąskim zakresie, dopóki nie przeniesiemy nadmiaru lub pożyczki. Kiedy nastąpi takie zdarzenie, pojawia się modyfikacja.
Dla innego przypadku, takim niefortunnym zdarzeniem psujacym wynik jest brak przeniesienia nadmiaru lub pożyczki.
Zatem można go stosować w bardzo wąskich zakresach, nieekonomiczne.

Śledziłem zmiany cyfry najbardziej znaczącej a0 przy podstawach p dla liczb trójcyfrowych, kiedy zmniejszałem p o 2 sprawdzając nieparzystych kandydatów na dzielniki.
Okazało się, że szukany współczynnik x zachowuje się jak ciągła liczba rzeczywista, wzrastając od jakiejś wartości 2k do wartości 2k+2. Prawie płynnie. Wartość k zależała od cyfr bardziej znaczących, w szczególności cyfry setek.
Wartość cyfry najmniej znaczącej wzrastała w każdym kroku o 2k, 2k+2, itd.
Różnice między kolejnymi cyframi najmniej znaczącymi liczby postaci początkowej 1'0'2 przy malejącej podstawie były 1, 3, 5 itd.
Dlatego stosunkowo łatwo było wyznaczyć podstawę, w której następowało przeniesienie lub pożyczka, po czym, szczególnie przy większych k, należało modyfikować wzór.

Ślad cyfry najbardziej znaczącej brany modulo p ze zmniejszającym się bardzo dużym p przypomina ślad punktu na kole, które porusza się coraz szybciej. Najpierw widać przyrosty odległości, następnie ślad się rozmywa, później pojawiają się wolniej obracające się 'szprychy', zmienia się ich liczność. Przy dużych szybkościach zmienia się kierunek 'widocznego' obrotu i zdaje nam się, że koło się kręci 'do tyłu'. Tak jest między innymi, gdy cyfra dziesiątek będzie się zbliżała do podstawy p.

Mnożenie przez zmianę systemów, ulepszenie

Ćwicząc kolejne działania arytmetyczne wróciłem do algorytmu mnożenia przez zmianę systemów pozycyjnych. Opracowany algorytm wygląda w pseudokodzie następująco:
Dane: liczby a>=b.
Liczba a konwertowana do systemu o podstawie b, tu ma wygląd a'.
Mnożenie a' przez b wyglądające jak 10, iloczyn to liczba a'0.
Konwersja liczby a'0 na system początkowy, uzyskując a*b.
Wynik: iloczyn a*b. 

Tutaj cyfry są liczbami należącymi do przedziału [0,p), gdzie p jest podstawą systemu liczbowego.
Konwersja z systemu o podstawie r na system o podstawie b ma przebieg następujący, przy oznaczeniach:
a jest tablicą cyfr  [an ... a1 a0]
r=10^i jest potęga 10 spełniającą warunek r<= b < 10*r:

1. c =  najbardziej znacząca cyfra liczby a w systemie o podstawie r, c = [an]
2. Dopóki nie pobrane wszystkie cyfry liczby a powtarzaj 3.-5.
3. przenieś kolejną cyfrę z a do c: c = c + [ak] = [a'n ... ak]
4. dla wszystkich liczb tablicy c wykonaj  [cj] = [cj] - (b-r)*[c{j+1}], j>k-1
5. wszystkie liczby c sprowadź do cyfr za pomocą pożyczek lub przeniesień w systemie o podstawie b
6. a' = c
Liczba a' jest postacią liczby a w systemie o podstawie b

Niezmiennikiem konwersji jest fakt, że ciąg [an ... ak] przy podstawie pierwotnej p ma taką samą wartość jak ciąg [a'n ... a'k] przy podstawie p+(b-r).

Niezmiennik ten powoduje, że wszystkie operacje pętli 2.-5. z wyjątkiem ostatniej są operacjami do siebie odwrotnymi, i można je pominąć. Zostaje tylko jednorazowo przeprowadzona operacja 4. 5. dla liczby a'0.

Zatem mnożenie a*b w zależności od argumentów sprowadza się do kilku mnożeń na liczbach wielkości r<=b < a, których liczność jest wyznaczona przez a/b.

Pomnóżmy przykładowo 5.027.608.376 * 1008.
Wtedy b=1008, r=1000, i=3. Ciąg a to ciąg trójek cyfr dziesiętnych
[5, 27, 608, 376].
Z konwersji niesparowany jest przyrost o 8 ciągu z dopisanym zerem [5, 27, 608, 376, 0].
Krok 4. to dodawanie pomnożonych przez 8 wartości poprzedzających. Czyli mamy 4 mnożenia przez 8 i kilka dodawań. Uzyskujemy ciąg
[5, 67, 824, 5240, 3008].
Krok 5. to usunięcie nadmiarów, by wynik był w systemie o podstawie 1000:
[5, 67, 829, 243, 8].
Wreszcie ostatnia czynność, odczytanie wyniku iloczynu  w systemie dziesiątkowym:
5.067.829.243.008 


Mając liczby zawierające 480 oraz 500 bitów, możemy wziąć r = 2^i oraz system binarny. Ten sposób zamienia podany iloczyn na iloczyn liczb zawierających zaledwie około 480 bitów jedna (podstawa) oraz 500-480=20 bitów druga (cyfra 'dziesiątek' przy podstawie liczby 480-bitowej). Oznacza to, że zamieniamy  mnożenie dwu gigantycznych liczb na mnożenie przez małą wartość. Gdyż (b-r) jest liczbą mniejszą o co najmniej rząd wielkości od r.