Primitivwurzel-Suche modulo n

Primitivwurzel-Suche modulo n | Kostenloses Online-Tool | Elysia Tools

Leitfaden zur Tool-Nutzung

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Kategorie: Math & Numbers
Eingabetypen: text, select
Ausgabetyp: text
Sample-Abdeckung: 4
API bereit: Ja

Überblick

Die Primitivwurzel-Suche ermittelt Primitivwurzeln modulo n für Werte bis 10¹², prüft die Zyklizität der multiplikativen Gruppe (mod n) und verifiziert spezifische Kandidaten anhand der Eulerschen φ-Funktion.

Wann verwenden

Wenn Sie den kleinsten Erzeuger (Primitivwurzel) für kryptografische Verfahren wie Diffie-Hellman oder diskrete Logarithmen bestimmen müssen.
Wenn Sie überprüfen wollen, ob für ein gegebenes n ∈ {2, 4, p^k, 2p^k} überhaupt Primitivwurzeln existieren.
Wenn Sie einen konkreten Kandidaten g auf Primitivwurzel-Eigenschaft modulo n mit Prüfzertifikat testen möchten.

So funktioniert es

1Geben Sie den Modul n (2 ≤ n ≤ 10¹²) ein und wählen Sie den gewünschten Ausgabemodus (Kleinste Wurzel, Liste oder Verifikation).
2Das Tool prüft die Primfaktorzerlegung und stellt fest, ob die multiplikative Gruppe zyklisch ist.
3Für jeden Primteiler q von φ(n) wird die Bedingung g^(φ(n)/q) ≢ 1 (mod n) ausgewertet, um Primitivwurzeln exakt zu zertifizieren oder den Kandidaten g zu prüfen.

Anwendungsfälle

Kryptografische Parameterwahl bei der Implementierung von Schlüsseltausch-Protokollen (z. B. Diffie-Hellman).
Lösung von Übungsaufgaben und Beweisen in der universitären Zahlentheorie und Algebra.
Analyse der Periodenlänge und Erzeugereigenschaften in modularen Pseudozufallszahlengeneratoren.

Beispiele

1. Erzeugerliste für Primzahl 23

Mathematikstudent

Hintergrund

In einer Algebra-Vorlesung sollen alle Erzeuger der multiplikativen Gruppe modulo 23 bestimmt werden.

Aufgabe

Manuelle Berechnung aller 10 Primitivwurzeln und deren Zertifikate ist fehleranfällig.

Verwendung

Modul n = 23 eingeben und den Modus 'Zusätzlich Primitivwurzeln auflisten (bis 50)' auswählen.

n = 23, mode = list

Ergebnis

Das Tool zeigt φ(23) = 22, ermittelt 5 als kleinste Wurzel mit Zertifikat und listet alle 10 Primitivwurzeln auf (5, 7, 10, 11, 14, 15, 17, 19, 20, 21).

2. Verifikation eines Erzeugerkandidaten modulo 41

Sicherheitsentwickler

Hintergrund

Für ein kryptografisches Protokoll soll g = 2 als Basis modulo 41 verwendet werden.

Aufgabe

Es muss sichergestellt werden, dass 2 eine Primitivwurzel ist und die volle Gruppenordnung 40 besitzt.

Verwendung

Modul n = 41, Modus 'Einen Kandidaten g prüfen' und Kandidat g = 2 setzen.

FAQ

Für welche Moduln n existieren überhaupt Primitivwurzeln?

Eine Primitivwurzel existiert genau dann, wenn n die Form 2, 4, p^k oder 2·p^k besitzt, wobei p eine ungerade Primzahl und k ≥ 1 ist.

Wie viele Primitivwurzeln gibt es modulo n?

Wenn die Gruppe zyklisch ist, beträgt die Anzahl der Primitivwurzeln exakt φ(φ(n)), berechnet über die Eulersche Phi-Funktion.

Was besagt das Zertifikat g^(φ/q) ≢ 1 (mod n)?

Es beweist, dass die Ordnung des Elements g nicht kleiner als φ(n) ist, indem alle maximalen echten Teilerordnungen ausgeschlossen werden.

Bis zu welcher Zahlengröße werden Berechnungen unterstützt?

Das Tool unterstützt Moduln bis n ≤ 10¹² über Probedivision und zahlentheoretische Faktorisierung.

Kann ich einen beliebigen Kandidaten g testen?

Ja, im Modus 'Einen Kandidaten g prüfen' wird der Wert modulo n reduziert und für jeden Primfaktor von φ(n) auf Ordnungsgleichheit mit φ(n) getestet.

n = 41, mode = verify, g = 2

Dieses Tool ausführen

Beispiele zu diesem Tool

Mit verwandten Tools und Themen fortfahren

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Überblick

Wann verwenden

So funktioniert es

Anwendungsfälle

Beispiele

1. Erzeugerliste für Primzahl 23

2. Verifikation eines Erzeugerkandidaten modulo 41

FAQ

Web Python Bildverarbeitung Beispiele

Android Java Bildverarbeitungsbeispiele

Android Kotlin Bildverarbeitungsbeispiele

Web Rust Bildverarbeitungsbeispiele

Quadratrest-Prüfer (Legendre-/Jacobi-Symbole)

Säure-Basen-Analyse des Blutgases (AG / ΔAG)

DNA-Konzentrationsrechner (A260-Absorption)

OD260/230-Reinheitsrechner (Salz-/Lösungsmittelkontamination)