n-ter Potenzrest

Eine ganze Zahl a ist ein k-ter Potenzrest modulo einer Primzahl p, wenn es eine ganze Zahl x gibt, sodass x hoch k kongruent zu a modulo p ist. Diese Frage verallgemeinert die quadratische Residuizität (den Fall k gleich zwei) auf Kuben, höhere Potenzen und beliebige positive Exponenten, wie sie in Wettbewerbs-Zahlentheorie und einführender Kryptographie vorkommen. Diese Fähigkeit nimmt einen Kandidaten a, einen positiven Exponenten k und einen Primmodul p entgegen, reduziert a auf den Bereich von null bis p minus eins, prüft, dass p prim ist, und wendet das Standardkriterium der zyklischen Gruppe auf die multiplikative Gruppe des Körpers mit p Elementen an. Wenn a durch p teilbar ist, lautet die Antwort für k mindestens eins stets ja, weil null zu jeder positiven Potenz null ist.

Was ein k-ter Potenzrest modulo einer Primzahl bedeutet

Fixieren Sie einen Primmodul p und eine positive ganze Zahl k. Die Restklassen modulo p bilden einen Körper, und ihre von null verschiedenen Elemente bilden eine zyklische multiplikative Gruppe der Ordnung p minus eins. Eine durch p nicht teilbare ganze Zahl a ist genau dann ein k-ter Potenzrest modulo p, wenn a im Bild der Abbildung liegt, die jede von null verschiedene Klasse x auf x hoch k schickt.

Weil die Gruppe zyklisch ist, ist dieses Bild die eindeutige Untergruppe vom Index gleich dem größten gemeinsamen Teiler d von k und p minus eins, und a gehört genau dann zu dieser Untergruppe, wenn a hoch (p minus eins) geteilt durch d kongruent zu eins modulo p ist. Diese eine modulare Exponentiation ist das hier verwendete Entscheidungsverfahren.

Wenn a durch p teilbar ist, hat die Kongruenz x hoch k kongruent zu a für jedes k mindestens eins die triviale Lösung x kongruent zu null, sodass null stets als k-ter Potenzrest behandelt wird. Spezialfälle liefern bekannte Werkzeuge: für k gleich zwei und ungerade Primzahl p ist das Kriterium Eulers Kriterium der quadratischen Residuizität — dieselbe Information wie im Legendre-Symbol — während für k gleich p minus eins jedes von null verschiedene a nach dem kleinen Satz von Fermat ein Rest ist.

Der Endpunkt erfindet keine Gleitkommawurzeln und keine genäherten Potenzen; er nutzt nur exakte ganzzahlige Modulararithmetik, damit Lehrbuchantworten und automatisierte Tests bitgenau übereinstimmen.

Eingabevertrag, Primzahlprüfung und Antwortfelder

Senden Sie die ganzen Zahlen a, k und p. Der Exponent k muss mindestens eins und höchstens eine Billion (10^12) sein. Optionale Feldnamen werden nie mit null gefüllt: das Kriteriumspaar wird im Nullrestfall einfach weggelassen.

Klassische Prüfungen, die Sie von Hand nachvollziehen können: für a gleich zwei, k gleich drei und p gleich sieben ist der gcd von drei und sechs drei, also ist der Kriteriumsexponent zwei und zwei zum Quadrat ist vier modulo sieben, nicht eins; folglich ist zwei kein kubischer Rest modulo sieben; dagegen ist eins für jede Primzahl stets ein k-ter Potenzrest, weil eins zu jeder Potenz eins ist. Nichtganzzahlen, fehlende Pflichtfelder und Exponenten unter eins scheitern an der Validierung mit einer klaren englischen Meldung.

Wo Prüfungen höherer Potenzreste in der Praxis vorkommen

Wettbewerbsprogrammierer brauchen ein schnelles Orakel, bevor sie versuchen, modulare Kubikwurzeln oder höhere Wurzeln zu extrahieren: ist das Restbit falsch, lohnt die Suche nach x nicht. Kryptographie-Studierende prüfen Übungen zum Bild der Potenzabbildung in endlichen Körpern, Indexkalkül-Beispiele und Spielzeugkonstruktionen, die davon abhängen, ob eine Nachrichtenklasse eine k-te Potenz ist, bevor eine Abbildung angewendet wird. Forschungs- und Hausaufgabenpipelines, die bereits Legendre- oder Jacobi-Symbole für Quadrate nutzen, brauchen oft dieselbe Ja-Nein-Antwort für Kuben und höhere Potenzen, ohne die Bibliothek zu wechseln.

Wenn Sie nur quadratische Residuizität benötigen, bleiben die speziellen Werkzeuge für quadratische Reste und das Legendre-Symbol verfügbar; diese Seite ist die allgemeine k-te-Potenz-Entscheidung für Primmoduln.