Rozważany w ostatnim poście algorytm okazał się niezależny od podstawy systemu. Sprawdził się w binarnym, sprawdził się też w dziesiątkowym.
Funkcja jest postaci
(1) k(x,n,p,a,b) = -(p+b)/p + n/(p*(px+p+a)
dla potęgi podstawy systemu p, liczby rozkładanej n, odpowiednio przygotowanych wartości a, b spełniajacych warunek
(2) a*b%p = n%p.
Dzielniki zależne od punktów kratowych (x,k) spełniają zależności
p*(x+1)+a, p*(k+1)+b.
Aby szybciej wyznaczyć dzielniki, z użyciem mniejszych liczb, trzeba odpowiednio przygotować a oraz b.
Pokażę to na przykładzie n = 8934053 = 1087*8219. Wartość p = 10.
Najmniej znacząca cyfra n to 3, szukam w tabliczce mnożenia iloczynów, które kończą się na 3. W systemie dziesiątkowym znajduję 4 takie. Ze względu na symetrię dwa można odrzucić. Są to pary (1,3) oraz (7,9).
Jeśli podstawa systemu jest liczbą pierwszą, takich par jest tyle, ile niezerowych cyfr - połowa się powtarza ze względu na symetrię. Ale tylko w tym kroku. W dalszych symetria najczęściej jest zaburzona oraz trzeba sprawdzać wszystkie przypadki (10 w dziesiątkowym).
Mamy już pary: 1*3 = 3 oraz 7*9=63. W podanym we wcześniejszym poście przebiegu powinniśmy odjąć je od n. Lecz teraz odcinamy najmniej znaczącą cyfrę zarówno od n, jak i od tego iloczynu. Uzyskamy odpowiednio e=0 oraz e=6, oraz n=893405.
Modyfikujemy sposób wyznaczania a, b oraz e. Zmieni to nieco sposób wyznaczania punktów kratowych.
Załóżmy, że wykorzystujemy parę (a,b) = (7,9), oraz przechodzimy do następnej cyfry: p = p*10 = 100, n=89340. Dołączymy cyfry bardziej znaczące do a, b. Zanim to jednak zrobimy, zapamiętamy wartość dziesiątek e=6 z iloczynu 63.
Dokładamy do a jako cyfrę najbardziej znaczącą kolejno c=0, 1, ..., 9, dopasowywując d w taki sposób, aby powstałe liczby
a*b = (c##7) * (d##9) %100 = 53.
Interesuje nas tylko cyfra dziesiątek 5. Zatem obliczenie sprowadza się do prostej kongruencji liniowej: 9c+7d+e=5, czyli 9c+7d+1=0.
Na przykład dla c=0 powstaje a=07, dalej 0*9+7*d+1=0 skąd d=7 oznacza, że b=79. Rzeczywiście 7*79=553.
W ogólności mnożymy dokładaną cyfrę do a przez cyfrę najmniej znaczącą b, dodajemy doń iloczyn cyfry dokładanej do b z najmniej znaczącą cyfrą a, fragment iloczynu wcześniejszych cyfr trzymaną w e oraz iloczyn dokładanych cyfr, przesunięty o p. W tym przypadku mamy
0*9+7*7+6+0*7*100 = 56.
Odcinamy cyfrę najmniej znaczącą 6 przyjmując nową wartość e=5. Jest to całość z dzielenia a*c przez p.
W kolejnym przypadku dokładamy do a=7 cyfrę 1, uzyskujemy 1*9+7*d+1=0 skąd d=0 oraz wartości a=17, b=09, oraz e = (1*9+0*1+6)/10 = 1.
Zamiast wyznaczać iloczyn a*b, dodamy do siebie aktualne wartości
g = a+b+e+1*p
U nas to będzie g = 07+79+5+1*100 = 191.
Sprawdzanie przypadków zmieniło się, należy sprawdzić podzielność (n-g)%(1##a), (n-g)%(1##b). W naszym przypadku (89340-191)%109 oraz (89340-191)%179. Punkty całkowite są punktami kratowymi krzywej (1), które wkładamy do równań na dzielniki.
Do następnej iteracji z p=1000 wartość n przejdzie jako n=8934.
Wtedy z przybliżenia dzielników powstałych z a=87, b=19 dla c=0 uzyskamy
0*9+2*d+6=0, skąd d=2, b=219, e=(0*19+2*87+16+0*2*100)/10 = 19;
g = 087+219+19+1*1000 = 1325;
8934-1325 = 7*1087 wskazuje dzielniki, co kończy obliczenia.
Oczywiście, wartości a=07, b=79 nie przybliżają dzielników, robią to wartości a=87, b=19. Ale i tak po przerobieniu co najwyżej 220 przypadków (440 dzieleń) będziemy znali dzielniki.
Dzielenie przez wartości nieparzyste to 542 przypadki.
21 września 2013
09 września 2013
Wzory na budowę dzielników
Kolejny algorytm faktoryzacji opisywany w tym blogu powstał dzięki odwróceniu kolejności w geometrycznym mnożeniu w systemie binarnym.
Mnożenie geometryczne polega na zapisaniu cyfr dzielników przy brzegach prostokąta, wewnątrz zapisujemy iloczyny tych cyfr, przy czym cyfra dziesiątek jest 'na innej przekątnej' niż cyfra jedności. Następnie sumujemy po przekątnych, np. wartość na cyfrze dziesziątek powstaje z sumy:
a_1*b_0 + a_0*b_1 + (a_0*b_0)/10.
Po uwzględnieniu przeniesień mamy wynik.
Sposób ten zastosowany w systemie binarnym wskazuje prostą zależność między bitami dzielników, co pozwala wyznaczyć te dzielniki, niestety, tylko na 50%. Ale wystarczy.
Połączyłem te informacje z moim pierwszym algorytmem, w którym zakładałem, że dzielniki sa odpowiedniej postaci (2^i*c+a) i sprawdzałem, czy jest tak rzeczywiście.
Niektóre informacje okazały sie nadmiarowe, i tak oto powstał wzór na funkcję dzielników k(x) liczby n, przy potędze dwójki i:
(1) k = -(i+b)/i + n/(i (ix+i+a) )
W tym wzorze n jest rozkładaną liczbą, i jest potęgą 2, szukamy dzielników większych niż i, wartości a oraz b są resztami z dzielenia n przez i, spełniającymi zależność bitową:
(2) (n - a*b) AND (i-1) = 0
Oznacza to, że a*b oraz n mają dokładnie takie same bity najmniej znaczące, czyli stanowią swoiste 'bitowe przybliżenie' dzielników.
Po przekształceniu wzoru (1) do wspólnego mianownika uzyskujemy funkcję holomorficzną postaci
(3) k = (-bx+q)/(ix+a),
w której i jest potęgą 2, q powstaje z ilorazu różnicy n oraz a*b, co jest liczbą naturalną bliską n*i^(-2). Dzielniki znajdujemy, gdy funkcja ta ma punkt kratowy (x,k), tzn. x, k są całkowite (interesują nas tylko nieujemne).
Wspomniane wzory na dzielniki:
i*(k+1)+b
oraz
i+x*i+a
Przykład: n=8934053, i=1024, znaleziona para (a,b) = (27,63) spełnia zależność (2), ich iloczyn w szesnastkowym to 0x2A5, oraz n jest postaci n = 0x400*d + 0x2A5.
funkcja (1) dla tego przypadku:
k = -(1024+63)/1024 + 8934053/(1024(1024x+1024+27))
przekształca się do
k = -1087(x-7)/(1024x+1061)
Punkt kratowy (x,k) = (7,0) wstawiamy do wzorów na dzielniki:
1024*(0+1)+63 = 1087
1024+7*1024+27 = 8219
Sprawdzamy, że rzeczywiście 8934053 = 1087*8219.
Mając postać (3), wystarczy przeglądać x naturalne w poszukiwaniu punktów kratowych, licznik maleje, mianownik rośnie, wartości są nie większe niż n*i^(-2). Im większe i, tym mniej wartości mamy do sprawdzenia, gdyż dla x rosnącego iloraz zmniejsza się wykładniczo. Kiedy zejdzie poniżej 0, nie znajdziemy dzielników. Ale trzeba spradzić parę początkowych wartości, żeby dzielnik nie umknął.
Największym kłopotem może być dopasowanie pary (a,b). Ale zaczynając od i=4, gdy bit na pozycji 'dziesiątek' liczby n jest ustawiony (n&2=1), a=1, b=3. Gdy bit ten jest zgaszony (n&2=0), mamy dwie możliwości a=b=1 albo a=b=3.
Teraz zwiększajac i = 2*i, sprawdzamy kombinacje par (a,b), (a+i,b), (a, b+i), (a+i,b+1). Dwie z nich mają takie same bity najmniej znaczace jak n - te zostawiamy, pozostałe dwie mają znak różny i je usuwamy. W ten sposób tworzy nam się drzewo binarne przypadków, w którym co najmniej jedna gałąź wskazuje rozkład. Dla liczb pierwszych jest to (a,b) = (1,n).
Mnożenie geometryczne polega na zapisaniu cyfr dzielników przy brzegach prostokąta, wewnątrz zapisujemy iloczyny tych cyfr, przy czym cyfra dziesiątek jest 'na innej przekątnej' niż cyfra jedności. Następnie sumujemy po przekątnych, np. wartość na cyfrze dziesziątek powstaje z sumy:
a_1*b_0 + a_0*b_1 + (a_0*b_0)/10.
Po uwzględnieniu przeniesień mamy wynik.
Sposób ten zastosowany w systemie binarnym wskazuje prostą zależność między bitami dzielników, co pozwala wyznaczyć te dzielniki, niestety, tylko na 50%. Ale wystarczy.
Połączyłem te informacje z moim pierwszym algorytmem, w którym zakładałem, że dzielniki sa odpowiedniej postaci (2^i*c+a) i sprawdzałem, czy jest tak rzeczywiście.
Niektóre informacje okazały sie nadmiarowe, i tak oto powstał wzór na funkcję dzielników k(x) liczby n, przy potędze dwójki i:
(1) k = -(i+b)/i + n/(i (ix+i+a) )
W tym wzorze n jest rozkładaną liczbą, i jest potęgą 2, szukamy dzielników większych niż i, wartości a oraz b są resztami z dzielenia n przez i, spełniającymi zależność bitową:
(2) (n - a*b) AND (i-1) = 0
Oznacza to, że a*b oraz n mają dokładnie takie same bity najmniej znaczące, czyli stanowią swoiste 'bitowe przybliżenie' dzielników.
Po przekształceniu wzoru (1) do wspólnego mianownika uzyskujemy funkcję holomorficzną postaci
(3) k = (-bx+q)/(ix+a),
w której i jest potęgą 2, q powstaje z ilorazu różnicy n oraz a*b, co jest liczbą naturalną bliską n*i^(-2). Dzielniki znajdujemy, gdy funkcja ta ma punkt kratowy (x,k), tzn. x, k są całkowite (interesują nas tylko nieujemne).
Wspomniane wzory na dzielniki:
i*(k+1)+b
oraz
i+x*i+a
Przykład: n=8934053, i=1024, znaleziona para (a,b) = (27,63) spełnia zależność (2), ich iloczyn w szesnastkowym to 0x2A5, oraz n jest postaci n = 0x400*d + 0x2A5.
funkcja (1) dla tego przypadku:
k = -(1024+63)/1024 + 8934053/(1024(1024x+1024+27))
przekształca się do
k = -1087(x-7)/(1024x+1061)
Punkt kratowy (x,k) = (7,0) wstawiamy do wzorów na dzielniki:
1024*(0+1)+63 = 1087
1024+7*1024+27 = 8219
Sprawdzamy, że rzeczywiście 8934053 = 1087*8219.
Mając postać (3), wystarczy przeglądać x naturalne w poszukiwaniu punktów kratowych, licznik maleje, mianownik rośnie, wartości są nie większe niż n*i^(-2). Im większe i, tym mniej wartości mamy do sprawdzenia, gdyż dla x rosnącego iloraz zmniejsza się wykładniczo. Kiedy zejdzie poniżej 0, nie znajdziemy dzielników. Ale trzeba spradzić parę początkowych wartości, żeby dzielnik nie umknął.
Największym kłopotem może być dopasowanie pary (a,b). Ale zaczynając od i=4, gdy bit na pozycji 'dziesiątek' liczby n jest ustawiony (n&2=1), a=1, b=3. Gdy bit ten jest zgaszony (n&2=0), mamy dwie możliwości a=b=1 albo a=b=3.
Teraz zwiększajac i = 2*i, sprawdzamy kombinacje par (a,b), (a+i,b), (a, b+i), (a+i,b+1). Dwie z nich mają takie same bity najmniej znaczace jak n - te zostawiamy, pozostałe dwie mają znak różny i je usuwamy. W ten sposób tworzy nam się drzewo binarne przypadków, w którym co najmniej jedna gałąź wskazuje rozkład. Dla liczb pierwszych jest to (a,b) = (1,n).
Subskrybuj:
Posty (Atom)