Auf dieser Seite können Sie primitive Wurzeln modulo einer Primzahl bestimmen. Falls die vorgegebene Zahl keine Primzahl ist, wird die nächste Primzahl gesucht. Es können Zahlen bis 9223372036854775808 (2^63)) verwendet werden. Maximal werden 500 primitive Wurzeln bestimmt.
Die Ordnung einer Zahl x in der primen Restklasse p wird mit Hilfe des Satzes von Lagrange bestimmt. Dieser sagt aus, daß die Ordnung eines Elements einer endlichen Gruppe die Ordnung der Gruppe teilt.
Es wird zunächst die Primfaktorzerlegung von φ(p)=p-1 (Ordnung der Gruppe) und danach alle möglichen Teiler von φ(p) bestimmt. Diese Teiler sind dann alle möglichen Ordnungen der primen Restgruppe. Die Teiler werden nach Größe sortiert und dann die modulare Potenz x t mod p berechnet. Die erste Zahl, bei der diese Potenz 1 ist, ist die Ordnung von x in der primen Restklasse p.
| 28 = | 2 | * 2 | * 7 |
Test von 2:
| 2 28/2 | mod 29 | = | 2 14 | mod 29 | = | 28 |
| 2 28/7 | mod 29 | = | 2 4 | mod 29 | = | 16 |
⇒ Primitive Wurzel 2 gefunden
Test von 3:
| 3 28/2 | mod 29 | = | 3 14 | mod 29 | = | 28 |
| 3 28/7 | mod 29 | = | 3 4 | mod 29 | = | 23 |
⇒ Primitive Wurzel 3 gefunden
Test von 4:
| 4 28/2 | mod 29 | = | 4 14 | mod 29 | = | 1 |
(war nichts)
Test von 5:
| 5 28/2 | mod 29 | = | 5 14 | mod 29 | = | 1 |
(war nichts)
Test von 6:
| 6 28/2 | mod 29 | = | 6 14 | mod 29 | = | 1 |
(war nichts)
Test von 7:
| 7 28/2 | mod 29 | = | 7 14 | mod 29 | = | 1 |
(war nichts)
Test von 8:
| 8 28/2 | mod 29 | = | 8 14 | mod 29 | = | 28 |
| 8 28/7 | mod 29 | = | 8 4 | mod 29 | = | 7 |
⇒ Primitive Wurzel 8 gefunden
Test von 9:
| 9 28/2 | mod 29 | = | 9 14 | mod 29 | = | 1 |
(war nichts)
Test von 10:
| 10 28/2 | mod 29 | = | 10 14 | mod 29 | = | 28 |
| 10 28/7 | mod 29 | = | 10 4 | mod 29 | = | 24 |
⇒ Primitive Wurzel 10 gefunden
Test von 11:
| 11 28/2 | mod 29 | = | 11 14 | mod 29 | = | 28 |
| 11 28/7 | mod 29 | = | 11 4 | mod 29 | = | 25 |
⇒ Primitive Wurzel 11 gefunden
| 2 | 3 | 8 | 10 | 11 |