Seite 1 von 1

Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 15:05
von levitin
Z17* ist eine zyklische Gruppe.

Wie findet man einen Generator g? Man fängt mit g = 2 an und erhöht a um 1 solange man alle Elemente aus Z17* bekommen?
g^a mod 17 = b (b element Z17*)

Wie kann man feststellen, dass der Generator falsch gewählt wurde?

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 16:29
von Christoph-D
levitin hat geschrieben:Z17* ist eine zyklische Gruppe.

Wie findet man einen Generator g?
Wär schön, wenn es dafür eine einfache Methode gäbe. :)

Es gibt Algorithmen dafür, die besser sind als naives Durchprobieren, aber bisher wohl keine wirklich effizienten: Siehe http://en.wikipedia.org/wiki/Primitive_ ... tive_roots.
levitin hat geschrieben:Wie kann man feststellen, dass der Generator falsch gewählt wurde?
Das kann man recht einfach testen, wenn man die Primfaktoren von phi(n) kennt (der Algorithmus steht in dem Wikipedia-Artikel).

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 16:57
von zeri
levitin hat geschrieben:Z17* ist eine zyklische Gruppe.

Wie findet man einen Generator g? Man fängt mit g = 2 an und erhöht a um 1 solange man alle Elemente aus Z17* bekommen?
g^a mod 17 = b (b element Z17*)

Wie kann man feststellen, dass der Generator falsch gewählt wurde?

Ich hab mal irgendwo gelesen, dass du eine zahl a > 1 nehmen kannst, dann ist a ** 2 mod p wohl ein generator. (hat bei meinen experimenten damit gut funktioniert)

EDIT: keine garantie für die korrektheit dieser aussage

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 17:13
von Christoph-D
zeri hat geschrieben:
levitin hat geschrieben:Z17* ist eine zyklische Gruppe.

Wie findet man einen Generator g? Man fängt mit g = 2 an und erhöht a um 1 solange man alle Elemente aus Z17* bekommen?
g^a mod 17 = b (b element Z17*)

Wie kann man feststellen, dass der Generator falsch gewählt wurde?

Ich hab mal irgendwo gelesen, dass du eine zahl a > 1 nehmen kannst, dann ist a ** 2 mod p wohl ein generator. (hat bei meinen experimenten damit gut funktioniert)

EDIT: keine garantie für die korrektheit dieser aussage
Sowas müsste eine mathematische Begründung haben.
Das geht schon schief bei p = 5 und a = 2, denn 4 ist kein Generator der Gruppe \(\mathbb{Z}^\ast_5\).
Auch bei p = 3 und a = 2 ist a^2 = 1 mod p, was kein Generator von \(\mathbb{Z}^\ast_3\) ist.

Auch bei größeren Zahlen: p = 17 und a = 15 ergibt a^2 = 4 mod 17, aber 4 ist kein Generator von \(\mathbb{Z}^\ast_{17}\), weil schon 4^4 = 1 mod 17 ist.

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 17:20
von levitin
Christoph-D hat geschrieben: Auch bei größeren Zahlen: p = 17 und a = 15 ergibt a^2 = 4 mod 17, aber 4 ist kein Generator von Z17 , weil schon 4^4 = 1 mod 17 ist.
Das heißt, die Ergebnisse der exp-modulo dürfen sich nicht wiederholen?
4^0 mod 17 = 1
4^1 mod 17 = 4
4^2 mod 17 = 16
4^3 mod 17 = 13
4^4 mod 17 = 1 <- abbrechen, da 1 schon als Ergebnis vorkam

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 19:10
von zeri
levitin hat geschrieben: Das heißt, die Ergebnisse der exp-modulo dürfen sich nicht wiederholen?
4^0 mod 17 = 1
4^1 mod 17 = 4
4^2 mod 17 = 16
4^3 mod 17 = 13
4^4 mod 17 = 1 <- abbrechen, da 1 schon als Ergebnis vorkam
Die ordnung des potentiellen generators auszurechnen kann aber nicht so richtig das wahre sein, da man dann für den fall, dass es ein generator ist, p-1 exponentiationen machen müsste ... sehr anstrengend, wenn p ne 1024bit primzahl ist!

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 19:26
von Christoph-D
zeri hat geschrieben:Die ordnung des potentiellen generators auszurechnen kann aber nicht so richtig das wahre sein, da man dann für den fall, dass es ein generator ist, p-1 exponentiationen machen müsste ... sehr anstrengend, wenn p ne 1024bit primzahl ist!
Man muss nicht p-1 oft potenzieren, wenn man die Primfaktorzerlegung von p-1 kennt. Dann reicht es, \(g^{\frac{p-1}{p_i}}\) für alle Primfaktoren p_i auszurechnen und zu prüfen, ob irgendwo 1 rauskommt. Das funktioniert wegen dem Satz von Lagrange. Die Primfaktorzerlegung kennt man aber natürlich nicht unbedingt. :/

Wenn du eine effizientere Möglichkeit kennst, um zu testen ob g ein Generator ist, immer her damit. Ich kenne bisher keine, würde mich aber interessieren, ob es was gutes gibt.

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 20:06
von zeri
Christoph-D hat geschrieben:Man muss nicht p-1 oft potenzieren, wenn man die Primfaktorzerlegung von p-1 kennt. Dann reicht es, \(g^{\frac{p-1}{p_i}}\) für alle Primfaktoren p_i auszurechnen und zu prüfen, ob irgendwo 1 rauskommt. Das funktioniert wegen dem Satz von Lagrange. Die Primfaktorzerlegung kennt man aber natürlich nicht unbedingt. :/

Wenn du eine effizientere Möglichkeit kennst, um zu testen ob g ein Generator ist, immer her damit. Ich kenne bisher keine, würde mich aber interessieren, ob es was gutes gibt.
Bei wiki (zu El Gamal) steht dass man p als Sophie-germain primzahl (p = 2 * q + 1 mit nem q das prim ist) wählt ... Hat früher für mich keinen Sinn gemacht (dachte das hätte was mit sicherheit oder so zu tun). Aber da kannst du natürlich trivial die zerlegung von phi(p) bestimmen. und damit deinen generator effektiv berechnen ^^

Re: Generator einer zyklischen Gruppe

Verfasst: 15. Mär 2010 20:09
von Christoph-D
zeri hat geschrieben:Bei wiki (zu El Gamal) steht dass man p als Sophie-germain primzahl (p = 2 * q + 1 mit nem q das prim ist) wählt ... Hat früher für mich keinen Sinn gemacht (dachte das hätte was mit sicherheit oder so zu tun). Aber da kannst du natürlich trivial die zerlegung von phi(p) bestimmen. und damit deinen generator effektiv berechnen ^^
Oh, das ist wirklich ein guter Trick. Gefällt mir. :)