Legendre Symbol
Le symbole de Legendre (a/p) détermine si a est un résidu quadratique modulo un nombre premier p : 1 (oui), -1 (non) ou 0 (p|a).
Objectif
Décider de la résolubilité des équations quadratiques modulo un nombre premier ; il est à la base de l'algorithme de Tonelli-Shanks.
Mécanisme
(a/p) = a^((p-1)/2) mod p (critère d'Euler). Propriétés : (ab/p)=(a/p)(b/p), et (a/p)*(a/q) est régi par la réciprocité quadratique. Il détermine si x^2≡a (mod p) admet une solution.
Cas d’usage
- Test de résidu quadratique
- Algorithmes de théorie des nombres
- Cryptographie
Outils associés
Exponentiation modulaire
Modular Exponentiation — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL
Symbole de Legendre
Legendre Symbol — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL
Symbole de Jacobi
Jacobi Symbol — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL
Symbole de Kronecker
Kronecker Symbol — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur. OUTIL