Faktoryzacja spradzająca duże i małe dzielniki

-->

Faktoryzacja liczb sprawdzająca prawie równocześnie największe i najmniejsze dzielniki jest możliwa do przedstawienia, chociaż algorytm jest bardziej skomplikowany. Przedstawię szkic za pomocą pseudokodu.

Ponieważ jednak podejście jest niestandardowe, najpierw funkcje biorące udział w algorytmach.

Liczba jest listą swoich cyfr, zaś cyfra to liczba z przedziału [0,p), gdzie p jest podstawą systemu liczbowego.

Last lista

zwraca ostatni element listy, w przypadku listy będącej liczbą, jej najmniej znaczącą cyfrę.

First lista

podobnie jak last, lecz zwraca pierwszy element listy, w przypadku liczb cyfrę najbardziej znaczącą.

Succ element

zwraca element poprzedzający dany iterator na liście, w braku takiego zwraca 0.

Move element lista

przenosi wskazany Element dołączając go do innej listy na koniec.

Rep [warunek] instrukcja

oznacza prostą pętlę powtarzającą się tak długo, dopóki warunek jest prawdziwy.

Fi instrukcje warunek

oznacza funkcję, która najpierw liczy instrukcje, a potem w zależności od warunku albo przywraca stare wartości, albo zostawia nowe, jest bardzo podobna do funkcji If, która robi to samo, ale w innej kolejności.

Konwersja [parametr]

tu oznacza konwersję zmniejszającą podstawę systemu o 2, chyba, że podany jest parametr. Wtedy zwiększa podstawę o ten parametr.

Corr [podstawa]

jest funkcją działającą na liczbach (listach) sprawdzającą, czy liczba jest poprawnie przedstawiona, w szczególności testuje warunki na cyfry, czy są liczbami całkowitymi w odpowiednim przedziale. Jeśli nie, nadmiary przenosi do cyfr bardziej znaczących, części ułamkowe jako liczby całkowite do cyfr mniej znaczących. Działa rekursywnie kończąc działanie, kiedy liczba jest we właściwej postaci.

Foreach lista : instrukcja

dla każdego elementu listy wykonuje podaną instrukcję.

Algorytm konwersji Konwersja [r=2]

Wejście: Liczba n pusta, Liczba m przy podstawie p+r, podstawa p

Rep [ m niepuste ] {

Move m.First n

Foreach n : element += r * Succ element

n.Corr [ p ]

}

Wyjście: Liczba n przy podstawie p, jako skutek uboczny może zmieniać p o r.

Algorytm faktoryzacji korzystający tylko z tej konwersji ma wadę: po znalezieniu dzielników nie wiemy, czy są one pierwsze czy złożone. Należy uruchomić algorytm ponownie dla każdego z dzielników, lub zapamiętać sprawdzonych kandydatów na dzielniki.

Jeśli dzielnik x dzieli podstawę systemu, aby dzielić liczbę, potrzebuje być także dzielnikiem wyrazu wolnego. W sprawdzaniu małych dzielników ograniczymy się tylko do iteracji, kiedy x jest dzielnikiem podstawy systemu.

Potrzebujemy trzech dodatkowych wartości: dzielnika minimalnego xmin, maksymalnego xmax oraz aktualnego x, inicjowanych x = xmin = 2, xmax=3.

Zaś dla większych liczb, często łatwiej i szybciej jest testować nieco większe wartości niż najbliższego kandydata na dzielnik. Mogą się one układać w pewien wzorek, w którym zaczynamy sprawdzać od większego kandydata, po czym w regularny sposób zmniejszamy do aktualnej najmniejszej podejrzanej wartości.

Przystąpmy do samego algorytmu faktoryzacji:

1. przygotowanie postaci liczby najmniejszej z trzycyfrowych n = [a, b, c], znalezienie podstawy p

2. Konwersja do najbliższej podstawy p nieparzystej i sprawdzenie dzielników xmin, x, xmax

3. dopasowanie licznika iteracji d

4. Rep [ istnieją kandydaci na dzielniki ] {

5. if 0= (d--) sprawdzenie i ponowne przeliczenie x, xmin, xmax, d

5a przy znalezionym dzielniku jego wyłączenie i restart algorytmu

6. Konwersja, modyfikacja podstawy p -=2

7. Corr [p]

8. if 0=n.Last czyli wyraz wolny równy 0, znaleziony dzielnik p; iteracyjny restart dla liczby z usuniętym Last, oraz z tą samą wartością xmin dla podstawy p

}

Ad 1. Chodzi o doprowadzenie do postaci b*p+c, w której b,c<p oraz p, b są największe z możliwych. W tym celu można przyjąć p jako sufit z pierwiastka kwadratowego liczby. Mając już tę postać stosujemy Konwercja [1], dzięki czemu uzyskujemy najmniejszą z możliwych liczbę trzycyfrową z a równym 1, b równym 0 albo 1 przy danej podstawie p;

Ad 2. W tym kroku sprawdzamy warunek p<xmin. Gdy 2=xmin, sprawdzamy podzielność przez 2 oraz stosujemy Konwersja [1], aby nie szukać niepotrzebnie dzielników po wartościach parzystych. Znalezione dzielniki usuwamy, i powtarzamy algorytm ze zmodyfikowaną liczbą. Gdy xmin jest większe, dobieramy x, xmax oraz d jak w 8;

Ad 3. Mała liczba naturalna d wskazująca, ile iteracji pętli będziemy czekać, aż x będzie dzielnikiem podstawy p. Jeśli nie jest wyznaczona w kroku 2, przyjmuje wartość 1 dla liczb postaci 3k+2, 2 dla liczb postaci 3k+4, wartość d=0 wykrywa podzielność przez 3;

Ad 4. Pętla 4-8, z której istnieją wyjścia na dwa sposoby, dla liczb pierwszych xmin>p, dla złożonych następuje ponowne wywołanie algorytmu dla poszczególnych dzielników z tymi samymi ustawieniami xmin;

Ad 5. W tym kroku d jako 0 wskazuje, że x dzieli p. Sprawdzamy, czy x dzieli też n.Last, czyli cyfrę najmniej znaczącą. Jeśli tak, mamy dzielnik x, zaś cała liczba ulega zniekształceniu, tak że należy zrestartować algorytm. Nie można podzielić podstawy oraz wyrazu wolnego przez x, gdyż wtedy mogą 'uciec' inne dzielniki. Jeżeli x>xmin, zmniejszamy x-=2 oraz liczymy d z pomocą y:

y = p modulo x; d = ( y%2 ? (y+x)/2 : y/2 )

Gdy x=xmin wstawiamy xmin = xmax oraz sprawdzamy wartości d liczone ww wzorem dla kolejnych elementów ciągu (p modulo (x+2*k) ). Interesuje nas podciąg malejący z wyjątkiem ostatniego elementu, który jest większy niż przedostatni. Taki podciąg cechuje się budową zbliżoną do (24, 22, 15, 8, 1, 17).

Przyjmujemy za xmax = (x+2*k) ostatniego elementu, oraz x = xmax-2.

Ad 8. Liczba jest iloczynem k*p, lecz nie wiemy, czy dzielniki są pierwsze czy złożone. Uruchamiamy algorytm dla tych wartości z aktualnym ustawieniem xmin;

Przykład liczbowy 169 747 007 = 19 * 1087 * 8219, szkic

Liczb niepodzielna przez 2. Do algorytmu wchodzi postać 

[a, b, c] = [1, 1, 5195] przy podstawie p=13028.

Następuje konwersja, by podstawa p była nieparzysta p=13027 = 3k+1, liczba [1, 3, 5197] , dwie iteracje doprowadzą do wartości p podzielnej przez 3. Obliczamy d dla p modulo 5 uzyskując 1, dla 7 jest większe. Mamy zatem d=1, xmin = 3, x = 5, xmax=7.

W pierwszej iteracji liczba przyjmuje postać 

[1, 7, 5207] przy p=13025. 

Podstawa p jest podzielna przez 5, lecz najmniej znacząca cyfra 5207 = 5*1041+2. Niezerowa reszta wskazuje, że 5 nie jest dzielnikiem. Zmniejszamy x do 3, d=1.

W drugiej iteracji liczba 

[1, 11, 5225] przy p=13023, 

p jest podzielne przez 3, sprawdzamy podzielność przez 3 cyfry najmniej znaczącej 5225 = 3*1741+2.

Teraz xmin=7, dane p jest podzielne przez 9, lecz x=9 nie jest dzielnikiem, jest 5 iteracji d=5 do sprawdzenia 7, reszta z dzielenia przez 11 jest większa, zatem xmax=11, x=7.

Po kolejnych kilku iteracjach okazuje się, że liczba postaci 

[1, 103, 7843] przy p=12977 

ma podstawę oraz najmniej znaczącą cyfrę podzielną przez x = xmin = 19.

Następuje restart algorytmu z xmin=19. Teraz należy powtórzyć krok 1. uzyskując postać liczby 169 747 007 : 19 = 8 934 053 jako 

[1, 3, 2923] przy p=2987. 

Teraz należy na nowo wyliczyć d=2, zaś do następnego dzielnika 21 jest 13 iteracji.

Kolejną postacią liczby jest [1, 7, 2933] przy p=2985.

I tak sprawdzamy kolejne duże dzielniki mniejsze od 2985, zarazem większe od 19.

Kiedy p opadnie do 1215, wiemy już z xmin=135, że dzielniki są w przedziale [xmax=157, 1215) lub sprawdzane właśnie 135, do sprawdzenia 173 dzielą nas dwie iteracje, zaś kolejne kandydatki: 171, 169, 167 i dalej dzieli taka sama krotność iteracji.

Osiągamy wreszcie postać [7, 580, 986] przy p=1089, dla której znowu następuje oczekiwanie na sprawdzenie dzielnika 217 (xmin=175) przy p=1085, lecz kolejna iteracja przekształca liczbę do postaci 

[7, 610, 0] przy p=1087. 

Mamy kolejne dzielniki: 1087 oraz 7*1087+610.

Obliczając jednak postać trzycyfrową tych wartości okazuje się, że są one mniejsze niż xmin=175, dzielniki są zatem liczbami pierwszymi.

Rozkład dokonany. 

W algorytmie tym rachujemy na coraz mniejszych wartościach, występujące dzielenie jest przez stosunkowo bardzo małe liczby. 

Logarytmy dyskretne - odczytywanie

W poprzednim poście z pierwszego października opisana została konstrukcja grafu, z której można odczytywać wartosci logarytmów dyskretnych. Czas na ćwiczenia praktyczne.

Porachujemy kilka logarytmów dyskretnych dla systemu Z_{17}. Został wybrany, gdyż dla tej liczby pierwszej pojawia się niejednoznaczność znajdowanych rozwiązań.
Dla przypomnienia podaję graf, którego lista jest wypisywana pionowo za numerem kolejnym wierzchołka. Wierzchołki listy są drzewami wysokości 1 o dwu liściach rozdzielonych '|'.
lista trywialna
0
lista długości 8:
1. 2 - 6 | 11
2. 4
3. 8 - 5 | 12
4. 16
5. 15 - 7 | 10
6. 13
7. 9 - 3 | 14
8. 1

Numer jest potrzebny, gdyż odczyt jest podobny jak w metodzie zliczania indeksów.
Rozwiązując równanie x^k = a (17) wyszukujemy pozycję a w grafie, tę pozycję listy dzielimy przez k. Jeśli nie jest to liczba całkowita dodajemy odpowiednią wielokrotność długości listy. Jeśli nie znajdujemy rozwiązania całkowitego, równanie nie ma rozwiązań. Wartość logarytmu odczytujemy z tego samego poziomu, co a.

Policzymy dla próby x^3 = 16 (17)
Szukamy 16 na listach. Znajdujemy na pozycji czwartej listy. Teraz znajdujemy położenie rozwiązania jako iloraz 4/3. Jest to liczba niewymierna, dodajemy długość listy (4+8)/3 = 12/3 = 4. Odczytujemy wartość: 16, oraz 16^3 = 16 (17).
Jest to proste, gdyż 16 = -1 (17) oraz (-1)^3 = (-1) = 16 (17).

Teraz coś trudniejszego, też z listy głównej:
x^5 = 9 (17)
Wartość 9 stoi na pozycji siódmej, zatem obliczamy pozycję wyniku (7+8)/5 = 3. Znajdujemy wartość 8, którą sprawdzamy: 8^5 = 9 (17). Zgadza się.

Kiedy wartość jest znaleziona w liściu, rozwiązanie też znajduje się na tym poziomie:
x^3 = 6 (17)
Wartość 6 jest na pozycji pierwszej listy, następuje tymczasowe 'podniesienie' do 2. Obliczamy pozycję wyniku (1+8)/3 = 3. Teraz 'schodzimy' poziom niżej znajdując dwie kandydatki: 5 oraz 12. Sprawdzamy je:
5^3 = 6 (17) oraz 12^3 = 11 (17).
Znaleźliśmy rozwiązanie 5, mając do sprawdzenia wybór jednej z dwu wartości.

Zwróćmy uwagę, że rachowane były wyższe potęgi niż druga. Dla tego sposobu wartość potęgi nie jest przeszkodą. W wikipedii większośc przykładów ograniczała się do potęgi drugiej, która przy tym podejściu jest często znajdowana 'z marszu'.


17 jest liczbą pierwszą. Sposób ten działa także dla liczb złożonych, lecz graf może być znacznie bardziej skomplikowany.
Przykładowo dla liczby 493 niektóre wartości mają do 8 pierwiastków, które trudno uporządkować liniowo. Dołączane do listy o długości 112 łańcuchy miały wysokość 1 lub 3. Dla 28 wartości przyłaczane łańcuchy długości 4 miały wspólny środkowy wierzchołek oraz maksimum lokowane na liście.
Wybieramy wtedy za jedną z list dowolny ze znalezionych łańcuchów długości 112, łańcuchy fragmentami są rozdzielne, lecz łączą się przy wartościach mających większą krotność pierwiastków. Przypomina mi to nieco budowę białek, kiedy poskręcane włókna wzajemnie się przeplatają. Pozostałe łańcuchy miały długości o 1 mniejsze niż dzielniki 493.
W przypadku doczepiania łańcuchów niektóre wartości musiały pojawiać się dwukrotnie, gdyż były sześcianami innych wartości, których łańcuchy nie obejmowały. Wartości te raz rozpoczynały łańcuch, za drugim razem sąsiadowały z korzeniem.

Logarytmy dyskretne - graf

W sierpniu podałem, że logarytmy dyskretne można znajdować za pomocą odpowiednio skonstruowanego grafu. Teraz podaję budowę tego grafu.

Najpierw nieco oznaczeń grafu zawierającego elementy zbioru Z_p:
ziarno - dowolna liczba 1< a < p; 
łańcuch - ciąg elementów dany resztami z a^k z dzielenia przez p, gdzie a jest ziarnem, p pochodzi z Z_p, k jest naturalne; z małego twierdzenia Fermata ciąg ten jest okresowy;
długość łańcucha - krotność elementów łańcucha liczonych od ziarna a do 0 lub 1 włącznie, albo do ponownego pojawienia się wartości a (łańcuch nie zawiera elementów 0, 1);  
lista - szczególny przypadek łańcucha, którego wierzchołki są grafami; listę tworzą najdłuższe łańcuchy (zazwyczaj);
struktura - zbiór częściowo uporządkowany podzbioru liczb Z_p relacją wziętą z łańcuchów; tworzy las czyli zbiór klasycznych drzew.

Grafy będące wierzchołkami listy to maksimum dla łańcuchów. Są one często
drzewami ukorzenionymi, czyli wierzchołek listy jest korzeniem drzewa.
Dla liczb złożonych mogą pojawić się także zbiory uporządkowane relacją z łańcuchów w sposób nieliniowy (istnieją rozgałęzienia łańcuchów). Taki przypadek spotkałem gdy p jest iloczynem nieco większych liczb, np p=493 = 17*29.

Tworzenie list.
Mamy dostępny zbiór wszystkich liczb Z_p. Będziemy je kolejno przenosić do grafu.
Wybieramy ziarno np. a=2. Tworzymy z niego łańcuch (a^k mod p), przemieszczając odpowiednie liczby. Przy okazji znajdujemy długość tego łańcucha n.
Jeśli 2n = p-1 lub n=p-1, p jest liczbą pierwszą (hipoteza sprawdzona dla p<50 i dla kilku większych p pierwszych).
Gdy n jest mniejsze, dzielimy p/n z resztą, szacując wartość reszty. Pozwala to przybliżyć wygląd grafów listy.
Za listy przyjmujemy łańcuchy. Jeśli z innego ziarna wygenerujemy łańcuch o wspólnym wierzchołku z pierwszym, zatrzymujemy generowanie, chyba że długość pierwszego uważamy za nieodpowiednią. Nowy łańcuch będzie miał więcej wierzchołków wspólnych, i czasem okazuje się lepszym kandydatem na listę.
Np. dla Z_{11} ziarno a=2 wygeneruje listę długości 6: a = (2^k) = (2 4 8 5 10 1), ale ziarno a=3 wygeneruje łańcuch odpowiedniej dla liczb pierwszych  długości 5: a = (3 9 5 4 1). 

Teraz mamy listę, oraz zbiór nieużytych wartości z Z_p. Wartości te usiłujemy przenieść doczepiając do listy jako grafy skierowane.
Wybieramy kolejne ziarno a nie należące do struktury, z którego generujemy łańcuch. Łańcuch tniemy na pierwszej wartości należącej do listy, oraz doczepiamy do odpowiedniego wierzchołka. Ostatecznie wszystkie wartości Z_p prócz ewentualnie 0 powinny zostać użyte.
Dla liczb złożonych mamy kilka niezależnych list. Mają one znacznie bardziej złożoną, i jak na razie niesklasyfikowaną budowę. Staram się tworzyć jak najbardziej symetryczne grafy.

Dla liczb pierwszych mamy 3 podstawowe listy (hipoteza prawdziwa dla liczb pierwszych mniejszych niż 75):
n=p-1, wszystkie elementy grypy multiplikatywnej Z_p^* są uporządkowane liniowo. Najłatwiejszy przypadek znajdowania, jak w metodzie zliczania indeksów (index calculi algorithm);
2n=p-1, wszystkie elementy listy mają doczepiony dokładnie jeden łańcuch, czyli dwuwierzchołkowe drzewo, którego korzeń jest na liście;
2n=p-1, co drugi element listy ma doczepione dwa łańcuchy, czyli pojawia się trójwierzchołkowe drzewo o korzeniu na liście, wysokości 1.

Liczby złożone mają bardziej skomplikowany wygląd, czasem nawet zamiast drzew pojawiają się grafy uporządkowane.

W przkładach poszukamy kwadratów, czyli takich wartości, które powstały z pomnożenia innych przez siebie.

Przykłady grafów dla rozwiązywania logarytmów dyskretnych:
Z_{19}, lista długości 18:
(2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1)
lista trywialna (0)
kwadraty: liczby przy wierzchołkach parzystych listy a[i] = {4, 16, 7, 9, 17, 11, 6, 5, 1} są kwadratami liczb na pozycjach a[i/2] oraz oraz a[(i+18)/2], np. 4 jest kwadratem 2 oraz a[(2+18)/2] = a[9] = 17.
Oraz oczywiście 0. 

Z_{14},
lista długości 3 zawierająca drzewa o 2 wierzchołkach, zapisywane (2 . 10):
( (2 . 10) (4 . 12) (8 . 6 ) );
lista liniowa długości 6: (3 9 13 11 5 1);
lista liniowa długości 1 zawierająca dzielnik: (7) i lista trywialna: (0)
kwadraty: kwadraty są na pozycjach parzystych list oraz w korzeniach doczepionych drzew, zbiór kwadratów: {2, 4, 8} + {9, 11, 1} + {7} + {0}

Z_{17}, oprócz listy trywialnej (0) lista mająca doczepione po dwa łańcuchy oddzielone przecinkami np. (2 . 6,11) oznacza złączenie łańcuchów (6-2-) oraz (11-2-) w jeden wierzchołek listy '2':
( (2 . 6,11)  4  (8 . 5,12)  16  (15 . 10,7)  13  (9 . 3,14)  1 )
kwadratami jak wcześniej są parzyste wierzchołki listy oraz te wierzchołki, które są korzeniami, tu wszystkie wierzchołki listy {2, 4, 8, 16, 15, 13, 9, 1}.

Sposób odczytywania logarytmów dyskretnych jest w poście z 3 października tego roku.