Calculateur du Symbole de Legendre

À propos de ce calculateur

Le symbole de Legendre (a/p), défini pour un entier a et un nombre premier impair p, est une façon compacte de répondre à une question fondamentale de la théorie des nombres : la congruence x² ≡ a (mod p) a-t-elle une solution ? Ce calculateur l'évalue avec le critère d'Euler : (a/p) ≡ a^((p-1)/2) (mod p), qui vaut 1 si a est un résidu quadratique modulo p, −1 si c'est un non-résidu, et 0 si p divise a exactement.

Le symbole de Legendre est une brique de la théorie de la réciprocité quadratique et apparaît dans toute la théorie des nombres computationnelle et la cryptographie — y compris les tests de primalité, les algorithmes de calcul de racines carrées modulaires et les constructions de la cryptographie sur courbes elliptiques — partout où il importe de savoir si un nombre est un carré parfait modulo un nombre premier.