Primitivwurzel-Rechner

Eine Primitivwurzel modulo einer Primzahl p ist ein Generator der multiplikativen Gruppe der von null verschiedenen Reste modulo p. Vereinfacht gesagt hat eine Ganzzahl g zwischen 1 und p minus eins die Eigenschaft, dass ihre aufeinanderfolgenden Potenzen g, g zum Quadrat, g in der dritten Potenz und so weiter schließlich jede zu p teilerfremde Restklasse treffen, bevor sie sich wiederholen. Dieses g ist ein Generator von (Z/pZ)*, und das kleinste solche positive g ist die klassische zahlentheoretische Antwort, die Studierende, Kryptografen und Wettbewerbslöser nachschlagen. Dieser Rechner nimmt einen Primzahlmodul p, verifiziert, dass p prim ist, faktorisiert p minus eins und liefert die kleinste Primitivwurzel zusammen mit der Gruppenordnung und der Primpotenz-Zerlegung von p minus eins. Der Pfad ist vollständig deterministisch: Miller-Rabin mit festen Zeugenmengen, Probedivision und modulare Exponentiation ohne Netzwerk, ohne Zufälligkeit und ohne Datumsabhängigkeit.

Was eine Primitivwurzel ist und was die Antwort enthält

Für einen Primzahlmodul p bildet die Menge der Reste 1, 2, …, p minus eins eine zyklische multiplikative Gruppe der Ordnung p minus eins. Eine Ganzzahl g ist eine Primitivwurzel modulo p, wenn die Ordnung von g in dieser Gruppe genau p minus eins ist: Die Potenzen g hoch k für k von 0 bis p minus zwei sind alle modulo p verschieden und erschöpfen jeden von null verschiedenen Rest.

Nicht jede Ganzzahl ist ein Generator; zum Beispiel durchlaufen die Potenzen von 2 modulo 7 nur drei Werte, bevor sie sich wiederholen, sodass 2 keine Primitivwurzel ist, während 3 alle sechs Einheiten erzeugt und die kleinste ist. Es gibt keine probabilistische Vermutung, die als Wurzel ausgegeben wird, und keinen stillen Fallback für zusammengesetzte Moduln, da eine Primitivwurzel im klassischen Sinn für Primzahlen definiert ist (und für einige spezielle zusammengesetzte Familien, die diese Seite nicht abdeckt).

Wenn Sie Faktoren einer beliebigen Ganzzahl statt eines Generators mod p benötigen, nutzen Sie stattdessen eine Faktorisierungs-Capability; diese Seite beantwortet ausschließlich die Frage nach dem kleinsten Generator mod einer Primzahl.

Wie die Primzahl geprüft wird und wie die kleinste Wurzel gefunden wird

Optionale führende Pluszeichen sind erlaubt; eingebettete Leerzeichen, Hex-Präfixe und Exponentialnotation werden mit einer klaren Meldung zurückgewiesen, damit eine fehlerhafte Zelle nicht zu einem falschen Generator wird. Nach dem Parsen führt die Engine einen deterministischen Miller-Rabin-Primzahltest mit Zeugenmengen aus, die für jede Ganzzahl von höchstens fünfzehn Dezimalstellen als ausreichend erwiesen sind.

Ist p prim, faktorisiert die Engine p minus eins durch Rad-Probedivision, sammelt die verschiedenen Primfaktoren q dieser Ordnung und sucht g gleich 2, 3, 4, … nach dem ersten Kandidaten, sodass g hoch (p minus eins geteilt durch q) für jedes solche q nicht kongruent zu 1 modulo p ist. Dieses klassische Kriterium ist notwendig und hinreichend dafür, dass g die Ordnung p minus eins hat. Der Sonderfall p gleich 2 liefert die Primitivwurzel 1, die einzige Einheit in dieser Gruppe.

Wo kleinste Primitivwurzeln bei Studium, Krypto und Code Anwendung finden

Studierende begegnen Primitivwurzeln, wenn sie zyklische Gruppen, diskrete Logarithmen und die Struktur endlicher Körper von Primzahlordnung lernen. Arbeitsblätter fragen oft nach dem kleinsten Generator modulo einer kleinen Primzahl; diese Seite liefert diese Antwort mit der unterstützenden Zerlegung von p minus eins, sodass Sie die Ordnungstests von Hand verifizieren können. Wettbewerbsprobleme und Programmier-Kata-Aufgaben verlangen häufig die kleinste Primitivwurzel als Unterroutine für den Bau primitiver Polynome, das Indizieren diskreter-Logarithmus-Tabellen oder das Speisen zahlentheoretischer Demos.

In angewandter Kryptografie brauchen Diffie-Hellman und verwandte Konstruktionen einen Generator einer großen Primzahlordnungs-Untergruppe; während Produktionssysteme sorgfältig gewählte sichere Primzahlen und standardisierte Generatoren nutzen, ist ein transparenter Rechner für gewöhnliche Primzahlen dennoch nützlich, wenn Sie Hausaufgaben-große Parameter validieren, Unit-Tests für Werkzeuge zur modularen Ordnung schreiben oder erklären, warum g gleich 2 für manche Primzahlen funktioniert und für andere nicht. Lehrkräfte können Lösungsschlüssel vorab erstellen, ohne undurchsichtigen Web-Widgets zu vertrauen.