Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Symbole de Jacobi
Résumé
Jacobi symbol k/n for various k (along top) and n (along left side). Only 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if k is a quadratic residue modulo a coprime n, then k/n = 1, but not all entries with a Jacobi symbol of 1 (see the n = 9 and n = 15 rows) are quadratic residues. Notice also that when either n or k is a square, all values are nonnegative.
The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.
For any integer a and any positive odd integer n, the Jacobi symbol a/n is defined as the product of the Legendre symbols corresponding to the prime factors of n:
where
is the prime factorization of n.
The Legendre symbol a/p is defined for all integers a and all odd primes p by
Following the normal convention for the empty product, a/1 = 1.
When the lower argument is an odd prime, the Jacobi symbol is equal to the Legendre symbol.
The following is a table of values of Jacobi symbol k/n with n ≤ 59, k ≤ 30, n odd.
The following facts, even the reciprocity laws, are straightforward deductions from the definition of the Jacobi symbol and the corresponding properties of the Legendre symbol.
The Jacobi symbol is defined only when the upper argument ("numerator") is an integer and the lower argument ("denominator") is a positive odd integer.
- If n is (an odd) prime, then the Jacobi symbol a/n is equal to (and written the same as) the corresponding Legendre symbol.
- If a ≡ b (mod n), then
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.