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{array}{cc}1& \text{wenn }a\text{ ein quadratischer Rest modulo }n\text{ ist}\\ -1& \text{wenn }a\text{ ein quadratischer Nichtrest modulo }n\text{ ist}\\ 0& \text{wenn }n\text{ ein Teiler von }a\text{ ist (also }a\text{ kongruent }0\text{ modulo }n\text{)}\end{array}$

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{array}{cc}{\chi }_n(a+n\mathbb{Z})& \text{falls ggT}(a,n)=1\\ 0& \text{sonst}\end{array}$

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

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

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

${\epsilon }_x(a):=\{\begin{array}{cc}1& \text{falls }x\text{ und }a\cdot x\text{ im gleichen Halbsystem liegen}\\ -1& \text{sonst}\end{array}$

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)}\mathrm{sgn}\left((\frac{k}{n}-\frac{h}{a})(\frac{k}{n}+\frac{h}{a}-\frac{1}{2})\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{array}{cc}1,& n\equiv \pm 1(\mathrm{mod}8)\\ -1,& n\equiv \pm 3(\mathrm{mod}8)\end{array}$
• $\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{m}\mathrm{o}\mathrm{d}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)=-{((-1{)}^{\frac{17^2-1}{8}})}^3=-1$

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

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

Literatur

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