Jacobi-Symbol

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

${\displaystyle \left({\frac {a}{n}\right)}$ oder auch ${\displaystyle (a/n)}$

Um zwischen dem Legendre-Symbol und dem Jacobi-Symbol zu unterscheiden, schreibt man auch ${\displaystyle L(a,p)}$ und ${\displaystyle J(a,n)}$.

Dabei muss ${\displaystyle n}$ im Gegensatz zum Legendre-Symbol keine Primzahl sein, allerdings muss es eine ungerade natürliche Zahl sein. Für ${\displaystyle a}$ sind beim Jacobi-Symbol wie beim Legendre-Symbol alle ganzen Zahlen zugelassen.

Falls ${\displaystyle n}$ eine Primzahl ist, ist das Jacobi-Symbol nach Definition gleich dem Legendre-Symbol:

${\displaystyle \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}$

Ist die Primfaktorzerlegung von ${\displaystyle n=p_{1}^{\nu _{1}\cdot p_{2}^{\nu _{2}\cdots p_{k}^{\nu _{k}$, so definiert man

${\displaystyle \left({\frac {a}{n}\right)=\left({\frac {a}{p_{1}\right)^{\nu _{1}\cdots \left({\frac {a}{p_{k}\right)^{\nu _{k}.}$

Für ${\displaystyle n=1}$ wird üblicherweise ${\displaystyle \left({\frac {a}{1}\right)=1}$ gesetzt (leeres Produkt).

Beispiel:

${\displaystyle \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}$

Achtung: Falls ${\displaystyle n}$ keine Primzahl ist, gibt das Jacobi-Symbol nicht an, ob ${\displaystyle a}$ ein quadratischer Rest modulo ${\displaystyle n}$ ist (wie beim Legendre-Symbol). Eine notwendige Bedingung dafür, dass ${\displaystyle a}$ ein quadratischer Rest modulo ${\displaystyle n}$ ist, ist allerdings, dass das Jacobi-Symbol ungleich ${\displaystyle -1}$ ist. Beispielsweise erhält man für vier verschiedene Reste a modulo 15 für

${\displaystyle \left({\frac {a}{15}\right)}$

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.

Allgemein ist das Jacobi-Symbol ${\displaystyle J(a,n)}$ über einen Charakter ${\displaystyle \chi _{n}$ der Gruppe ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ definiert:

${\displaystyle \left({\frac {a}{n}\right):={\begin{cases}\chi _{n}(a+n\mathbb {Z} )&{\mbox{falls ggT}(a,n)=1\\0&{\mbox{sonst}\end{cases}$

Dabei ist ${\displaystyle \chi _{n}(a+n\mathbb {Z} )}$ die folgende Funktion:

${\displaystyle \chi _{n}(a+n\mathbb {Z} ):=\prod _{x\in H}\varepsilon _{x}(a)}$

${\displaystyle H}$ ist dabei ein beliebiges Halbsystem modulo ${\displaystyle n}$, da der Wert von ${\displaystyle \chi _{n}$ nicht von der Wahl des Halbsystems abhängt. ${\displaystyle \varepsilon _{x}(a)}$ bezeichnet den Korrekturfaktor von ${\displaystyle a}$ und ${\displaystyle x}$ bezüglich ${\displaystyle H}$:

${\displaystyle \varepsilon _{x}(a):={\begin{cases}1&{\mbox{falls }x{\mbox{ und }a\cdot x{\mbox{ im gleichen Halbsystem liegen}\\-1&{\mbox{sonst}\end{cases}$

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

Die folgende Formel ist eine geschlossene Darstellung des Werts des Jacobi-Symbols:

${\displaystyle \left({\frac {a}{n}\right)=\prod _{k=1}^{\frac {1}{2}(n-1)}\prod _{h=1}^{\frac {1}{2}(a-1)}\operatorname {sgn} \left(\left({\frac {k}{n}-{\frac {h}{a}\right)\left({\frac {k}{n}+{\frac {h}{a}-{\frac {1}{2}\right)\right)}$

Zur effektiven Berechnung ist diese Formel jedoch wenig geeignet, da sie für größere ${\displaystyle a,n}$ schnell sehr viele Faktoren aufweist.

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 ${\displaystyle n}$ in ${\displaystyle J(a,n)}$, 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 ${\displaystyle a,n}$ nicht effizient genug.

Es gibt jedoch ein paar Rechenregeln, mit denen sich ${\displaystyle J(a,n)}$ effizient bestimmen lässt. Diese Regeln ergeben sich unter anderem aus dem 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 ${\displaystyle m,n}$ größer 1 gilt:

${\displaystyle \left({\frac {m}{n}\right)=(-1)^{\frac {(m-1)}{2}{\frac {(n-1)}{2}\left({\frac {n}{m}\right)}$

Diese Regel ist das quadratische Reziprozitätsgesetz für das Jacobi-Symbol. Mit ihrer Hilfe, sowie wenigen weiteren Rechenregeln, lässt sich ${\displaystyle J(a,b)}$ für alle ${\displaystyle a,b}$ mit verhältnismäßig geringem Aufwand bestimmen, der vergleichbar mit dem des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers ist. Die Rechenregeln, die zusätzlich benötigt werden, sind die folgenden:

• ${\displaystyle \left({\frac {2}{n}\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}$
• ${\displaystyle \left({\frac {-1}{n}\right)=(-1)^{\frac {n-1}{2}$
• ${\displaystyle \left({\frac {1}{n}\right)=1}$
• ${\displaystyle \left({\frac {a}{n}\right)=\left({\frac {a\;\mathrm {mod} \;n}{n}\right)}$

Die oben stehende Regel folgt aus der Definition des Jacobi-Symbol über den Charakter. Der Zähler des Jacobi-Symbols ist nur ein Repräsentant der Gruppe ${\displaystyle a+n\mathbb {Z} }$; daher spielt es keine Rolle, welchen Repräsentanten man wählt.

• ${\displaystyle \left({\frac {ab}{n}\right)=\left({\frac {a}{n}\right)\cdot \left({\frac {b}{n}\right)}$ (Multiplikativität im Zähler)
• ${\displaystyle \left({\frac {a}{mn}\right)=\left({\frac {a}{m}\right)\cdot \left({\frac {a}{n}\right)}$ (Multiplikativität im Nenner)

Als Beispiel soll ${\displaystyle J(127,703)}$ bestimmt werden:

${\displaystyle \left({\frac {127}{703}\right)=(-1)^{\frac {126}{2}{\frac {702}{2}\left({\frac {703}{127}\right)=-\left({\frac {703}{127}\right)}$

Da man den Repräsentanten im Zähler frei wählen darf, ist dies gleich

${\displaystyle -\left({\frac {68}{127}\right)=-\left({\frac {2}{127}\right)^{2}\cdot \left({\frac {17}{127}\right)}$

Da 2 zu 127 teilerfremd ist, ist J(2, 127) sicher nicht 0 und damit J(2, 127)² = 1. Also fällt dieser Faktor weg und man erhält:

${\displaystyle -\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}$

Für die 2 im Zähler gibt es eine geschlossene Formel, daher erhält man schließlich:

${\displaystyle \left({\frac {127}{703}\right)=-\left((-1)^{\frac {17^{2}-1}{8}\right)^{3}=-1}$

1	Eingabe ${\displaystyle x\gets a,\,y\gets b}$
2	${\displaystyle J\gets 1}$
3	if ${\displaystyle y=1}$ then ${\displaystyle x\gets 1}$
4	while ${\displaystyle x\neq 1}$ and ${\displaystyle J\neq 0}$ do
5		Berechne ${\displaystyle q\in \mathbb {Z} ,\,r\in \mathbb {N} _{0},{\text{ wobei }x=q\cdot y+r{\text{ und }0\leq r<y}$
6		if ${\displaystyle r=0}$ then ${\displaystyle J\gets 0}$
7		else
8			Berechne ${\displaystyle k,x'\in \mathbb {N} _{0},{\text{ wobei }r=2^{k}\cdot x'{\text{ und }x'{\text{ ungerade}$
9			if ${\displaystyle k\equiv 1{\text{ mod }2}$ and ${\displaystyle y\equiv \pm 3{\text{ mod }8}$ then ${\displaystyle J\gets -J}$
10			if ${\displaystyle x'=1}$ then ${\displaystyle x\gets 1}$
11			else
12				if ${\displaystyle {\frac {x'-1}{2}\cdot {\frac {y-1}{2}\equiv 1{\text{ mod }2}$ then ${\displaystyle J\gets -J}$
13				${\displaystyle x\gets y}$
14				${\displaystyle y\gets x'}$
15	Ausgabe ${\displaystyle J}$

• Armin Leutbecher, Zahlentheorie. Springer-Verlag, 1996. ISBN 3-540-58791-8.