Jacobi-Symbol

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

To distinguish between the Legendre symbol and the Jacobi symbol, it also writes L ( A, P ) and J ( a, n).

It need not be prime, in contrast to the Legendre symbol, but it must be greater than 1 in an odd number act. For the Jacobi symbol as the Legendre symbol all integers are allowed.

N is a prime number

If a prime number is, the Jacobi symbol behaves exactly as the Legendre symbol:

N is not a prime number

If the prime factorization of, so we define

Example:

Note: If no prime, are the Jacobi symbol does not indicate whether a quadratic residue modulo (like the Legendre symbol ). A necessary condition that a quadratic residue modulo is, however, that the Jacobi symbol is not equal.

General definition

Generally, the Jacobi symbol J (a, n ) over a character of the group defined:

It is the following function:

Is any system half modulo, as the value of is independent of the choice of the semiconductor system. denotes the correction factor of and respect:

Closed representation

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

However, to effectively calculate this formula is very useful, since it has, for more quickly many factors.

Efficient calculation of the Jacobi symbol

In most cases where you need to calculate the Jacobi symbol, so the Solovay -Strassen test, you do not have prime factorization of the number n in J (a, n ) so that the Jacobi symbol is not the Legendre can be traced back symbol. In addition, the above mentioned closed-form representation for bigger is not efficient enough.

However, there are a few rules of calculation with which J ( a, n) can be determined efficiently. These rules are, among others from the quadratic reciprocity law, which has its validity also for the Jacobi symbol.

The most important principle is the following: For all odd integers greater than 1:

This rule is the law of quadratic reciprocity for the Jacobi symbol. With their help, as well as a few other calculation rules can be J (a, b ) for all a, b determine with relatively little effort, which is comparable to the Euclidean algorithm for finding the greatest common divisor. The calculation rules that are additionally needed are the following:

The above rule follows from the definition of the Jacobi symbol of the character. The Jacobi symbol, the counter is only a representative of the group; therefore it does not matter which representatives are selected.

• ( Multiplicativity in the numerator )
• ( Multiplicativity in the denominator )

As an example, J (127, 703) is to be determined:

Since one may choose the representatives in the numerator free, this is equal to

As 2 to 127 is relatively prime, J ( 2, 127) is not 0, and thus ensure J (2, 127 ) 2 = 1 Thus, this factor is eliminated and we obtain:

For the 2 in the numerator there is a closed formula, therefore we obtain finally: