Aufgabe zu zyklischen Gruppen

27.12.2007, 16:28	flasher	Auf diesen Beitrag antworten »
Aufgabe zu zyklischen Gruppen Hallo! Ich habe hier eine Aufgabe im Themenbereich zyklische Gruppen vorliegen. Ich kann auch den Aufgabenteil a) und c) lösen, allerdings bei b) fällt mir nur ein ineffizientes Verfahren ein, dass so eigentlich nicht der Lösungsweg sein kann. Zur Aufgabe: Verwenden Sie im Folgenden einige (nicht sehr schwer zu beweisende) Tatsachen über endliche Gruppen, G, \|G\| = m: $\begin{eqnarray} g \in G \end{eqnarray}$ ist ein Generator von G (G ist somit zyklisch), genau dann, wenn für jeden Primteiler p von m gilt $\begin{eqnarray} g^{\frac{m}{p} } \neq 1 \end{eqnarray}$ (:= neutr. Element). Ist G zyklisch, so hat Phi(m) verschiedene Generatoren: Man erhält aus einem Generator $\begin{eqnarray} g \in G \end{eqnarray}$ alle Generatoren als die Potenzen $\begin{eqnarray} g^{k} \end{eqnarray}$ ; $\begin{eqnarray} k \in [1:m-1];ggT(k;m)=1 \end{eqnarray}$ Nach dem in der Vorlesung zitierten Satz von Gauß ist G := Z343 zyklisch ( $\begin{eqnarray} 343 = 7^{3} \end{eqnarray}$ ). a) Zeigen Sie dass 3 ein primitives Element in G ist. b) Wie viele weitere Generatoren hat G? Geben Sie mindestens 4 an! c) Berechnen Sie in G den diskreten Logarithmus von 65 zur Basis 3. Soweit die Aufgabe: zu a) Konnte ich problemlos anhand des ersten Satzes erledigen. zu b) Von der Theorie her klar, ich muss einfach die k heraussuchen für die gilt $\begin{eqnarray} g^{k} \end{eqnarray}$ ; $\begin{eqnarray} k \in [1:m-1];ggT(k;m)=1 \end{eqnarray}$ Ich kann das also mühsam für m-1 Elemente durchführen. Das sind 293 Tests. Ich vermute aber, dass es hier einen einfacheren Weg gibt. z.B. sind für k = 6 die zwei Bedingungen erfüllt. Allerdings weiß ich keine Möglichkeit! zu c) Mit Hilfe des Baby-Step-Giant-Step-Algorithmus lösbar! Für Hinweise bin ich dankbar! Schöne Grüße, Flasher
27.12.2007, 17:06	20_Cent	Auf diesen Beitrag antworten »
Habs mal in die Algebra verschoben...
27.12.2007, 17:51	therisen	Auf diesen Beitrag antworten »
Es gibt $\begin{eqnarray} \varphi\left(7^3\right)=7^2(7-1)=294 \end{eqnarray}$ verschiedene Generatoren. Es werden nur 4 gesucht.
27.12.2007, 18:31	flasher	Auf diesen Beitrag antworten »
Verwenden wir z.B. k = 4 dann wäre der ggT(k,m) --> ggT(4,294) --> 2 und nicht 1 und somit wäre es dann kein Generator mehr. Irgendwie ist mir der ganze Satz nicht klar. Es wird defniert, dass es $\begin{eqnarray} \varphi(343) \end{eqnarray}$ Generatoren gibt, und dass für alle dann diese Bedingung gilt: $\begin{eqnarray} k \in[1:m-1];ggT(k;m)=1 \end{eqnarray}$ Aber das ist ja z.b. bei k = 4 nicht der Fall.
27.12.2007, 19:11	therisen	Auf diesen Beitrag antworten »
Es ist $\begin{eqnarray} \mathrm{ggT}(4,7^3)=1 \end{eqnarray}$ und somit ist $\begin{eqnarray} 3^4 \end{eqnarray}$ ein weiterer Generator.
27.12.2007, 19:21	flasher	Auf diesen Beitrag antworten »
Das ist mir ehrlich gesagt nicht klar, ich bin bisher davon ausgegangen dass: $\begin{eqnarray} m = \|G\| = \varphi(343) \end{eqnarray}$ Das steht bei uns auch so im Script. Und somit wäre ja m = 294 und nicht 343.
Anzeige

27.12.2007, 19:28	therisen	Auf diesen Beitrag antworten »
Nein, das stimmt nicht. Die Einheitengruppe hätte diese Ordnung.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »