Beschreibung
Der Gauß-Algorithmus ist ein Algorithmus um eine Primitivwurzel einer Prime Restklassengruppe zu erhalten.
Algorithmus
Sei eine Prime Restklassengruppe der Ordnung :
Der Gauß-Algorithmus läuft in Schritten ab:
- Beginne mit . Sei ein beliebiges Element der Primen Restklassegruppe Berechne
- Wenn , dann ist schon ein Erzeuger von , also Primitivwurzel
- Wähle ein Element , welches keine Potenz von ist. und berechne Wenn , setze . ist eine Primitivwurzel
- Suche und mit und
- Sei , dann gilt Erhöhe um und wiederhole ab .
Erklärung Schritt 3
Wir suchen ein Element . Im 4. Schritt wollen wir ein Element berechnen, welches und durch Potenzieren erzeugt. Die Ordnung des neuen Elements kann kein Teiler von sein, da sonst in der von erzeugten Untergruppe läge.
Erklärung Schritt 4
Die Existenz eines solchen ist nicht auf den ersten Blick offensichtlich. Durch ein Beispiel lässt sich die Methode, mit der man zwei solche Elemente findet leicht illustrieren: . Wir wollen ein finden, sodass und Nehmen wir für einfach selbst, dann sind die ersten beiden Anforderungen erfüllt. Will man noch die dritte Erfüllen, können wir so lang Faktoren aus entfernen, bis sie teilerfremd sind, also erfüllen. Entfernen wir alle Faktoren aus . Wir müssten alle Teiler entfernen da diese auch in liegen. Wir erhalten , was zar erfüllt aber nicht Klar, wir haben auch die letzte Bedingung nicht berücksitigt.
Wie können wir Faktoren aus entfernen, sodass wir die letzte Bedingung berücksichtigen? Für den kgV zweier Zahlen gilt die folgende Regel Wir dürfen nicht einfach beliebig viele Faktoren aus der ersten Zahl entfernen. Wir müssen immer so viele Faktoren entfernen wie und gemein sind. Damit die beiden Zahlen aber teilerfremd werden ist es notwendig, dass wir die gemeinsamen Faktoren aus der Zahl entfernen, die weniger dieses Faktors hat. So teilen sich die Zahlen keine gemeinsamen Faktoren, d.h. und wir sind haben die Faktoren so entfernt, dass . Führen wir die Idee auf durch: Wir entfernen die gemeinsame aus und die gemeinsame aus und erhalten . Es gilt und
Erklärung Schritt 5
Warum gilt für , ? Nach den Rechenregeln für Ordnung (Gruppe) gilt:
Für ein mit
Auf unseren Fall angewendet: Und analog Da teilerfremd sind gilt (Siehe dazu Ordnung (Gruppe))
Übungen
McEliece Übung 3-5
Betriachte den Körper
a)
Was ist ? . Die Ordnung muss also sein.
Die Ordnung muss oder ein Teiler davon sein. Alle Teiler im Exponenten ergeben aber nicht , d.h.
Damit muss
ist oder Teiler. Die Teiler sind es aber nicht.
b)
Finde ein Element mit . . Dann ist mit
c)
Was ist die kleinste Zahl in welche keine Potenz von ist?
- ist immer Potenz
- ist Potenz da
- ist Potenz
- , ist also Potenz, da
- ( kann also keine Potenz von sein, denn sonst müsste das hier ergeben. kann nur Ordnung 24 oder 72 haben)
d)
Was ist und . ist eine Primitivwurzel.
Suche , sodass .
Suche , sodass . Benutze den euklidischen Algorithmus, um eine sinnvolle Linearkombination zu finden.
| 1 | 0 | 72 | |
| 0 | 1 | 30 | |
| 1 | -2 | 12 | 2 |
| -2 | 5 | 6 | 2 |
Damit gilt . In Folge und damit
. Das rechte ist ein lineares Gleichungssystem. Die Lösungspunkte sind eine Gerade mit der Gleichung
Der Punkt ist ein Punkt auf der Gerade. Die Gerade hat die Steigung . Die Anderen Ganzzahligen Punkte sind damit Also:
Es gilt
Das heißt
&= (5^{4})^{30} = 41^{30}\\ &= (5^{16})^{30} = 4^{30} \\ &= (5^{28})^{30} = 36^{30} \\ &= (5^{40})^{30} = 32^{30}\\ &= (5^{52})^{30}= 69^{30}\end{align}$$ Suche $y$, sodass $59 = 5^y$ $59$ ist eine Primzahl. Es gibt also keine billigen Tricks, um an Faktoren heranzukommen. - $59^2 = 50$ - $59^4 = 18$ - $59^8 = 32 = (5^8)^5 = 5^{40}$ - $59 =5^5$ Suche $x$, sodass $30x = 5 \mod 72$. Eine solche Zahl gibt es nicht. Für alle $x$ ist $30x$ gerade. Insbesondere ist $30x\mod 72$ gerade und kann niemals kongruent zu $5$ sein. $\newcommand{\R}{\mathbb R}$ elieceFiniteFieldsComputer2012]]