Jacobi-Symbol - LinkFang.de





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 L(a,p) und J(a,n).

Dabei muss [math]n[/math] im Gegensatz zum Legendre-Symbol keine Primzahl sein, allerdings muss es eine ungerade Zahl größer als 1 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{ kein quadratischer Rest 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]

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.

Allgemeine Definition

Allgemein ist das Jacobi-Symbol J(a, n) ü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 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 [math]a, n[/math] 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 [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 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:

  • [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 J(127, 703) 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)2 = 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]

Literatur


Kategorien: Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Jacobi-Symbol (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.