Primitivwurzel-Rechner

Primitivwurzel-Rechner

Der Primitivwurzel-Rechner findet alle Primitivwurzeln eines gegebenen Moduls n — ganze Zahlen g, deren Potenzen \(g^1, g^2, \ldots, g^{\varphi(n)}\) jedes Element der multiplikativen Gruppe \((\mathbb{Z}/n\mathbb{Z})^*\) erzeugen. Geben Sie eine beliebige positive ganze Zahl ein, um sofort alle Primitivwurzeln, die Eulersche Phi-Funktion \(\varphi(n)\), eine interaktive Visualisierung des zyklischen Gruppenrads, eine Potenztabelle und eine Schritt-für-Schritt-Verifizierung der kleinsten Primitivwurzel zu sehen.

Anwendungen von Primitivwurzeln

Wichtige Konzepte und Formeln

Primitivwurzeln verstehen

Eine Primitivwurzel modulo n ist eine ganze Zahl g, so dass die Menge \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) der Menge aller ganzen Zahlen von 1 bis n−1 entspricht, die teilerfremd zu n sind. Gruppentheoretisch ausgedrückt ist g ein Erzeuger der zyklischen multiplikativen Gruppe \((\mathbb{Z}/n\mathbb{Z})^*\). Zum Beispiel ist 3 eine Primitivwurzel mod 7, da die Potenzen 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) jedes Element von {1, 2, 3, 4, 5, 6} erzeugen.

Wann existieren Primitivwurzeln?

Ein klassisches Resultat der Zahlentheorie (bewiesen von Gauß) besagt, dass Primitivwurzeln modulo n genau dann existieren, wenn n einer der folgenden Werte ist: 1, 2, 4, p^k oder 2p^k, wobei p eine ungerade Primzahl und k ≥ 1 ist. Für andere Werte von n ist die Gruppe \((\mathbb{Z}/n\mathbb{Z})^*\) nicht zyklisch — sie zerfällt nach dem Chinesischen Restsatz in ein direktes Produkt zyklischer Gruppen — sodass kein einzelnes Element die gesamte Gruppe erzeugen kann. Beispielsweise hat \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) keine Primitivwurzel.

Wie man Primitivwurzeln effizient findet

Der Standardalgorithmus arbeitet in zwei Phasen. Phase 1: Finden der kleinsten Primitivwurzel durch Ausprobieren. Für jeden Kandidaten g, beginnend bei 2, wird \(g^{\varphi(n)/p} \bmod n\) für jeden Primfaktor p von \(\varphi(n)\) berechnet. Wenn keiner dieser Werte gleich 1 ist, dann ist g eine Primitivwurzel. In der Praxis ist die kleinste Primitivwurzel meist klein — es wird vermutet, dass sie \(O(n^\epsilon)\) für jedes \(\epsilon > 0\) ist. Phase 2: Sobald eine Primitivwurzel g bekannt ist, sind alle anderen Primitivwurzeln \(g^k \bmod n\), wobei \(\gcd(k, \varphi(n)) = 1\) ist, was insgesamt genau \(\varphi(\varphi(n))\) Primitivwurzeln ergibt.

So verwenden Sie den Primitivwurzel-Rechner

1. Modul n eingeben: Geben Sie eine positive ganze Zahl in das Eingabefeld ein oder klicken Sie auf eine der Schaltflächen für Kurzbeispiele, um einen Wert automatisch auszufüllen.
2. Klicken Sie auf Primitivwurzeln finden: Drücken Sie die Schaltfläche, um alle Primitivwurzeln modulo n zu berechnen.
3. Ergebnisse überprüfen: Sehen Sie die Anzahl, die vollständige Liste der Primitivwurzeln, Eulers Phi-Funktion, die Gruppenordnung und ob für Ihr n Primitivwurzeln existieren.
4. Visualisierung erkunden: Für n ≤ 100 zeigt das interaktive zyklische Gruppenrad, wie jede Primitivwurzel durch ihre Potenzen die gesamte Gruppe erzeugt. Klicken Sie auf einen Wurzel-Chip, um den Zyklus auf dem Rad animiert zu sehen.
5. Potenztabelle studieren: Das Gitter zeigt g^k mod n für k = 1, 2, …, φ(n), wobei Primitivwurzeln und das neutrale Element in verschiedenen Farben hervorgehoben sind.

Primitivwurzeln in der Kryptographie

Primitivwurzeln spielen eine zentrale Rolle in der modernen Kryptographie. Beim Diffie-Hellman-Schlüsselaustausch einigen sich zwei Parteien auf eine große Primzahl p und eine Primitivwurzel g mod p und tauschen dann die öffentlichen Schlüssel g^a mod p und g^b mod p aus. Das gemeinsame Geheimnis g^ab mod p ist für einen Lauscher rechnerisch nicht zu bestimmen, da die Berechnung diskreter Logarithmen in großen zyklischen Gruppen als schwierig gilt. Ähnlich basieren die ElGamal-Verschlüsselung und der Digital Signature Algorithm (DSA) beide auf der Schwierigkeit des diskreten Logarithmusproblems in Gruppen, die von Primitivwurzeln erzeugt werden.

FAQ

Andere verwandte Tools:

Erweiterte Rechenoperationen:

• Antilogarithmus Rechner
• Betafunktion-Rechner
• Binomialkoeffizient-Rechner
• Binomialverteilungsrechner
• Binär-Rechner
• Zentraler Grenzwertsatz Rechner
• Kombinatorik-Rechner
• Rechner für komplementäre Fehlerfunktion
• Komplexe Zahlen Rechner
• Entropie-Rechner
• Fehlerfunktion berechnen
• Rechner für exponentiellen Zerfall
• Exponentielle Zunahme Rechner
• Exponentielles Integral Rechner
• exponenten-rechner-hohe-präzision
• Fakultätsrechner
• Gammafunktion-Rechner
• Goldener Schnitt Rechner
• Halbwertszeit berechnen Empfohlen
• Prozentuale Wachstumsrate Rechner Empfohlen
• permutationsrechner
• Poisson-Verteilungsrechner
• Polynom Wurzeln Rechner mit detaillierten Schritten
• Wahrscheinlichkeitsrechner
• Wahrscheinlichkeitsverteilung Rechner
• Anteil-Rechner
• Mitternachtsformel Rechner
• Wissenschaftlicher Taschenrechner Empfohlen
• Wissenschaftliche Schreibweise Rechner
• Signifikante Stellen Rechner Neu
• Summe von Kuben Rechner
• Summe von positiven Ganzzahlen Rechner
• Summe von Quadratzahlen Rechner
• Wahrheitstabellen-Generator Neu
• Mengenlehre-Rechner Neu
• Venn-Diagramm-Generator (3 Mengen) Neu
• Chinesischer Restsatz Rechner Neu
• Euler Totient Funktion Rechner Neu
• Erweiterter Euklidischer Algorithmus Rechner Neu
• Modularer Multiplikativer Inverser Rechner Neu
• Kettenbruch-Rechner Neu
• Dijkstra Kürzester Weg Rechner Neu
• Minimaler Spannbaum Rechner Neu
• Graph Gradfolgen-Validator Neu
• Derangement Subfaktorielle Rechner Neu
• Stirling-Zahlen-Rechner Neu
• Schubfachprinzip-Rechner Neu
• Markov-Ketten Stationäre Verteilung Rechner Neu
• rundungsrechner Neu
• Negativer Binomialverteilungsrechner Neu
• Permutationen mit Wiederholung Rechner Neu
• Modulare Exponentiationsrechner Neu
• Primitivwurzel-Rechner Neu
• Boolesche Algebra Vereinfacher Neu
• Karnaugh-Diagramm (K-Map) Löser Neu
• Graphfärbung Rechner Neu
• Topologische Sortierung Rechner Neu
• Adjazenzmatrix-Rechner Neu
• Inklusions-Exklusions-Rechner Neu
• Solver für lineare Programmierung Neu
• Traveling Salesman Solver (TSP) Neu
• Hamilton-Pfad-Prüfer Neu
• Planarer Graph Prüfer Neu
• Netzwerkfluss-Rechner (Maximaler Fluss) Neu
• Stable Marriage Problem Löser Neu
• Gruppentheorie-Ordnungsrechner Neu
• Ring und Körperrechner Neu