Gigantyczne kłopoty z dostępem do bloga.Przy moim ulubionym interfesie dużo rzeczy niewidocznych bądź nie działa. Ryzyko literówek, których nie jestem w stanie wykryć.
Mnożenie w niektórych systemach niedziesiątkowych jest łatwo odwracalne. Wystarczy korzystając od cyfr najmniej znaczących rozwiązać odpowiednie układy kongruencji. Liczba jest odwracalna, gdy w systemie mamy dla każdego iloczynu przez cyfry różne końcówki cyfr oraz cyfra najmniej znacząca nie jest pełnym kwadratem. Zatem w systemie dziesiętnym mnożenie nie jest odwracalne. Gdy podstawa jest liczbą pierwszą, mnożenie może stać się odwracalne, o ile najmniej znacząca cyfra ma rozkład na dwa różne czynniki (binarny nie spełnia tego warunku).
Na przykład, wszystkie liczby dziesiętne zakończone na 3 lub 7 mają proste odwrócenie mnożenia w systemie piątkowym, najczęściej należy sprawdzać zaczynając od 3 = 1*3 equiv 4*2 albo 7 \equiv 1*2 \equiv 4*3.
A następnie znajdować kolejne cyfry bardziej znaczące z układu kombinacji liniowych jak z mnożenia pisemnego. Można też sprawdzać odwracając mnozenie Karatsuby, te też staje się odwracalne.
Np liczby
A = a[2]*5^2 + a[1]*5 + a[0]
B = b[2]*5^2 + b[1]*5 + b[0]
Mnożenie C = A*B polega na wypełnianiu pól:
c[0] = a[0]*b[0] // 1*3 lub 2*4 lub 1*2 lub 3*4
c[1] = a[1]*b[0] + a[0]*b[1] // kombinacja liniowa, jedna z wykorzystywanych kongruencji
c[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2] // kombinacja liniowa + wyraz już wyliczalny
c[3] = a[2]*b[1] + a[1]*b[2] + 0 // wyliczalne, bo nie a[3] = b[3] = 0 w przykładzie
c[4] = a[2]*b[2]
A następnie dopasowujemy pożyczki między polami. Ogólnie c[k] = sum _{p+q=k}a[p]*b[q].
Drugi układ kongruencji wykorzystuje kombinacje liniowe oraz przeniesienia z pól o mniejszych indeksach. Mamy zależności między parami tych kongruencji zależne od a[0], b[0], np. (3,4) = (i,j) daje
(i, j) \equiv (i+1, j-2) mod 5
Znajomość przeniesień czyni mnożenie odwracalnym.
Liczba 10002 w piątkowym. Podejrzewamy, że dzielniki przystają do 2 equiv 3*4 mod 5, bo 3*4 = 2*5+2, przeniesienie 1, bo 3+4 = 12. Pożyczamy tworząc postać liczby w niepoprawnym piątkowym 4 4 5 2 (wycofane zostały przeniesienia blokujące odwracanie).
Teraz sprawdzamy kongruecje kombinacji liniowych (i,j) \equiv (12 - 2)/5 = 0 mod 5. Są nimi (0,0), (1,3), (2,1), (3.4), (4,2); wybieramy tą o sumie i+j \equiv 5-1 \equiv 4 mod 5. Dzielniki dla pary (1,3) kończą się na _34 * _13.
Następna iteracja to kombinacja liniowa z uwzględnienia wszystkich dotychczasowych przeniesień (i,j) equiv (2 + 3*3+1*4)/5 = 3 z rozwiązaniami (0,2), (1,0), (2,3), (3,1), (4,4) oraz sumie 4-3 = 1 mod 5.
Ta para uzgadnia pozostałe wartości do wyniku: 34*113 = 10002 w piątkowym, co w dziesiątkowym daje (3*5+4)*(25+5+3) = 19*33 = 627 = 5^4+2.
