W ostatnim poście pokazałem sposób faktoryzacji dużych liczb. Wejściową daną była poostać bliska pierwiastkowi kwadratowego z rozkładanej liczby n, czyli
n = a b r _ p
gdzie a=1, b=0 lub b=1, r jest resztą z dzielenia n przez p, zaś p jest podstawą systemu. Parametry r, p, b można liczyć klasycznie, ale istnieje też sposób mający złożoność arytmetyczną logarytmiczną.
Będziemy wykorzystywać binarną postać liczby n.
Jako pierwszy krok potrzebujemy podział liczby n na dwie części, mniej więcej na połowy, które także oznaczam przez b, r. Dalsze modyfikacje sprowadzą te wartości do odpowiednich parametrów. Oto warunki podziału: podstawa jest potęgą 2 nieco większą niż połowa n:
p = 2^k,
n < p^2,
b < p, r < p,
b*p+r = n.
Warunki te zapewnia przyjęcie k jako połowy logarytmu binarnego z n,
b = (n >> k) ;
r = n % (2^k);
Mając już tę postać, posługujemy się konwersjami
d e _ {p+f} = d {e+d*f} _ p
dla f będącymi potęgami 2. Oczywiście liczby e+d*f często są większe niż podstawa systemu p, zatem nadmiary są przenoszone do cyfry d.
Konwersje te stosujemy tylko wtedy, gdy
b+2^{k+1} < p.
Chodzi o to, by przybliżać się do pierwiastka z nadmiarem - będziemy mieli wtedy ciągle do czynienia z liczbą dwucyfrową b r _ p.
Algorytm to prosta pętla po zmniejszającym się k. Kiedy wspomniany warunek jest spełniony, stosowana jest konwersja. Krotność wykonania konwersji jest związana z krotnością zer w binarnym przedstawieniu pierwiastka.
Zmniejszając iteracyjnie k = (k>>1), parametry b oraz p zbiegają do wartości pierwiastka kawadtowego, kiedy k=0, co najmniej jeden z nich osiąga wartość pierwiastka. Kiedy są różne, jest to mniejszy z nich.
Na zakończenie stosujemy konwersję na system z podstawą o 1 mniejszą, co doprowadza do potrzebnej trójcyfrowej postaci wejściowej.
Przykład liczbowy: szukanie pierwiastka 169 747 007 < 2^{28}.
Tutaj za k zamiast wykładnika 28/2 = 14 przyjęta jest cała potęga 2^{14} = 16384. W kolumnach podane są wartości b, r, p, k, spełnienie warunku b+2k < p oznaczane jest przez p-=k, co oznacza zastosowanie konwersji.
Przygotowanie: p = k = 16384, b = n*2^{-14} = 10360, r = n%k = 8767
b r p k konwersja o
10360 8767 16384 16384
10360 8767 16384 8192
10360 8767 16384 4096
10360 8767 16384 2048 p-=2048
11840 8767 14336 1024 p-=1024
12751 5695 13312 512
12751 5695 13312 256 p-=256
13001 5951 13056 128
13001 5951 13056 64
13001 5951 13056 32
13001 5951 13056 16 p-=16
13017 5327 13040 8 p-=8
13025 5207 13032 4
13025 5207 13032 2 p-=2
13027 5197 13030 1 p-=1
13028 5195 13029 0
Wiemy zatem, że pierwiastek całkowity to 13028, zakończenie to konwersja na system o tej podstawie (wystarczy wymienic b z p). Uzyskamy postać:
1 1 5195 _ {13028}
Wynika ona z przeniesienia nadmiaru: 13029 = 13028 +1 = p+1.
Brak komentarzy:
Prześlij komentarz