Generator einer zyklischen Gruppe

levitin
Kernelcompilierer
Kernelcompilierer
Beiträge: 435
Registriert: 7. Okt 2007 15:36
Wohnort: Darmstadt

Generator einer zyklischen Gruppe

Beitrag 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?

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Generator einer zyklischen Gruppe

Beitrag 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).
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

zeri
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: Generator einer zyklischen Gruppe

Beitrag 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
don't get even, get odd!

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Generator einer zyklischen Gruppe

Beitrag 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.
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

levitin
Kernelcompilierer
Kernelcompilierer
Beiträge: 435
Registriert: 7. Okt 2007 15:36
Wohnort: Darmstadt

Re: Generator einer zyklischen Gruppe

Beitrag 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

zeri
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: Generator einer zyklischen Gruppe

Beitrag 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!
don't get even, get odd!

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Generator einer zyklischen Gruppe

Beitrag 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.
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

zeri
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 17. Jul 2009 23:25

Re: Generator einer zyklischen Gruppe

Beitrag 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 ^^
don't get even, get odd!

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Generator einer zyklischen Gruppe

Beitrag 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. :)
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

Antworten

Zurück zu „Archiv“