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 a n displaystyle left frac a n right oder auch a n displaystyle a n Um zwischen dem Legendre Symbol und dem Jacobi Symbol zu unterscheiden schreibt man auch L a p displaystyle L a p und J a n displaystyle J a n Dabei muss n displaystyle n im Gegensatz zum Legendre Symbol keine Primzahl sein allerdings muss es eine ungerade naturliche Zahl sein Fur a displaystyle a sind beim Jacobi Symbol wie beim Legendre Symbol alle ganzen Zahlen zugelassen Inhaltsverzeichnis 1 n ist eine Primzahl 2 n ist keine Primzahl 3 Allgemeine Definition 4 Geschlossene Darstellung 5 Effiziente Berechnung des Jacobi Symbols 6 Algorithmus Berechnung des Jacobi Symbols a b 7 Literaturn ist eine Primzahl BearbeitenFalls n displaystyle n nbsp eine Primzahl ist ist das Jacobi Symbol nach Definition gleich dem Legendre Symbol a n 1 wenn a ein quadratischer Rest modulo n ist 1 wenn a ein quadratischer Nichtrest modulo n ist 0 wenn n ein Teiler von a ist also a kongruent 0 modulo n displaystyle left frac a n right begin cases 1 amp mbox wenn a mbox ein quadratischer Rest modulo n mbox ist 1 amp mbox wenn a mbox ein quadratischer Nichtrest modulo n mbox ist 0 amp mbox wenn n mbox ein Teiler von a mbox ist also a mbox kongruent 0 mbox modulo n mbox end cases nbsp n ist keine Primzahl BearbeitenIst die Primfaktorzerlegung von n p 1 n 1 p 2 n 2 p k n k displaystyle n p 1 nu 1 cdot p 2 nu 2 cdots p k nu k nbsp so definiert man a n a p 1 n 1 a p k n k displaystyle left frac a n right left frac a p 1 right nu 1 cdots left frac a p k right nu k nbsp Fur n 1 displaystyle n 1 nbsp wird ublicherweise a 1 1 displaystyle left frac a 1 right 1 nbsp gesetzt leeres Produkt Beispiel 11 91 11 7 11 13 4 7 11 13 1 1 1 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 nbsp Achtung Falls n displaystyle n nbsp keine Primzahl ist gibt das Jacobi Symbol nicht an ob a displaystyle a nbsp ein quadratischer Rest modulo n displaystyle n nbsp ist wie beim Legendre Symbol Eine notwendige Bedingung dafur dass a displaystyle a nbsp ein quadratischer Rest modulo n displaystyle n nbsp ist ist allerdings dass das Jacobi Symbol ungleich 1 displaystyle 1 nbsp ist Beispielsweise erhalt man fur vier verschiedene Reste a modulo 15 fur a 15 displaystyle left frac a 15 right nbsp den Wert 1 jedoch sind nur zwei davon Quadrate modulo 15 man erhalt fur 1 2 4 8 den Wert 1 Quadrate sind nur 1 und 4 Den Wert 0 erhalt man siebenmal 0 3 5 6 9 10 12 davon sind aber auch nur vier Quadrate 0 6 9 10 Ubrig bleiben die vier Werte fur die man 1 erhalt 7 11 13 14 hier erhalt man wie bereits angesprochen niemals ein Quadrat Allgemeine Definition BearbeitenAllgemein ist das Jacobi Symbol J a n displaystyle J a n nbsp uber einen Charakter x n displaystyle chi n nbsp der Gruppe Z n Z displaystyle mathbb Z n mathbb Z nbsp definiert a n x n a n Z falls ggT a n 1 0 sonst displaystyle left frac a n right begin cases chi n a n mathbb Z amp mbox falls ggT a n 1 0 amp mbox sonst end cases nbsp Dabei ist x n a n Z displaystyle chi n a n mathbb Z nbsp die folgende Funktion x n a n Z x H e x a displaystyle chi n a n mathbb Z prod x in H varepsilon x a nbsp H displaystyle H nbsp ist dabei ein beliebiges Halbsystem modulo n displaystyle n nbsp da der Wert von x n displaystyle chi n nbsp nicht von der Wahl des Halbsystems abhangt e x a displaystyle varepsilon x a nbsp bezeichnet den Korrekturfaktor von a displaystyle a nbsp und x displaystyle x nbsp bezuglich H displaystyle H nbsp e x a 1 falls x und a x im gleichen Halbsystem liegen 1 sonst displaystyle varepsilon x a begin cases 1 amp mbox falls x mbox und a cdot x mbox im gleichen Halbsystem liegen 1 amp mbox sonst end cases nbsp Eine alternative Definitionsmoglichkeit liefert das Lemma von Zolotareff nach dem das Jacobi Symbol gleich dem Vorzeichen einer speziellen Permutation ist Geschlossene Darstellung BearbeitenDie folgende Formel ist eine geschlossene Darstellung des Werts des Jacobi Symbols a n k 1 1 2 n 1 h 1 1 2 a 1 sgn k n h a k n h a 1 2 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 nbsp Zur effektiven Berechnung ist diese Formel jedoch wenig geeignet da sie fur grossere a n displaystyle a n nbsp schnell sehr viele Faktoren aufweist Effiziente Berechnung des Jacobi Symbols BearbeitenIn den meisten Fallen in denen man die Berechnung des Jacobi Symbols benotigt so beim Solovay Strassen Test hat man keine Primfaktorzerlegung der Zahl n displaystyle n nbsp in J a n displaystyle J a n nbsp sodass sich das Jacobi Symbol nicht auf das Legendre Symbol zuruckfuhren lasst Zudem ist die oben angegebene geschlossene Darstellung fur grossere a n displaystyle a n nbsp nicht effizient genug Es gibt jedoch ein paar Rechenregeln mit denen sich J a n displaystyle J a n nbsp effizient bestimmen lasst Diese Regeln ergeben sich unter anderem aus dem quadratischen Reziprozitatsgesetz das auch fur das Jacobi Symbol seine Gultigkeit besitzt Das wichtigste Prinzip ist das folgende Fur alle ungeraden ganzen Zahlen m n displaystyle m n nbsp grosser 1 gilt m n 1 m 1 2 n 1 2 n m displaystyle left frac m n right 1 frac m 1 2 frac n 1 2 left frac n m right nbsp Diese Regel ist das quadratische Reziprozitatsgesetz fur das Jacobi Symbol Mit ihrer Hilfe sowie wenigen weiteren Rechenregeln lasst sich J a b displaystyle J a b nbsp fur alle a b displaystyle a b nbsp mit verhaltnismassig geringem Aufwand bestimmen der vergleichbar mit dem des euklidischen Algorithmus zur Bestimmung des grossten gemeinsamen Teilers ist Die Rechenregeln die zusatzlich benotigt werden sind die folgenden 2 n 1 n 2 1 8 1 n 1 mod 8 1 n 3 mod 8 displaystyle left frac 2 n right 1 frac n 2 1 8 begin cases 1 amp n equiv pm 1 pmod 8 1 amp n equiv pm 3 pmod 8 end cases nbsp 1 n 1 n 1 2 displaystyle left frac 1 n right 1 frac n 1 2 nbsp 1 n 1 displaystyle left frac 1 n right 1 nbsp a n a m o d n n displaystyle left frac a n right left frac a mathrm mod n n right nbsp Die oben stehende Regel folgt aus der Definition des Jacobi Symbol uber den Charakter Der Zahler des Jacobi Symbols ist nur ein Reprasentant der Gruppe a n Z displaystyle a n mathbb Z nbsp daher spielt es keine Rolle welchen Reprasentanten man wahlt a b n a n b n displaystyle left frac ab n right left frac a n right cdot left frac b n right nbsp Multiplikativitat im Zahler a m n a m a n displaystyle left frac a mn right left frac a m right cdot left frac a n right nbsp Multiplikativitat im Nenner Als Beispiel soll J 127 703 displaystyle J 127 703 nbsp bestimmt werden 127 703 1 126 2 702 2 703 127 703 127 displaystyle left frac 127 703 right 1 frac 126 2 frac 702 2 left frac 703 127 right left frac 703 127 right nbsp Da man den Reprasentanten im Zahler frei wahlen darf ist dies gleich 68 127 2 127 2 17 127 displaystyle left frac 68 127 right left frac 2 127 right 2 cdot left frac 17 127 right nbsp Da 2 zu 127 teilerfremd ist ist J 2 127 sicher nicht 0 und damit J 2 127 2 1 Also fallt dieser Faktor weg und man erhalt 17 127 1 126 2 16 2 127 17 127 17 8 17 2 17 3 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 nbsp Fur die 2 im Zahler gibt es eine geschlossene Formel daher erhalt man schliesslich 127 703 1 17 2 1 8 3 1 displaystyle left frac 127 703 right left 1 frac 17 2 1 8 right 3 1 nbsp Algorithmus Berechnung des Jacobi Symbols a b Bearbeiten1 Eingabe x a y b displaystyle x gets a y gets b nbsp 2 J 1 displaystyle J gets 1 nbsp 3 if y 1 displaystyle y 1 nbsp then x 1 displaystyle x gets 1 nbsp 4 while x 1 displaystyle x neq 1 nbsp and J 0 displaystyle J neq 0 nbsp do5 Berechne q Z r N 0 wobei x q y r und 0 r lt y displaystyle q in mathbb Z r in mathbb N 0 text wobei x q cdot y r text und 0 leq r lt y nbsp 6 if r 0 displaystyle r 0 nbsp then J 0 displaystyle J gets 0 nbsp 7 else8 Berechne k x N 0 wobei r 2 k x und x ungerade displaystyle k x in mathbb N 0 text wobei r 2 k cdot x text und x text ungerade nbsp 9 if k 1 mod 2 displaystyle k equiv 1 text mod 2 nbsp and y 3 mod 8 displaystyle y equiv pm 3 text mod 8 nbsp then J J displaystyle J gets J nbsp 10 if x 1 displaystyle x 1 nbsp then x 1 displaystyle x gets 1 nbsp 11 else12 if x 1 2 y 1 2 1 mod 2 displaystyle frac x 1 2 cdot frac y 1 2 equiv 1 text mod 2 nbsp then J J displaystyle J gets J nbsp 13 x y displaystyle x gets y nbsp 14 y x displaystyle y gets x nbsp 15 Ausgabe J displaystyle J nbsp Literatur BearbeitenArmin Leutbecher Zahlentheorie Springer Verlag 1996 ISBN 3 540 58791 8 Abgerufen von https de wikipedia org w index php title Jacobi Symbol amp oldid 235234888
