Jacobi-Symbol-Rechner

Das Jacobi-Symbol (a/n) erweitert das Legendre-Symbol von Primmoduln auf jede ungerade positive ganze Zahl n. Es liefert 0, wenn a und n einen gemeinsamen Teiler größer als eins teilen, und sonst +1 oder −1 gemäß dem Produkt der Legendre-Symbole über die Primfaktoren von n — ohne dass Sie n zuvor faktorisieren müssen. Dieser Rechner implementiert den klassischen Algorithmus der quadratischen Reziprozität: Zweierpotenzen aus dem Zähler entfernen, das Ergänzungsgesetz für (2/n) anwenden, bei beiden Seiten 3 mod 4 mit dem Reziprozitätszeichen tauschen und reduzieren.

Was das Jacobi-Symbol (a/n) bedeutet

Für eine ungerade positive ganze Zahl n und beliebiges ganzzahliges a ist das Jacobi-Symbol (a/n) multiplikativ aus dem Legendre-Symbol definiert. Ist n eine ungerade Primzahl p, stimmt Jacobi mit Legendre überein: (a/p) ist 0, wenn p a teilt, +1, wenn a ein von null verschiedenes quadratisches Residuum modulo p ist, und −1, wenn a ein quadratisches Nichtresiduum modulo p ist. Faktorisiert sich n als Produkt ungerader Primzahlen, ist (a/n) das Produkt der Legendre-Symbole von a an diesen Primzahlen (mit Vielfachheit).

Folglich gilt (a/n) = 0 genau dann, wenn gcd(a, n) größer als eins ist; ist das Symbol −1, so ist a kein Quadrat mod n; ist es jedoch +1, kann a bei zusammengesetztem n trotzdem kein Quadrat sein — Jacobi ist eine notwendige Bedingung der quadratischen Residuizität, nicht immer eine hinreichende.

Der Wert ist in beiden Argumenten vollständig multiplikativ (mit den üblichen Einschränkungen zum Definitionsbereich von n), und die Gesetze der quadratischen Reziprozität liefern eine effiziente Auswertung: a modulo n auf ein nichtnegatives Residuum reduzieren, Zweierfaktoren mit (2/n) = (−1)^((n²−1)/8) abtrennen, und wenn beide aktuellen ungeraden Teile 3 mod 4 sind, bei jedem Tausch das laufende Vorzeichen umkehren. Dieses Verfahren faktorisiert n nie und endet in logarithmisch vielen arithmetischen Schritten; deshalb teilen Handrechnungen und Maschinenimplementierungen denselben Lehrbuchalgorithmus.

Negative Zähler werden vor der Schleife ins Standard-Residuensystem reduziert, sodass (−1/n) automatisch dem Ergänzungsgesetz (−1)^((n−1)/2) folgt. Diese Fähigkeit lehnt gerades n und n unter 1 ab, weil das klassische Jacobi-Symbol für solche Nenner nicht definiert ist; das Kronecker-Symbol erweitert den Begriff, ist aber ein anderes Werkzeug mit anderer Suchintention.

Grenzen, Leistung und Einsatzorte

Der Reziprozitätsalgorithmus führt pro Bit der Eingaben eine konstante Menge modularer Arithmetik aus, sodass die Kosten mit der Bitlänge von n skalieren und nicht mit einer Probedivisionsfaktorisierung von n. Lehrkräfte nutzen es, um Handrechnungen von (a/n) zu prüfen, bevor Studierende Beweise abgeben. Entwickler binden es in Property-Tests für Gerüste im Solovay–Strassen-Stil, in Puzzle- und CTF-Löser, die einen schnellen quadratischen Charakter brauchen, und in Pipelines ein, die Reziprozität nicht in jeder Sprache neu implementieren sollen.