Das Jacobi Symbol ist eine Generalisation des Symbols von Legendre. Eingeführt von Jacobi 1837 ist es von theoretischem Interesse in der Modularithmetik und den anderen Zweigen der Zahlentheorie, aber sein Hauptgebrauch ist in der rechenbetonten Zahlentheorie, besonders primality Prüfung und ganze Zahl factorization; diese sind der Reihe nach in der Geheimschrift wichtig.

Definition

Für jede ganze Zahl a und jede positive sonderbare ganze Zahl n das Symbol von Jacobi wird als das Produkt der Symbole von Legendre entsprechend den Hauptfaktoren von n definiert:

:

vertritt das Symbol von Legendre, das für alle ganzen Zahlen a und die ganze sonderbare Blüte p durch definiert ist

:

\left (\frac {p }\\Recht) = \begin {Fälle }\

\; \; \, 0\mbox {wenn} ein \equiv 0 \pmod {p }\

\\+1\mbox {wenn} ein \not\equiv 0\pmod {p} \mbox {und für eine ganze Zahl} x, \; a\equiv x^2\pmod {p }\

\\-1\mbox {wenn es nicht solchen} x. \end {Fälle} </Mathematik> gibt

Im Anschluss an die normale Tagung für das leere Produkt sind Die Symbole von Legendre und Jacobi genau nicht zu unterscheidend, wenn das niedrigere Argument eine sonderbare Blüte ist, in welchem Fall sie denselben Wert haben.

Eigenschaften

Diese Tatsachen, sogar die Reziprozitätsgesetze, sind aufrichtige Abzüge aus der Definition des Symbols von Jacobi und den entsprechenden Eigenschaften des Symbols von Legendre.

Es sollte bemerkt werden, dass das Symbol von Jacobi nur definiert wird, wenn das obere Argument ("Zähler") eine ganze Zahl ist und das niedrigere Argument ("Nenner") eine positive sonderbare ganze Zahl ist.

:1) Wenn (ein sonderbarer) erst ist, dann ist das Symbol von Jacobi auch ein Symbol von Legendre.

:2) Wenn dann

:3)

\begin {Fälle }\

\; \; \, 0\mbox {wenn} \gcd (a, n) \ne 1

\\\pm1\mbox {wenn} \gcd (a, n) = 1\end {Fälle }\

</Mathematik>

:4) so (oder)

:5) so (oder)

Das Gesetz der quadratischen Reziprozität: Wenn M und n sonderbare positive coprime ganze Zahlen, dann sind

:6)

\left (\frac {n} {M }\\Recht) (-1) ^ {\\tfrac {m-1} {2 }\\tfrac {n-1} {2}}

\begin {Fälle }\

\; \; \; \left (\frac {n} {M }\\Recht) & \text {wenn} n \equiv 1 \pmod 4 \text {oder} M \equiv 1 \pmod 4 \\

- \left (\frac {n} {M }\\Recht) & \text {wenn} n\equiv M \equiv 3 \pmod 4

\end {Fälle }\

</Mathematik>

und seine Ergänzungen

:7)

\left (\frac {-1} {n }\\Recht)

(-1) ^\\tfrac {n-1} {2}

\begin {Fälle} \; \; \, 1 & \text {wenn} n \equiv 1 \pmod 4 \\-1 &\\Text {wenn} n \equiv 3 \pmod 4\end {Fälle }\

</Mathematik>

:8)

\left (\frac {2} {n }\\Recht)

(-1) ^\\tfrac {n^2-1} {8}

\begin {Fälle} \; \; \, 1 & \text {wenn} n \equiv 1,7 \pmod 8 \\-1 &\\Text {wenn} n \equiv 3,5\pmod 8\end {Fälle }\

</Mathematik>

Wie das Symbol von Legendre,

:If ist dann ein quadratischer Nichtrückstand

:If ist ein quadratischer Rückstand dann

Aber, verschieden vom Symbol von Legendre

:If kann dann oder kann kein quadratischer Rückstand sein.

Das ist, weil für, um ein Rückstand (mod n) zu sein, es ein Rückstand modulo jede Blüte sein muss, die n teilt, aber das Symbol von Jacobi wird demjenigen gleichkommen, wenn zum Beispiel eines Nichtrückstands für genau zwei der Blüte zu sein, die n teilt.

Obwohl das Symbol von Jacobi in Bezug auf Quadrate und Nichtquadrate nicht gleichförmig interpretiert werden kann, kann es als das Zeichen einer Versetzung durch das Lemma von Zolotarev gleichförmig interpretiert werden.

Das Jacobi Symbol ist ein Charakter von Dirichlet zum Modul n.

Das Rechnen des Symbols von Jacobi

Die obengenannten Formeln führen zu einem effizienten Algorithmus, für das Symbol von Jacobi zu berechnen, das dem Euklidischen Algorithmus analog ist, für den GCD von zwei Zahlen zu finden. (Das sollte im Licht der Regel 3 nicht überraschend sein)).

Der "Zähler" wird modulo der "Nenner" mit der Regel 2 reduziert). Irgendwelche Vielfachen 2 werden mit der Regel 4 herausgezogen), und hat Verwenden-Regel berechnet 8). Das Symbol wird mit der Regel 6 geschnipst), und die Algorithmus-Wiederflüche, bis der "Zähler" 1 (bedeckt durch die Regel 4) ist) oder 2 (bedeckt durch die Regel 8)), oder der "Zähler" dem "Nenner" (Regel 3) gleichkommt).

Beispiel von Berechnungen

Das Legendre Symbol wird nur für die sonderbare Blüte p definiert. Es folgt denselben Regeln wie das Symbol von Jacobi (d. h., Reziprozität und die ergänzenden Formeln für und und multiplicativity des "Zählers".)

Das Verwenden des Symbols von Legendre

:

\left (\frac {1001} {9907 }\\Recht)

\left (\frac {7} {9907 }\\Recht) \left (\frac {11} {9907 }\\Recht) \left (\frac {13} {9907 }\\Recht).

</Mathematik>

::

\left (\frac {7} {9907 }\\Recht)

- \left (\frac {9907} {7 }\\Recht)

- \left (\frac {2} {7 }\\Recht)

- 1

</Mathematik>::

\left (\frac {11} {9907 }\\Recht)

- \left (\frac {9907} {11 }\\Recht)

- \left (\frac {7} {11 }\\Recht)

\left (\frac {11} {7 }\\Recht)

\left (\frac {4} {7 }\\Recht)

1

</Mathematik>::

\left (\frac {13} {9907 }\\Recht)

\left (\frac {9907} {13 }\\Recht)

\left (\frac {1} {13 }\\Recht)

1

</Mathematik>:

Das Verwenden des Symbols von Jacobi

:

\left (\frac {1001} {9907 }\\Recht)

\left (\frac {9907} {1001 }\\Recht)

\left (\frac {898} {1001 }\\Recht)

\left (\frac {2} {1001 }\\Recht) \left (\frac {449} {1001 }\\Recht)

\left (\frac {449} {1001 }\\Recht)

</Mathematik>::

\left (\frac {1001} {449 }\\Recht)

\left (\frac {103} {449 }\\Recht)

\left (\frac {449} {103 }\\Recht)

\left (\frac {37} {103 }\\Recht)

\left (\frac {103} {37 }\\Recht)

</Mathematik>::

\left (\frac {29} {37 }\\Recht)

\left (\frac {37} {29 }\\Recht)

\left (\frac {8} {29 }\\Recht)

\left (\frac {4} {29 }\\Recht) \left (\frac {2} {29 }\\Recht)

- 1.

</Mathematik>

Der Unterschied zwischen den zwei Berechnungen ist, dass, wenn das Symbol von Legendre verwendet wird, der "Zähler" factored in Hauptmächte sein muss, bevor das Symbol geschnipst wird. Das macht die Berechnung mit dem Symbol von Legendre bedeutsam langsamer als dasjenige mit dem Symbol von Jacobi, weil es keinen bekannten polynomisch-maligen Algorithmus für ganze Factoring-Zahlen gibt. Tatsächlich ist das, warum Jacobi das Symbol eingeführt hat.

Prüfung von Primality

Es gibt eine andere Weise, wie sich die Symbole von Jacobi und Legendre unterscheiden. Wenn die Kriterium-Formel von Euler modulo eine zerlegbare Zahl verwendet wird, kann das Ergebnis oder kann nicht der Wert des Symbols von Jacobi sein.

So, wenn es nicht bekannt ist, ob eine Nummer n erst oder zerlegbar ist, können wir eine Zufallszahl a aufpicken, das Symbol von Jacobi berechnen und es mit der Formel von Euler vergleichen; wenn sie sich modulo n unterscheiden, dann ist n zerlegbar; wenn sie derselbe modulo n für viele verschiedene Werte von a sind, dann ist n wahrscheinlich "erst".

Das ist die Basis für den probabilistic Solovay-Strassen primality Test und seine Verbesserung der Müller-Rabin primality Test.

Siehe auch

• Das Kronecker Symbol ist eine Generalisation des Symbols von Jacobi zu allen ganzen Zahlen.

Referenzen

Außenverbindungen

• Rechnen Sie Jacobi Symbol zeigt die Schritte der Berechnung.