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.