Legendre-Symbol (a/p)

Das Legendre-Symbol ist der klassische zahlentheoretische Test auf quadratische Residuizität modulo einer ungeraden Primzahl. Gegeben ein ganzzahliges a und eine ungerade Primzahl p, ist das Symbol (a/p) null, wenn p a teilt, eins, wenn a ein von null verschiedenes Quadrat modulo p ist, und minus eins, wenn a ein quadratisches Nichtresiduum ist. Kryptographie-Kurse, primzahlbezogene Algorithmen, Beweise kubischer und quadratischer Reziprozität sowie Wettbewerbsprogrammieraufgaben stützen sich auf diesen dreiwertigen Indikator. Viele Sprachen bieten modulare Exponentiation, überlassen Residuizitätskonvention und Primprüfung jedoch Ihnen. Dieser Rechner akzeptiert a und p, prüft dass p eine ungerade Primzahl ist, wendet Eulers Kriterium deterministisch an und liefert das Symbol zusammen mit dem reduzierten Residuum von a und einer kurzen Interpretation, sodass Sie das Ergebnis nutzen können ohne die modulare Potenz von Hand neu abzuleiten.

Was das Legendre-Symbol aussagt

Das Legendre-Symbol beantwortet eine einfache Frage: Gibt es eine ganze Zahl, deren Quadrat bei Division durch die ungerade Primzahl p denselben Rest lässt wie a? Ist das so und ist a kein Vielfaches von p, lautet das Symbol 1. Gibt es kein solches Quadrat, lautet es −1. Teilt p die Zahl a, ist das Symbol 0. Von den Resten ungleich null ist genau die Hälfte ein Quadrat, die andere Hälfte nicht. Diese Unterscheidung taucht im quadratischen Reziprozitätsgesetz, in Kryptografiekursen und in Wettbewerbsaufgaben auf.

So wird es berechnet und worauf Sie achten sollten

Der Rechner prüft zuerst, ob p eine ungerade Primzahl zwischen 3 und einer Billion ist, und reduziert a auf einen Rest von 0 bis p minus 1. Dann wendet er das Euler-Kriterium an: a hoch (p − 1)/2 modulo p ergibt 1, p minus 1 oder 0. Diese Potenz wird exakt berechnet, ohne Rundung. Ein typischer Fehler ist, für p die 2 oder eine zusammengesetzte Zahl einzugeben; das Symbol ist dafür nicht definiert, und die Eingabe wird abgelehnt. Ein Ergebnis von 1 sagt außerdem nur, dass eine Quadratwurzel existiert, nicht welche.

Was das Legendre-Symbol bedeutet und warum es zählt

In der modularen Arithmetik ist die Frage „gibt es eine ganze Zahl x mit x im Quadrat kongruent zu a modulo p?“ grundlegend. Ist p eine ungerade Primzahl, fällt die Antwort in drei saubere Fälle.

Ist a durch p teilbar, wird das Symbol als null definiert. Ist a nicht durch p teilbar, sind die Hälfte der von null verschiedenen Reste Quadrate (quadratische Residuen) und die andere Hälfte Nichtresiduen; das Legendre-Symbol ist plus eins für Residuen und minus eins für Nichtresiduen. Diese Trichotomie erscheint im Gesetz der quadratischen Reziprozität, in Beweisen dass bestimmte diophantische Gleichungen keine Lösungen haben, in der Analyse des Tonelli–Shanks-Quadratwurzelalgorithmus und in Lehrbuchdarstellungen der Primideen von Miller–Rabin und Solovay–Strassen, die Eulers Kriterium mit einem behaupteten Jacobi-Wert vergleichen.

Wie dieser Rechner (a/p) mit Eulers Kriterium auswertet

Rufen Sie die Fähigkeit mit den ganzzahligen Feldern a und p auf, wobei p eine ungerade Primzahl zwischen drei und einer Billion einschließlich sein muss und a eine ganze Zahl mit Absolutbetrag höchstens einer Billion. Die Implementation validiert zuerst Typen und Grenzen und führt dann einen deterministischen Probedivisions-Primtest auf p aus. Eulers Kriterium besagt, dass a hoch (p minus eins) geteilt durch zwei modulo p dem Legendre-Symbol kongruent ist.

Der Rechner berechnet diese modulare Potenz mit exakter BigInt-Arithmetik, sodass Zwischenprodukte innerhalb der veröffentlichten Grenzen nie Präzision verlieren. Ist die Potenz eins, ist das Symbol eins. Ist die Potenz p minus eins, ist das Symbol minus eins.