Primitivwurzel – Rechner

Geben Sie einen Modul n ein, um seine kleinste Primitivwurzel zu finden.

So funktioniert's

  1. Geben Sie Ihre Werte in die Felder oben ein.
  2. Klicken Sie auf "Berechnen", um das Ergebnis zu sehen.
  3. Nutzen Sie "Teilen", um Ihr Ergebnis zu senden.

Über diesen Rechner

Eine Zahl g ist eine Primitivwurzel modulo n, wenn ihre Potenzen — g¹, g², g³ und so weiter — alle zu n teilerfremden Zahlen durchlaufen, bevor sie sich wiederholen, das heißt, der kleinste Exponent k, für den g^k ≡ 1 (mod n) gilt, ist genau φ(n), die Eulersche Phi-Funktion. Anders gesagt erzeugt eine einzelne Primitivwurzel die gesamte multiplikative Gruppe modulo n allein. Primitivwurzeln existieren nicht für jeden Modul: Die klassische Zahlentheorie (zurückgehend auf Gauß) zeigt, dass sie nur existieren, wenn n gleich 1 (trivial), 2, 4, eine Potenz einer ungeraden Primzahl oder das Doppelte einer Potenz einer ungeraden Primzahl ist.

Primitivwurzeln sind ein Arbeitswerkzeug in der Kryptografie, nicht nur eine Kuriosität: Der Diffie–Hellman-Schlüsselaustausch und das ElGamal-Kryptosystem stützen sich beide auf die Schwierigkeit des diskreten Logarithmusproblems in einer von einer Primitivwurzel erzeugten Gruppe, und zahlentheoretische Transformationen, die bei der schnellen, exakten Polynommultiplikation verwendet werden (relevant für einige moderne kryptografische und fehlerkorrigierende Verfahren), hängen ebenfalls davon ab, geeignete Primitivwurzeln eines Moduls zu finden.

Geben Sie einen ganzzahligen Modul n von 2 bis 100.000 ein, und dieser Rechner findet seine kleinste Primitivwurzel, zusammen mit φ(n) und der Anzahl der Primitivwurzeln. Existiert für dieses n keine Primitivwurzel, liefert er kein Ergebnis.

War das hilfreich?

Sie können bis zu 3 Reaktionen auswählen.

Kommentare

  • Schreiben Sie den ersten Kommentar.

Beliebte Rechner

Alle Rechner