Wspomniałem 18 grudnia o nowym pomyśle na faktoryzację, związanym z przedstawianiem podstawy systemu w postaci kanonicznej.
Pomysł jest tak specyficzny, że działa także dla normalnych liczb, choć potrzeba pamiętania ogromnych wartości z ich dzielnikami powoduje, że sposób jest nieopłacalny, i nikt o nim nie wspomina.
Podobnie jest i teraz, choć wymagam tylko znajomości tablicy liczb pierwszych nie przekraczajacych pierwiastka czwartego stopnia z rozkładanej liczby. Nie mamy? Nic straconego, delikatna rekursywna modyfikacja i już taką uzyskujemy, niejako przy okazji.Ale teraz podaję jakby tablica ta była znana.
Zacznijmy od nieformalnego podziału liczb pierwszych w zależności od rozkładanej liczby N:
- małe, mniejsze niż pierwiastek czwartego stopnia z N;
- średnie, większe niż pierwiastek czwartego stopnia, ale pojawią się w co najmniej dwu warstwach badanych;
- duże, wystąpią raz, rozpoznajemy je po tym, że podstawa systemu jest albo taką liczbą pierwszą, albo jej podwojeniem.
W pętli przeszukiwania zupełnego duże liczby pierwsze są sprawdzane i ignorowane. Potrzebujemy struktury kopca trzymajacego strukturę (liczba, lista jej dzielników), sortowaną malejąco po liczbie. Wkładając do kopca liczbę z dzielnikiem, sprawdzamy jej obecność. Jeśli już jest, tylko dopisujemy kolejny dzielnik do listy. Kopiec osiąga rozmiar równy krotności wszystkich małych i średnich liczb pierwszych.
Zaczynamy od liczby n będącej pierwiastkiem kwadratowym z N, w kopcu umieszczamy wartości (n- (n%k), k), gdzie k są małymi liczbami pierwszymi. Wiemy, że są one już dzielnikami podstawy systemu, trzeba jeszcze sprawdzić, czy są dzielnikami N.Dlatego specjalnie je zaznaczamy do sprawdzenia. Każdą liczbę pierwszą sprawdzamy dokładnie raz.
Mamy niezmiennik
N = (a+b)*a+c
Jeśli liczba k dzieli a oraz c, dzieli też N.
W pętli algorytmu przechodzimy na kolejną warstwę operacjami:
a-=1;
b+=2;
c+=b-1;
stosując przemieszczenie nadmiaru (z liczby w systemie o podstawie a), by c było ograniczone przez a. Może być też ujemne. Wartosć b tylko zwiększamy, może przekroczyć a. Dzielnik znajdziemy jako wspólny dzielnik gcd(c,a). Wystarczy tylko warunek 0= c%a, zamiast szukać wspólnego dzielnika gcd(c,a). Jest to pierwszy krok szukania tegoż dzielnika, i właśnie tyle wystarczy przy założeniu znajomości małych liczb pierwszych.
Algorytm przebiega następująco:
- pobieramy liczbę o 1 mniejszą, czyli n:=n-1
jeżeli z kopca, dzielimy ją przez jej dzielniki (z listy) by uzyskać jak najmniejszą wartość d, w przeciwnym przypadku generujemy;
uzyskujemy w ten sposób liczbę pierwszą d albo 1;
- dzielimy c%d i sprawdzamy reszty, tak samo z małymi liczbami pierwszymi z pobranej listy, reszta zero oznacza dzielnik, który zwracamy. Wyjście z algorytmu. Przy reszcie niezerowej te liczby pierwsze już nie muszą być sprawdzane, zaznaczają tylko kolejne wartości dla wygodniejszego szukania d;
- dla wszystkich uzyskanych średnich i małych liczb pierwszych k wprowadzamy do kopca pary (n-k, k);- przechodzimy na kolejną warstwę a-1;
- powtarzamy, aż osiągniemy połowę pierwiastka kwadratowego z N, zwracamy że N jest liczb pierwszą;
Załóżmy N=893453
pierwiastek kwadratowy sqrt N = 2988, którego kolejny pierwiastek to 54.
Bierzemy listę liczb pierwszych mniejszych niż 55 i wprowadzamy do kopca w postaci (c2 oznacza konieczność sprawdzenia podzielności 2 przez N):
(2988, [c2,c3])
(2987, [c29])
(2985, [c5])
(2983, [c19])
(2982, [c7])
(2981, [c11])
(2977, [c13])
(2976, [c31])
(2975, [c17])
(2968, [c53])
(2967, [c23, c43])
(2961, [c47])
(2960, [c37])
(2952, [c41])
Przystępujemy do algorytmu:
pobieramy n=a=2988, które ma dwa dzielniki: 2 i 3. Po podzieleniu przez nie n (czasem kilkakrotnie uzyskujemy nową średnią liczbę pierwszą d=83.
Niezmiennik dostarcza a=2988, b=1, c=2921
Sprawdzamy, czy N jest podzielne przez 2, 3, 83, dzieląc c przez te wartości. Zawsze występuje niezerowa reszta, zatem odkładamy do kopca nowe pozycje (2988-83, [83]) = (2905, [83]), (2985, [3]), (2986, [2])
Pozycja wyznaczona przez 2985 przyjmuje teraz wartość (2985, [3, c5])
Następna pozycja (2987, [29]), wskazuje kolejną liczbę pierwszą 103. Ale poznieważ c było duże, możemy przenieść 2987 z c jako jedynkę do b uzyskując
nową postać niezmiennika a=2897, b=4, c=-64
Sprawdzamy obydwie liczby 'dzieląc' 64%29, 64%103, odkładając na kopiec kolejne dwie wartości (2884, [103]) oraz (2958, [29]).
I tak początkowo co iterację dostajemy nową liczbę pierwszą, którą sprawdzamy. Ale wkrótce mamy wziąć 2978, na kopcu jest (2978, [2]), i mamy rozkład 2978 = 2*1489. Jest to duża liczba pierwsza w myśl podziału. Wartości (1489, [1489]) nie odkładamy do kopca.
Wartość (2976, [2,3,c31]) ma rozkład wykorzystujący tylko te cyfry, d=1. Z niezmiennika, c urosło do 101, sprawdzamy 101%31. Przy następnej takiej wartości 2970 nie ma już nic do sprawdzenia - wszystkie użyte dzielniki zostały sprawdzone.
Nieco wcześniej mamy 2971, której to wartości nie ma w kopcu. Jest to duża liczba pierwsza d=2971, która jest za duża, by być dzielnikiem. Niezmiennik ma wtedy znacznie mniejsze c=256.
W ten sposób znajdujemy kolejne liczby pierwsze; zeszlibyśmy z a do połowy 2988 czyli 1494, gdyby nie dzielnik, który znajdziemy dla pozycji o niezmienniku a=2174, b=1935 lub b=1936, c=|1087|, d=1087 = |c|.
Teraz modyfikacje.
Jeśli nie znamy wszystkich małych liczb pierwszych, możemy wywołać procedurę dla pierwiastka rekursywnie. Jednak wtedy każda znaleziona wartość pierwsza (także duza) generuje nowy obiekt do kopca do sprawdzenia. Przy wywołaniu rekursywnym niezmiennik jest nieistotny, nie porównujemy ani nie sprawdzamy. Uzyskamy w ten sposób tablicę liczb pierwszych.
Może być, że w petli głównej wartość jest iloczynem mniejszych liczb pierwszych, dla średnich liczb pierwszych wkrótce napotkamy kolejną warstwę z tym dzielnikiem, który powienien być lepiej widoczny (bo np. zmieni się parzystość). Ale dla dużych liczb pierwszych obawiam się przeoczenia tego dzielnika.
Na szczęście kierunek przechodzenia warstw można odwrócić.Proponowanym punktem startowym jest połowa pierwiastka z N, czyli w tym przykładzie a=1494, b=3a=4482 (choć lepiej 4486, gdyż wtedy c=-67).
Brak komentarzy:
Prześlij komentarz