Modulare n-te Wurzel

Eine modulare k-te Wurzel einer ganzen Zahl a modulo einer Primzahl p ist jeder Rest x, für den x hoch k kongruent zu a modulo p ist. Quadratwurzeln modulo Primzahlen erscheinen in Tonelli–Shanks-Tutorials, kubische und höhere Wurzeln in der Algebra endlicher Körper, und Kryptografie-Kurse brauchen ein verlässliches Orakel, das entweder alle Wurzeln auflistet oder klar ablehnt, wenn keine existieren. Dieser Rechner nimmt a, einen positiven Exponenten k und einen Primmodul p entgegen, reduziert a in den kanonischen Bereich von null bis p minus eins und liefert die vollständige geordnete Lösungsliste in diesem Körper.

Was modulare k-te Wurzeln sind und wann sie existieren

In der multiplikativen Gruppe eines Primkörpers hat jeder von null verschiedene Rest eine wohldefinierte Ordnung, die p minus eins teilt. Das Erheben von x zur k-ten Potenz ergibt eine Abbildung, deren Bild die Menge der k-ten Potenzreste ist. Für ein von null verschiedenes Ziel a hat die Kongruenz x hoch k kongruent a modulo p genau dann Lösungen, wenn a hoch (p minus eins) geteilt durch d kongruent eins ist, wobei d der größte gemeinsame Teiler von k und p minus eins ist.

Gilt dieses Kriterium, gibt es genau d verschiedene von null verschiedene Wurzeln. Der Nullrest ist besonders: null zu jeder positiven Potenz ist null, also hat a kongruent null die einzige Wurzel null. Zusammengesetzte Moduln liegen außerhalb dieses zyklischen Gruppenbildes und werden abgelehnt, damit der Solver nie so tut, als wäre ein Produkt nach dem chinesischen Restsatz eine Antwort im Primkörper.

Studierende begegnen Quadratwurzeln beim manuellen Prüfen von Legendre-Symbolen, höheren Wurzeln beim Studium zyklotomischer Nebenklassen oder diskreter Logarithmen und Existenzfehlern, wenn eine Hausaufgabe die Kubikwurzel eines nicht-kubischen Rests verlangt.

Wie dieser Rechner jede Wurzel findet

Rufen Sie die Fähigkeit mit den ganzzahligen Feldern a, k und p auf. Die Implementierung prüft zuerst, dass k eine positive ganze Zahl und p eine Primzahl innerhalb der veröffentlichten Grenze ist, mittels deterministischem Miller–Rabin-Test. Nach Reduktion von a modulo p liefert der Nullrest-Fall die einzige Wurzel null.

Für von null verschiedenes a berechnet sie d gleich dem ggT von k und p minus eins und wendet den Existenztest oben an. Ist d gleich eins, gibt es eine eindeutige Wurzel durch Erheben von a zur modularen Inversen von k modulo p minus eins — der Schnellpfad für teilerfremde Exponenten.

Ist d größer als eins, findet der Solver eine Primitivwurzel g modulo p, ermittelt den diskreten Logarithmus von a zur Basis g mit baby-step giant-step und löst die lineare Kongruenz k mal y kongruent diesem Logarithmus modulo p minus eins. Jede zurückgegebene Wurzel wird per modularer Exponentiation geprüft, bevor die Antwort gesendet wird. Absolutbeträge von a und k sind durch eine Billion begrenzt und die Primzahl p nahe einer Milliarde, damit baby-step-giant-step-Speicher praktikabel bleibt; würde d zehntausend Wurzeln überschreiten, wird die Anfrage abgelehnt statt den Client zu überfluten.