Generator grupy.

[MN]

Witam

Jak sie oblicza generator zbioru, czy jest jakis "przepis" ?
Dla przykladu, wiemy, ze
generatorem grupy Z*29 jest g=2.
Jak to sie wylicza ?
Dziekuje za pomoc i pozdrawiam.

Aga

[pb]

Ogolnego przepisu nie ma. W tym wlasnie rzecz, zeby, jesli istnieje taka
mozliwosc , wskazac generator grupy. Czasem jednak mozemy wyciagac pewne ogolne
wnioski odnosnie generatorow grupy, gdy mamy do czynienia z pewnym konkretnym
typem grupy. Z pewnoscia mozemy powiedziec, ze grupa cykliczna ma jeden
generator. Latwo bawic sie z grupami C_n. Pozdrawiam.

--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

[MN]

Jeszcze cos.
Taki generator jest zawsze potrzebny gdy chcemy wykorzystac algorytm
ElGamala. Naprawde nie ma zadnego algorytmu obliczania tego generatora ?
Jak wiec stosowac metode ElGamala ? :/

Aga

[my.e...@autograf.pl]

Generatorami takich grup są liczby względnie pierwsze, w tym przypadku z 29,
czyli wszystkie liczby od 1 do 28. Para liczb względnie pierwszych ma nwd =
1 (mozna skorzystac z algorytmu euklidesa).
Użytkownik "MN" <kl...@polbox.com> napisał w wiadomości
news:c7i6pq$nss$1...@news.onet.pl...

[MN]

To znaczy, ze wszystkie liczby 1, 2, ..., 28 sa generatorami grupy Z*29 ? I
jak wykorzystac algorytm Euklidesa ?

Aga

Użytkownik <my.e...@autograf.pl> napisał w wiadomości
news:c7iil8$lbi$1...@atlantis.news.tpi.pl...
> Generatorami takich grup s± liczby względnie pierwsze, w tym przypadku z

[my.e...@autograf.pl]

No tak. Czy na pewno znasz definicję generatora? to taka liczba, która po
wykonaniu ilus tam dzialan, da nam elementy calej grupy, np. 1. bo 1+1 to 2
potem 3, 4 itd, tak samo 27, bo masz 27, 25, 23...1, 28, 26, itd. 29 jest
liczb± pierwsz±, zatem wszystkie liczby mniejsze od 29 s± z ni± względnie
pierwsze. Algorytm Euklidesa pozwala Ci szybko sprawdzać, czy dane dwie
liczby s± ze sob± względnie pierwsze.
Użytkownik "MN" <kl...@polbox.com> napisał w wiadomo¶ci
news:c7ik76$crs$1...@news.onet.pl...

[eelt]

> Generatorami takich grup są liczby względnie pierwsze, w tym przypadku z
29,
> czyli wszystkie liczby od 1 do 28. Para liczb względnie pierwszych ma nwd
=

no chyba nie bo jak przypuszczam chodzi o grupe multiplikatywna np dla Z*7 i
2 nie jest generatorem
o ile wiem to w przypadku Z*p pierwsza takich generatorow jest duzo (zalezy
od rozkladu p-1) i szuka sie ich losowo wybierajc liczby i sprawdzajac czy
sie udalo(co mozna zrobic szybko)
co to jest elgamala?

[MN]

Oj chyba nie!!! Generator jest zawsze jeden (chociaz nie wiem dlaczego :/ )
Niestety jego znalezienie to nie taka prosta sprawa i w przypadku duzego p
wydaje mi sie, ze wrecz niewykonalna. Jesli interesuje Cie algorytm ElGamala
zapraszam na priva. Wysle Ci co trzeba :)

Aga

Użytkownik "eelt" <ee...@wp.pl> napisał w wiadomości
news:c7jjjb$p6o$1...@atlantis.news.tpi.pl...
> > Generatorami takich grup s± liczby względnie pierwsze, w tym przypadku z

[MN]

Tak jest w przypadku gdy dzialaniem jest "+".
A co gdy dzialaniem jest "mod 29" bo wlasciwie o taka grupe mi chodzi ???
Mozna sie zaliczyc na smierc sprawdzajac kolejne liczby czy nie sa
generatorami.

Użytkownik <my.e...@autograf.pl> napisał w wiadomości

news:c7inl1$me6$1...@nemesis.news.tpi.pl...

[eelt]

> Oj chyba nie!!! Generator jest zawsze jeden (chociaz nie wiem dlaczego
:/ )

Dla grupy multiplikatywnej dla p pierwszego jest generatorow
funkcja_eulera(p-1) jesli np .p-1=q1*q2
to generatorow jest (q1-1)*(q2-1) czyli multum. Nawet dla bardzo duzej p nie
ma zadnego problemu zeby znalezc generator

[my.e...@autograf.pl]

No tak, ale jak jest w grupie multiplikatywnej?
m.e

Użytkownik "eelt" <ee...@wp.pl> napisał w wiadomości

news:c7l7pu$912$1...@nemesis.news.tpi.pl...

[Michał Strojnowski]

> co to jest elgamala?
ElGamal - kryptosystem asymetryczny:
Mamy grupę (G,*) oraz jej generator a (zapewne wylosowany). Kluczem
prywatnym jest losowe x < |G|, kluczem publicznym (G,a,b=a^x).
Szyfrowanie wiadomości m: losujemy k i publikujemy (y1,y2)=(a^k, m*b^k)
Deszyfrowanie: m1=y2/(y1^x)=m
Bezpieczeństwo opiera się na domniemanej trudności policzenia logarytmu w
grupie G.

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

[Krystian Matusiewicz]

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.