Jacobi symbol

The Jacobi symbol , named after Carl Gustav Jacob Jacobi , is a generalization of the Legendre symbol . The Jacobi symbol can in turn be generalized to the Kronecker symbol . The notation is the same as that of the Legendre symbol :

${\displaystyle \left({\frac {a}{n}}\right)}$ or ${\displaystyle (a/n)}$

To distinguish between the Legendre symbol and the Jacobi symbol, one also writes and . ${\displaystyle L(a,p)}$ ${\displaystyle J(a,n)}$

In contrast to the Legendre symbol, it does not have to be a prime number, but it has to be an odd number greater than 1. For both the Jacobi symbol and the Legendre symbol, all integers are permitted. ${\displaystyle n}$ ${\displaystyle a}$

n is a prime number

If is a prime number, the Jacobi symbol is by definition equal to the Legendre symbol: ${\displaystyle n}$

${\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}}}$

n is not a prime number

If the prime factorization of , then one defines ${\displaystyle n=p_{1}^{\nu _{1}}\cdot p_{2}^{\nu _{2}}\cdots p_{k}^{\nu _{k}}}$

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

Example:

${\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}$

Caution: If it is not a prime number, the Jacobi symbol does not indicate whether a quadratic remainder is modulo (as with the Legendre symbol). A necessary condition for a quadratic remainder to be modulo , however, is that the Jacobi symbol is not equal . ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle -1}$

general definition

In general, the Jacobi symbol is defined by a character in the group : ${\displaystyle J(a,n)}$ ${\displaystyle \chi _{n}}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

${\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}}}$

It has the following function: ${\displaystyle \chi _{n}(a+n\mathbb {Z} )}$

${\displaystyle \chi _{n}(a+n\mathbb {Z} ):=\prod _{x\in H}\varepsilon _{x}(a)}$

${\displaystyle H}$is any half-system modulo , since the value of does not depend on the choice of the half-system. denotes the correction factor of and with respect to : ${\displaystyle n}$ ${\displaystyle \chi _{n}}$ ${\displaystyle \varepsilon _{x}(a)}$ ${\displaystyle a}$ ${\displaystyle x}$ ${\displaystyle H}$

${\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}}}$

An alternative definition is provided by Zolotareff's lemma , according to which the Jacobi symbol is equal to the sign of a special permutation .

Closed representation

The following formula is a closed representation of the value of the Jacobi symbol:

${\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)}$

However, this formula is not very suitable for effective calculation, as it quickly shows a large number of factors for larger ones. ${\displaystyle a,n}$

Efficient calculation of the Jacobi symbol

In most cases in which the calculation of the Jacobi symbol is required, as in the Solovay-Strassen test , there is no prime factorization of the number in , so that the Jacobi symbol cannot be traced back to the Legendre symbol. In addition, the closed representation given above is not efficient enough for larger ones . ${\displaystyle n}$ ${\displaystyle J(a,n)}$ ${\displaystyle a,n}$

However, there are a few calculation rules that can be used to determine efficiently. These rules result, among other things, from the quadratic reciprocity law , which is also valid for the Jacobi symbol. ${\displaystyle J(a,n)}$

The most important principle is the following: For all odd whole numbers greater than 1 the following applies: ${\displaystyle m,n}$

${\displaystyle \left({\frac {m}{n}}\right)=(-1)^{{\frac {(m-1)}{2}}{\frac {(n-1)}{2}}}\left({\frac {n}{m}}\right)}$

This rule is the quadratic reciprocity law for the Jacobi symbol. With their help, as well as a few other calculation rules, it can be determined for everyone with relatively little effort, which is comparable to that of the Euclidean algorithm for determining the greatest common divisor. The calculation rules that are additionally required are the following: ${\displaystyle J(a,b)}$ ${\displaystyle a,b}$

• ${\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}}}$
• ${\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\frac {n-1}{2}}}$
• ${\displaystyle \left({\frac {1}{n}}\right)=1}$
• ${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a\;\mathrm {mod} \;n}{n}}\right)}$

The above rule follows from the definition of the Jacobi symbol about the character . The numerator of the Jacobi symbol is only a representative of the group ; therefore it doesn't matter which representative you choose. ${\displaystyle a+n\mathbb {Z} }$

• ${\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\cdot \left({\frac {b}{n}}\right)}$ (Multiplicativity in numerator)
• ${\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\cdot \left({\frac {a}{n}}\right)}$ (Multiplicativity in the denominator)

The following is to be determined as an example : ${\displaystyle J(127,703)}$

${\displaystyle \left({\frac {127}{703}}\right)=(-1)^{{\frac {126}{2}}{\frac {702}{2}}}\left({\frac {703}{127}}\right)=-\left({\frac {703}{127}}\right)}$

Since you can freely choose the representative in the counter, this is the same

${\displaystyle -\left({\frac {68}{127}}\right)=-\left({\frac {2}{127}}\right)^{2}\cdot \left({\frac {17}{127}}\right)}$

Since 2 to 127 is relatively prime , J (2, 127) is certainly not 0 and therefore J (2, 127) ² = 1. So this factor is omitted and we get:

${\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}}$

There is a closed formula for the 2 in the numerator, so you finally get:

${\displaystyle \left({\frac {127}{703}}\right)=-\left((-1)^{\frac {17^{2}-1}{8}}\right)^{3}=-1}$

Algorithm - calculation of the Jacobi symbol ${\displaystyle \left({\frac {a}{b}}\right)}$

1	input ${\displaystyle x\gets a,\,y\gets b{\text{ und }}J\gets 1}$
2	while do ${\displaystyle x\neq 1}$
3		Calculate ${\displaystyle k,\,x'\in \mathbb {N} _{0},{\text{ wobei }}x=2^{k}x'{\text{ gilt und }}x'{\text{ungerade ist.}}}$
4th		if then ${\displaystyle k\equiv 1({\text{ mod }}2)}$
5			${\displaystyle J\gets (-1)^{{\frac {x'-1}{2}}{\frac {y-1}{2}}}J}$
6th		if then ${\displaystyle x'\neq 1}$
7th			${\displaystyle J\gets (-1)^{{\frac {x'-1}{2}}{\frac {y-1}{2}}}J}$
8th			divide with remainder by where ${\displaystyle y}$ ${\displaystyle r}$ ${\displaystyle x'}$ ${\displaystyle \implies y=qx'+r}$ ${\displaystyle 0\leq r<x'}$
9			${\displaystyle y\gets x'{\text{ und }}x\gets r}$
10		else
11			${\displaystyle x\gets 1}$
12	output ${\displaystyle J}$

literature

• Armin Leutbecher, number theory . Springer-Verlag, 1996. ISBN 3-540-58791-8 .