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:

<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 <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 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 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 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. 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)² = 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)

1	Eingabe <math>x \gets a,\, y \gets b</math>
2	<math>J \gets 1</math>
3	if <math>y = 1</math> then <math>x \gets 1</math>
4	while <math>x \neq 1</math> and <math>J \neq 0</math> do
5		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		if <math>r = 0</math> then <math>J \gets 0</math>
7		else
8			Berechne <math>k, x' \in \mathbb{N}_0, \text{ wobei } r = 2^k \cdot x' \text{ und } x' \text{ ungerade}</math>
9			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			if <math>x' = 1</math> then <math>x \gets 1</math>
11			else
12				if <math>\frac{x'-1}{2} \cdot \frac{y-1}{2} \equiv 1 \text{ mod } 2</math> then <math>J \gets -J</math>
13				<math>x \gets y</math>
14				<math>y \gets x'</math>
15	Ausgabe <math>J</math>

Literatur

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