primitive Elemte < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Finden Sie primitive Elemente in [mm] \IZ_{7},\IZ_{11},\IZ_{47} [/mm] |
Habt ihr einen schneller Weg wie alle Elemente einzeln durzuquadrieren um zu schauen ob man mit ihnen jeden wert von 1 bis ... erzeugen kann?
denn bei [mm] \IZ_{47} [/mm] würde das einige Zeit dauern :(
Liebe Grüße.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:20 So 15.04.2007 | | Autor: | felixf |
Hallo.
> Finden Sie primitive Elemente in [mm]\IZ_{7},\IZ_{11},\IZ_{47}[/mm]
> Habt ihr einen schneller Weg wie alle Elemente einzeln
> durzuquadrieren um zu schauen ob man mit ihnen jeden wert
> von 1 bis ... erzeugen kann?
>
> denn bei [mm]\IZ_{47}[/mm] würde das einige Zeit dauern :(
Ein primitives Element von [mm] $\IZ_p$ [/mm] ist ja gerade ein $a [mm] \in \IZ_p^*$, [/mm] dessen Ordnung in der multiplikativen Gruppe $p - 1$ ist.
Oder anders: ein Element $a [mm] \in \IZ_p^*$ [/mm] ist kein primitives Element, wenn seine Ordnung $< p - 1$ ist. Nach Lagrange ist die Ordnung ein Teiler von $p - 1$, womit es eine Primzahl [mm] $\ell$ [/mm] gibt so, dass [mm] $\ell$ [/mm] ein Teiler von $p - 1$ ist und das die Ordnung von $a$ ein Teiler von [mm] $\frac{p - 1}{\ell}$ [/mm] ist (nimm fuer [mm] $\ell$ [/mm] irgendeinen Primfaktor von [mm] $\frac{p - 1}{\mathrm{ord} \, a}$).
[/mm]
Es gilt also [mm] $a^{\frac{p - 1}{\ell}} [/mm] = 1$ in [mm] $\IZ_p^*$ [/mm] fuer einen Primteiler [mm] $\ell$ [/mm] von $p - 1$.
Wie du also effizient vorgehen kannst: faktorisiere $p - 1$ und bestimme alle Primteiler. Dann probiere $a = 2, 3, 5, 6, 7, 10, 11, ...$ (Potenzen von Elementen, die man schon hatte, kann man weglassen) oder durch und berechne jeweils [mm] $a^{\frac{p - 1}{\ell}}$ [/mm] fuer alle Primteiler [mm] $\ell$ [/mm] von $p - 1$. Ist das $1$ fuer ein solches [mm] $\ell$, [/mm] so ist $a$ kein primitives Element. Ist es dagegen [mm] $\neq [/mm] 1$ fuer jedes solche [mm] $\ell$, [/mm] so ist es ein primitives Element.
Hat $p - 1$ also nur wenige Primteiler, so kann man mit dieser Methode recht schnell testen ob ein Element primitiv ist oder nicht. Und wenn man bedenkt, dass fuer die meisten kleinen $p$ entweder $2$, $3$ oder $5$ primitiv ist, so ist man recht schnell fertig.
LG Felix
|
|
|
|
