Mnożenie przez zmianę systemów - mnożenie chłopów rosyjskich

Sprawdziłem kilka algorytmów dotyczących mnożenia, korzystając z postaci uzyskanej przez zmianę systemów. Prawie wszystkie okazują się nieefektywne, mając duży narzut obliczeniowy. Dzielenie jest znacznie prostsze.

Powrotna wersja przekształceń liczby "a 0_p" do systemu dziesiątkowego wymaga podczas konwersji mnożenia przez stosunkowo duże liczby.

Wywoływanie iteracyjne konwersji zmieniających podstawę o 2^k dla kolejnych k jest szybkie komputerowo, lecz ma tyle wywołań, ile jedynek zawiera komputerowy zapis mniejszego z czynników. 

Pozostaje jeszcze jeden algorytm, bazujący na konwersjach
2a * p + b = a * (2p) + b
(2a+1) * p + b = a * (2p) + (p+b).
Liczbie "a 0_p" wartość a jest połowiona, po jakimś czasie ze względu na przenoszenie jedynek z nieparzystych wartości a do cyfry mniej znaczącej cała zawartość a przeniesie się do cyfry jednostek. Wtedy mamy wartość dziesiątkową iloczynu zapisaną w cyfrze jednostek.
Nie jest to nic innego jak tzw. mnożenie chłopów rosyjskich, i to jeszcze przy słabym uporządkowaniu czynników.

Ale mnożenie chłopów rosyjskich można zastosować od razu do czynników uporządkowanych malejąco, bez bawienia się konwersjami.
Mamy tylko tyle przekształceń, ile wynosi log_2 z mniejszego z czynników.

Oto przykładowe zastosowanie algorytmu mnożenia egipskiego. Pomnożymy 5*129.
Mniejsza jest 5, zatem będziemy dzielić 5 przez 2, zaś drugi czynnik 129 będziemy mnożyć przez dwa oraz dodawać do wyniku, kiedy reszta będzie niezerowa. 
pierwszy czynnik z dzieleniem, drugi czynnik p mnożony przez 2, wynik w
5/2=2 r 1  p=129   w = 129
2/2=1 r 0  p=258
1/2=0 r 1  p=516   w = 129+516 = 645
koniec, uzyskujemy wynik 5*129 = 645.
Bez bawienia się konwersjami, że 129 ma postać 1004_5 w piątkowym, zaś iloczyn 5*129 przedstawiamy jako 10040_5, jak przy mnożeniu przez zmianę podstaw.

Publikacje

Międzynarodowa wymiana listów owocuje powstawaniem abstraktu opartego na moim pomyśle. Artykuł sprawdził i praktycznie napisał od nowa Djilali Behloul z Algerii.
Nie możemy zastosować standardowych modeli pamięciowych - prowadzą do  użytkowania stałych zasobów pamięci przez cały czas działania.
Z kolei model arytmetyczny, szacowany przeze mnie na
O ( n log^2 n )
jest jeszcze mniej złożony
O ( sqrt n log^2 n )
co dla bardzo dużych liczb jest poniżej złożoności liniowej.

Jest też konkurs prowadzony przez firmę Securitum na artykuł o szeroko pojętym bezpieczeństwie sieci. Wysłałem tam swoje najnowsze informacje dotyczące faktoryzacji oraz logarytmów dyskretnych. 
Jeżeli znajdę las dopasowany do danego logarytmu dyskretnego, znalezienie dowolnej z wartości staje się równoważne przeszukaniu tegoż, co jest wykonywane bardzo szybko.Zastanawiam się, czy można przewidzieć typ lasu.
Bliższe informację zamieszczę po zakończeniu konkursu.