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:

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

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

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

n ist eine Primzahl

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

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

n ist keine Primzahl

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

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

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

Beispiel:

$\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 $n$ keine Primzahl ist, gibt das Jacobi-Symbol nicht an, ob $a$ ein quadratischer Rest modulo $n$ ist (wie beim Legendre-Symbol). Eine notwendige Bedingung dafür, dass $a$ ein quadratischer Rest modulo $n$ ist, ist allerdings, dass das Jacobi-Symbol ungleich $-1$ ist. Beispielsweise erhält man für vier verschiedene Reste a modulo 15 für

$\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.

Allgemeine Definition

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

$\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 $\chi _{n}(a+n\mathbb {Z} )$ die folgende Funktion:

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

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

$\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.

Geschlossene Darstellung

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

$\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 $a,n$ 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 $n$ in $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 $a,n$ nicht effizient genug.

Es gibt jedoch ein paar Rechenregeln, mit denen sich $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 $m,n$ größer 1 gilt:

$\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 $J(a,b)$ für alle $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:

• $\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}}$
• $\left({\frac {-1}{n}}\right)=(-1)^{\frac {n-1}{2}}$
• $\left({\frac {1}{n}}\right)=1$
• $\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 $a+n\mathbb {Z}$; daher spielt es keine Rolle, welchen Repräsentanten man wählt.

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

Als Beispiel soll $J(127,703)$ bestimmt werden:

$\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

$-\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:

$-\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:

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

Algorithmus – Berechnung des Jacobi-Symbols (a/b)

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

Literatur

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