Jacobi-Symbol

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 an\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 zu p in L(a,p) keine Primzahl sein, allerdings muss es sich bei n um eine ungerade Zahl größer als 1 handeln. Für a sind beim Jacobi-Symbol wie beim Legendre-Symbol alle ganzen Zahlen zugelassen.

Inhaltsverzeichnis

n ist eine Primzahl

Falls n eine Primzahl ist, verhält sich das Jacobi-Symbol exakt wie das 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{ kein quadratischer Rest modulo }n\mbox{ ist} \\ 0 & \mbox{wenn }a\mbox{ und }n\mbox{ nicht teilerfremd sind} \end{cases}

n ist keine Primzahl

Ist die Primfaktorzerlegung von n=p_1^{\nu_1}\cdot p_2^{\nu_2}\cdot ... \cdot 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},

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 für a, ein quadratischer Rest modulo n zu sein, ist allerdings, dass das Jacobi-Symbol ungleich -1 ist.

Allgemeine Definition

Allgemein ist das Jacobi-Symbol J(a, n) über einen Charakter χ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 χn nicht von der Wahl des Halbsystems abhängt. ε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}

Geschlossene Darstellung

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

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

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 mn\right) = (-1)^{\frac{(m-1)}{2}\frac{(n-1)}{2}}\left(\frac nm\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(\frac2n\right) = (-1)^{\frac{n^2-1}8} = \begin{cases} 1 & n \equiv \pm 1 (mod 8) \\ -1 & n \equiv\pm 3 (mod 8) \end{cases}
  • \left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}2}
  • \left(\frac1n\right) = 1
  • \left(\frac an\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 an\right)\cdot\left(\frac bn\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)2 = 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

Literatur


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Jacobi symbol — The Jacobi symbol is a generalization of the Legendre symbol introduced by Jacobi in 1837 [C.G.J.Jacobi Uber die Kreisteilung und ihre Anwendung auf die Zahlentheorie , Bericht Ak. Wiss. Berlin (1837) pp 127 136] . It is of theoretical interest… …   Wikipedia

  • Jacobi symbol — noun Mathematical function of two integers, written , based on whether a is a square modulo the prime factors of b …   Wiktionary

  • Jacobi — ist der Familienname folgender Personen: Abraham Jacobi (1830–1919), deutsch US amerikanischer Kinderarzt Albano von Jacobi (1854–1928), deutscher Offizier und Diplomat Ariane Jacobi (* 1966), deutsche Jazzsängerin und Moderatorin Arnold Jacobi… …   Deutsch Wikipedia

  • Symbol — des Sternbildes Löwe Der Terminus Symbol (aus dem Griechischen: Etwas Zusammengefügtes) oder auch Sinnbild wird im Allgemeinen für Bedeutungsträger (Zeichen, Wörter, Gegenstände, Vorgänge etc.) verwendet, die eine Vorstellung meinen (von etwas,… …   Deutsch Wikipedia

  • Jacobi sum — In mathematics, a Jacobi sum is a type of character sum formed with one or more Dirichlet characters. The simplest example would be for a Dirichlet character χ modulo a prime number p . Then take: J (χ) = Σ χ( a )χ(1 − a ) where the summation… …   Wikipedia

  • Jacobi triple product — In mathematics, the Jacobi triple product is a relation that re expresses the Jacobi theta function, normally written as a series, as a product. This relationship generalizes other results, such as the pentagonal number theorem.Let x and y be… …   Wikipedia

  • Jacobi polynomials — In mathematics, Jacobi polynomials are a class of orthogonal polynomials. They are obtained from hypergeometric series in cases where the series is in fact finite::P n^{(alpha,eta)}(z)=frac{(alpha+1) n}{n!}, 2F 1left(… …   Wikipedia

  • Legendre symbol — The Legendre symbol or quadratic character is a function introduced by Adrien Marie Legendre in 1798 [A. M. Legendre Essai sur la theorie des nombres Paris 1798, p 186] during his partly successful attempt to prove the law of quadratic… …   Wikipedia

  • Carl Gustav Jacob Jacobi — Carl Jacobi Carl Gustav Jacob Jacobi Born December 10, 1804(1804 …   Wikipedia

  • Carl Gustav Jacobi — Carl Jacobi Carl Gustav Jacob Jacobi (* 10. Dezember 1804 in Potsdam; † 18. Februar 1851 in Berlin), war ein deutscher Mathematiker. Er war ein Bruder von Hermann Jacobi. Jacobis Begabung für die Mathematik, aber auch für Sprachen, zeigte sich… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”