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:
oder auch ![{\displaystyle (a/n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5380e7fa8cd49a34aa0cc7c2c5d4e3479724b6ef)
Um zwischen dem Legendre-Symbol und dem Jacobi-Symbol zu unterscheiden, schreibt man auch
und
.
Dabei muss
im Gegensatz zum Legendre-Symbol keine Primzahl sein, allerdings muss es eine ungerade natürliche Zahl sein. Für
sind beim Jacobi-Symbol wie beim Legendre-Symbol alle ganzen Zahlen zugelassen.
n ist eine Primzahl
Falls
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7de046ed7e891e308250db58af6585be62d72154)
n ist keine Primzahl
Ist die Primfaktorzerlegung von
, 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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec8d5789061fa8519d6544a2221ed6c8ded7c539)
Für
wird üblicherweise
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/075b3f0b4556fb43ef2e8c6a4b2af05f7e8967e7)
Achtung: Falls
keine Primzahl ist, gibt das Jacobi-Symbol nicht an, ob
ein quadratischer Rest modulo
ist (wie beim Legendre-Symbol). Eine notwendige Bedingung dafür, dass
ein quadratischer Rest modulo
ist, ist allerdings, dass das Jacobi-Symbol ungleich
ist. Beispielsweise erhält man für vier verschiedene Reste a modulo 15 für
![{\displaystyle \left({\frac {a}{15}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71f4832232dad659ee86fc53a62f5dcef37148ff)
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
über einen Charakter
der Gruppe
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c3e6ecdbb73c20afd81bbba269195ea0d87f105)
Dabei ist
die folgende Funktion:
![{\displaystyle \chi _{n}(a+n\mathbb {Z} ):=\prod _{x\in H}\varepsilon _{x}(a)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96c23f896e117c188a6bb1963dd828e084b8c45b)
ist dabei ein beliebiges Halbsystem modulo
, da der Wert von
nicht von der Wahl des Halbsystems abhängt.
bezeichnet den Korrekturfaktor von
und
bezüglich
:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e369875d206ddbc40d7bbe31d021ebeec86cd4a1)
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:
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5caadc01d4fb6eb3aece8726a8c6149cf081ff32)
Zur effektiven Berechnung ist diese Formel jedoch wenig geeignet, da sie für größere
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
in
, 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
nicht effizient genug.
Es gibt jedoch ein paar Rechenregeln, mit denen sich
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
größer 1 gilt:
![{\displaystyle \left({\frac {m}{n}}\right)=(-1)^{{\frac {(m-1)}{2}}{\frac {(n-1)}{2}}}\left({\frac {n}{m}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b478b67eb9f0be6fc099b77ddd7abe45ac43489)
Diese Regel ist das quadratische Reziprozitätsgesetz für das Jacobi-Symbol. Mit ihrer Hilfe, sowie wenigen weiteren Rechenregeln, lässt sich
für alle
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcf36bfe3bc4c8cff7a4113b49651986fab7301a)
![{\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\frac {n-1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f48f49e42c6611c68bc1df748ba9a81123ef27e8)
![{\displaystyle \left({\frac {1}{n}}\right)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07b2a3eef03e7519a37bc536daf9abd9e5dd86a5)
![{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a\;\mathrm {mod} \;n}{n}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8ff063a0451cd9cb65d7f9fd02c641faaa847fc)
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
; daher spielt es keine Rolle, welchen Repräsentanten man wählt.
(Multiplikativität im Zähler)
(Multiplikativität im Nenner)
Als Beispiel soll
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4888ce2354553658bf509787e82c183d4b868f0a)
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc76aa57537adcc4788889700b9d10853e34b9f9)
Da 2 zu 127 teilerfremd ist, ist J(2, 127) sicher nicht 0 und damit J(2, 127)2 = 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76492fe5ce73ffb0113cffcd2621b0851323d31f)
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a3e6af0c7ff49cc96325c2ae0c59206b4241e98)
Algorithmus – Berechnung des Jacobi-Symbols (a/b)
1 | Eingabe |
2 | |
3 | if then |
4 | while and do |
5 | | Berechne |
6 | | if then |
7 | | else |
8 | | | Berechne |
9 | | | if and then |
10 | | | if then |
11 | | | else |
12 | | | | if then |
13 | | | | |
14 | | | | |
15 | Ausgabe |
Literatur
- Armin Leutbecher, Zahlentheorie. Springer-Verlag, 1996. ISBN 3-540-58791-8.