Jacobi-Symbol

Das Jacobi-Symbol, benannt nach Carl Gustav Jacob Jacobi, ist eine Verallgemeinerung des Legendre-Symbols. Die Notation ist die gleiche wie die des Legendre-Symbols:

$\left({\frac {a}{n}}\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 das n im Gegensatz zum p im (a/p) keine Primzahl sein, allerdings muss es sich bei dem n um eine ungerade Zahl handeln.

n ist eine Primzahl

Solange aber das n eine Primzahl ist, verhält sich das Jacobi-Symbol exakt wie das Legendre Symbol:

$\left({\frac {a}{n}}\right)=\left\{{\begin{matrix}1&{\mbox{wenn }}a{\mbox{ ein quadratischer Rest zu }}n{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ kein quadratischer Rest zu }}n{\mbox{ ist}}\\0&{\mbox{wenn }}a{\mbox{ und }}n{\mbox{ nicht teilerfremd sind und }}n\ a{\mbox{ teilt}}\end{matrix}}\right.$

n ist keine Primzahl

Ist die Primfaktorzerlegung von $b=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdot ...\cdot p_{n}^{\nu _{n}}$, so definiert man

$\left({\frac {a}{b}}\right)=\left({\frac {a}{p_{1}}}\right)^{\nu _{1}}\cdots \left({\frac {a}{p_{n}}}\right)^{\nu _{n}},$

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: Das Jacobi-Symbol gibt, für den Fall, das n keine Primzahl ist, nicht mehr an, ob a ein Quadratischer Rest modulo b ist, wie dies noch beim Legendre-Symbol der Fall war.

Die allgemeine Berechnung des Jacobi-Symbols

In den meisten Fällen, in denen man die Berechnung des Jacobi-Symbols benötigt, so bei dem Solovay-Strassen-Test, hat man keine Primfaktorzerlegung der Zahl n in J(a,n), so dass sich keiner der beiden oben angeführten Berechnungen durchführen lässt. In diesem Fall gibt es sechs Regeln, mit denen sich J(a,n) in einzelne L(b,p) zerlegen lässt. An einem Beispiel werden diese Regeln erklärt (über die Kenntnis von Primzahlen gehe ich mal weg):

J(127,703)

Regel 6: Wenn der ggT(a,b) = 1, und (a-1)(b-1)/4 gerade ist, dann ist J(a,b) = J(b,a)
         Wenn der ggT(a,b) = 1, und (a-1)(b-1)/4 ungerade ist, dann ist J(a,b) = -1 * J(b,a)

ggT(127,703) = 1; (126*702)/4 = 22113 => J(127,703) = -1 * J(703,127)

J(703,127)

Regel 4: J(a,n) = J((a mod n),n)

J(703,127) = J(68,127)

J(68,127)

Regel 2: J(a*b,n) = J(a,n) * J(b,n)

J(68,127) = J(2,127)^{2 * J(17,127) = J(17,127)}

Das sind die wichtigsten drei Regeln. Außerdem gibt es noch die folgenden drei Regeln:

Regel 1: J(1,n) = 1
Regel 3: Wenn (n2-1)/8 gerade ist, dann ist J(2,n) = 1
               Wenn (n2-1)/8 ungerade ist, dann ist J(2,n) = -1
Regel 5: J(a,b1*b2) = J(a,b1) * J(a,b2)

Siehe auch: Solovay-Strassen-Test