imported>PurpleXanadu: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-09-15T13:18:48Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

Das '''Jacobi-Symbol''', benannt nach [[Carl Gustav Jacob Jacobi]], ist eine Verallgemeinerung des [[Legendre-Symbol]]s. Das Jacobi-Symbol kann wiederum zum [[Kronecker-Symbol]] verallgemeinert werden. Die Notation ist die gleiche wie die des ''Legendre-Symbols'':

:<math>\left(\frac an\right)</math> oder auch <math>(a/n)</math>

Um zwischen dem Legendre-Symbol und dem Jacobi-Symbol zu unterscheiden, schreibt man auch <math>L(a,p)</math> und <math>J(a,n)</math>.

Dabei muss <math>n</math> im Gegensatz zum Legendre-Symbol keine [[Primzahl]] sein, allerdings muss es eine ungerade [[natürliche Zahl]] sein. Für <math>a</math> sind beim Jacobi-Symbol wie beim Legendre-Symbol alle ganzen Zahlen zugelassen.

== ''n'' ist eine Primzahl ==
Falls <math>n</math> eine Primzahl ist, ist das ''Jacobi-Symbol'' nach Definition gleich dem Legendre-Symbol:
:<math>\left(\frac{a}{n}\right) = \begin{cases} 1 & \mbox{wenn } a \mbox{ ein quadratischer Rest modulo } n \mbox{ ist} \\ -1 & \mbox{wenn }a\mbox{ ein quadratischer Nichtrest modulo }n\mbox{ ist} \\ 0 & \mbox{wenn }n\mbox{ ein Teiler von }a\mbox{ ist (also } a \mbox{ kongruent } 0 \mbox{ modulo } n \mbox{)}\end{cases}</math>

== ''n'' ist keine Primzahl ==
Ist die [[Primfaktorzerlegung]] von <math>n=p_1^{\nu_1}\cdot p_2^{\nu_2}\cdots p_k^{\nu_k}</math>, so definiert man
:<math>\left(\frac{a}{n}\right)=\left(\frac{a}{p_1}\right)^{\nu_1}\cdots \left(\frac{a}{p_k}\right)^{\nu_k}.</math>

Für <math>n = 1</math> wird üblicherweise <math>\left(\frac{a}{1}\right) = 1</math> gesetzt (leeres Produkt).

Beispiel:
:<math>\left(\frac{11}{91}\right)=\left(\frac{11}{7}\right)\cdot \left(\frac{11}{13}\right)=\left(\frac{4}{7}\right)\cdot \left(\frac{11}{13}\right)=1\cdot(-1)=-1</math>

'''Achtung:''' Falls <math>n</math> keine Primzahl ist, gibt das Jacobi-Symbol nicht an, ob <math>a</math> ein [[quadratischer Rest]] modulo <math>n</math> ist (wie beim Legendre-Symbol). Eine ''notwendige'' Bedingung dafür, dass <math>a</math> ein quadratischer Rest modulo <math>n</math> ist, ist allerdings, dass das Jacobi-Symbol ungleich <math>-1</math> ist. Beispielsweise erhält man für vier verschiedene Reste a modulo 15 für
:<math>\left(\frac{a}{15}\right)</math>
den Wert 1, jedoch sind nur zwei davon Quadrate modulo 15 (man erhält für 1, 2, 4, 8 den Wert 1, Quadrate sind nur 1 und 4). Den Wert 0 erhält man siebenmal (0, 3, 5, 6, 9, 10, 12), davon sind aber auch nur vier Quadrate (0, 6, 9, 10). Übrig bleiben die vier Werte, für die man -1 erhält (7, 11, 13, 14), hier erhält man, wie bereits angesprochen, niemals ein Quadrat.

== Allgemeine Definition ==
Allgemein ist das Jacobi-Symbol <math>J(a, n)</math> über einen [[Charakter (Mathematik)|Charakter]] <math>\chi_n</math> der Gruppe <math>\mathbb{Z}/n\mathbb{Z}</math> definiert:
:<math>\left(\frac{a}{n}\right) := \begin{cases} \chi_n(a + n\mathbb{Z}) & \mbox{falls ggT}(a, n) = 1\\ 0 & \mbox{sonst}\end{cases}</math>
Dabei ist <math>\chi_n(a + n\mathbb{Z})</math> die folgende Funktion:
:<math>\chi_n(a + n\mathbb{Z}) := \prod_{x \in H}\varepsilon_x(a)</math>
<math>H</math> ist dabei ein beliebiges [[Halbsystem]] modulo <math>n</math>, da der Wert von <math>\chi_n</math> nicht von der Wahl des Halbsystems abhängt. <math>\varepsilon_x(a)</math> bezeichnet den ''Korrekturfaktor'' von <math>a</math> und <math>x</math> bezüglich <math>H</math>:
:<math>\varepsilon_x(a) := \begin{cases}1 & \mbox{falls } x \mbox{ und } a \cdot x \mbox{ im gleichen Halbsystem liegen}\\ -1 & \mbox{sonst}\end{cases}</math>

Eine alternative Definitionsmöglichkeit liefert das [[Lemma von Zolotareff]], nach dem das Jacobi-Symbol gleich dem [[Vorzeichen (Permutation)|Vorzeichen]] einer speziellen [[Permutation]] ist.

== Geschlossene Darstellung ==
Die folgende Formel ist eine geschlossene Darstellung des Werts des Jacobi-Symbols:
:<math>\left(\frac{a}{n}\right) = \prod_{k=1}^{\frac12(n-1)}\prod_{h=1}^{\frac12(a-1)}\sgn\left(\left(\frac kn - \frac ha\right)\left(\frac kn + \frac ha - \frac12\right)\right)</math>
Zur effektiven Berechnung ist diese Formel jedoch wenig geeignet, da sie für größere <math>a, n</math> schnell sehr viele Faktoren aufweist.

== Effiziente Berechnung des Jacobi-Symbols ==
In den meisten Fällen, in denen man die Berechnung des Jacobi-Symbols benötigt, so beim ''[[Solovay-Strassen-Test]]'', hat man keine Primfaktorzerlegung der Zahl <math>n</math> in <math>J(a,n)</math>, sodass sich das Jacobi-Symbol nicht auf das Legendre-Symbol zurückführen lässt. Zudem ist die oben angegebene geschlossene Darstellung für größere <math>a, n</math> nicht effizient genug.

Es gibt jedoch ein paar Rechenregeln, mit denen sich <math>J(a,n)</math> effizient bestimmen lässt. Diese Regeln ergeben sich unter anderem aus dem [[Quadratisches Reziprozitätsgesetz|quadratischen Reziprozitätsgesetz]], das auch für das Jacobi-Symbol seine Gültigkeit besitzt.

Das wichtigste Prinzip ist das folgende: Für alle ungeraden ganzen Zahlen <math>m, n</math> größer 1 gilt:

:<math>\left(\frac mn\right) = (-1)^{\frac{(m-1)}{2}\frac{(n-1)}{2}}\left(\frac nm\right)</math>

Diese Regel ist das quadratische Reziprozitätsgesetz für das Jacobi-Symbol. Mit ihrer Hilfe, sowie wenigen weiteren Rechenregeln, lässt sich <math>J(a, b)</math> für alle <math>a, b </math> mit verhältnismäßig geringem Aufwand bestimmen, der vergleichbar mit dem des [[Euklidischer Algorithmus|euklidischen Algorithmus]] zur Bestimmung des größten gemeinsamen Teilers ist. Die Rechenregeln, die zusätzlich benötigt werden, sind die folgenden:
* <math>\left(\frac2n\right) = (-1)^{\frac{n^2-1}8} = \begin{cases} 1, & n \equiv \pm 1 \pmod 8 \\ -1, & n \equiv\pm 3 \pmod 8 \end{cases}</math>
* <math>\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}2}</math>
* <math>\left(\frac1n\right) = 1</math>
* <math>\left(\frac an\right) = \left(\frac{a \;\mathrm{mod}\; n}n\right)</math>
Die oben stehende Regel folgt aus der Definition des Jacobi-Symbol über den [[Charakter (Mathematik)|Charakter]]. Der Zähler des Jacobi-Symbols ist nur ein Repräsentant der Gruppe <math>a + n\mathbb{Z}</math>; daher spielt es keine Rolle, welchen Repräsentanten man wählt.
* <math>\left(\frac{ab}{n}\right) = \left(\frac an\right)\cdot\left(\frac bn\right)</math> (Multiplikativität im Zähler)
* <math>\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\cdot\left(\frac{a}{n}\right)</math> (Multiplikativität im Nenner)

Als Beispiel soll <math>J(127, 703)</math> bestimmt werden:
:<math>\left(\frac{127}{703}\right) = (-1)^{\frac{126}{2}\frac{702}{2}}\left(\frac{703}{127}\right) = -\left(\frac{703}{127}\right)</math>
Da man den Repräsentanten im Zähler frei wählen darf, ist dies gleich
:<math>-\left(\frac{68}{127}\right) = -\left(\frac{2}{127}\right)^2 \cdot \left(\frac{17}{127}\right)</math>
Da 2 zu 127 [[teilerfremd]] ist, ist J(2, 127) sicher nicht 0 und damit J(2, 127)<sup>2</sup> = 1. Also fällt dieser Faktor weg und man erhält:
:<math>-\left(\frac{17}{127}\right) = -(-1)^{\frac{126}{2}\frac{16}{2}}\left(\frac{127}{17}\right) = -\left(\frac{127}{17}\right) = -\left(\frac{8}{17}\right) = -\left(\frac{2}{17}\right)^3</math>
Für die 2 im Zähler gibt es eine geschlossene Formel, daher erhält man schließlich:
:<math>\left(\frac{127}{703}\right) = -\left((-1)^{\frac{17^2-1}8}\right)^3 = -1</math>

== Algorithmus – Berechnung des Jacobi-Symbols (a/b) ==
{| class="wikitable"
|'''1'''
| colspan="8" | '''Eingabe''' <math>x \gets a,\, y \gets b</math>
|-
|'''2'''
| colspan="8" | <math>J \gets 1</math>
|-
|'''3'''
| colspan="8" | '''if''' <math>y = 1</math> '''then''' <math>x \gets 1</math>
|-
|'''4'''
| colspan="8" | '''while''' <math>x \neq 1</math> '''and''' <math>J \neq 0</math> '''do'''
|-
|'''5'''
|
| colspan="7" | '''Berechne''' <math>q \in \mathbb{Z}, \, r \in \mathbb{N}_0, \text{ wobei } x = q \cdot y + r \text{ und } 0 \le r < y</math>
|-
|'''6'''
|
| colspan="7" | '''if''' <math>r = 0</math> '''then''' <math>J \gets 0</math>
|-
|'''7'''
|
| colspan="7" | '''else'''
|-
|'''8'''
|
|
| colspan="6" | '''Berechne''' <math>k, x' \in \mathbb{N}_0, \text{ wobei } r = 2^k \cdot x' \text{ und } x' \text{ ungerade}</math>
|-
|'''9'''
|
|
| colspan="6" | '''if''' <math>k \equiv 1 \text{ mod } 2</math> '''and''' <math>y \equiv \pm 3 \text{ mod } 8</math> '''then''' <math>J \gets -J</math>
|-
|'''10'''
|
|
| colspan="6" | '''if''' <math>x' = 1</math> '''then''' <math>x \gets 1</math>
|-
|'''11'''
|
|
| colspan="6" | '''else'''
|-
|'''12'''
|
|
|
| colspan="5" | '''if''' <math>\frac{x'-1}{2} \cdot \frac{y-1}{2} \equiv 1 \text{ mod } 2</math> '''then''' <math>J \gets -J</math>
|-
|'''13'''
|
|
|
| colspan="5" | <math>x \gets y</math>
|-
|'''14'''
|
|
|
| colspan="5" | <math>y \gets x'</math>
|-
|'''15'''
| colspan="8" | '''Ausgabe''' <math>J</math>
|}

== Literatur ==
* Armin Leutbecher: ''Zahlentheorie''. Springer-Verlag, 1996, ISBN 3-540-58791-8.

{{SORTIERUNG:Jacobisymbol}}
[[Kategorie:Zahlentheorie]]
[[Kategorie:Carl Gustav Jacob Jacobi als Namensgeber]]

Jacobi-Symbol - Versionsgeschichte

imported>PurpleXanadu: /* growthexperiments-addlink-summary-summary:1|0|0 */