Witam!
Troche sie zebralo roznych watpliwosci, wiec moze postaram sie to jakos
uporzadkowac.
1) Rzeczywiscie, dla grup multiplikatywnych Z*_p (p - pierwsza) nie ma
wielomianowego algorytmu znajdowania generatora. Nie znaczy to jednak, ze
nie jestesmy w stanie szybko go znalezc za pomoca algorytmu
probabilistycznego. Jest bowiem twierdzenie:
Niech G bedzie grupa cykliczna rzedu n. Dla kazdego dodatniego
dzielnika d liczby n ilosc elementow rzedu d w grupie G jest rowna
eulerphi(d).
Zatem dla grupy Z^*_p, ktora jest rzedu p-1 mamy eulerphi(p-1)
generatorow (czyli elementow rzedu p-1, generujacych cala grupe).
Korzystajac teraz z oszacowania prawdziwego dla wszystkich n>=5
eulerphi(n) > n / (6 ln ln n)
[BTW., czy ktos wie, gdzie mozna znalezc dowod tego wzoru?]
mozemy wywnioskowac, ze wybierajac losowo element grupy Z*_p szansa, ze
jest on generatorem wynosi
eulerphi(p-1)/(p-1) = 1/(6 ln ln (p-1)).
Zatem dla liczby pierwszej majacej 100 cyfr binarnych bedziemy srednio
potrzebowali ok. 25 testow a dla liczb 500 cyfrowych bedzie to ok. 35 testow.
Jezeli jednak znamy faktoryzacje p-1 (bo np. tak konstruowalismy liczbe
p, zeby znac faktoryzacje p-1), mozemy ta procedure jeszcze ulepszyc.
2) Grupa cykliczna, to grupa generowana przez pojedynczy element, ale to nie
znaczy, ze ma ona tylko jeden, pojedynczy generator. Generatorow jest wiele
i kazdy z nich generuje cala grupe cykliczna.
3) Dla porzadku dodam jeszcze, ze kazda grupa cykliczna rzedu (skonczonego) n
jest izomorficzna z addytywna grupa (Z_n, +).
4) Po szczegoly odsylam zainteresowanych do bardzo dobrej ksiazki V.Shoup'a,
ktora mozna sobie sciagnac za darmo ze strony:
http://shoup.net/ntb/
Tematyce znajdowania generatora w grupie Z^*_p poswiecony jest tam
rozdzial 11, a ogolne rozwazania na temat grup cyklicznych mozna
znalezc w rozdziale 8.
Bardzo dobra pozycja, goraco polecam.
Serdeczne pozdrowienia,
Krystian Matusiewicz
PS. Przepraszam za brak pl liter.