Math & Numbers

Vérificateur de résidu quadratique (symboles de Legendre/Jacobi)

Calcule le symbole de Jacobi (a/n) (n impair jusqu'à 10¹⁸ ; Legendre si n est premier) : modulo un nombre premier, a^((n−1)/2) ≡ 1 signifie résidu quadratique et Tonelli–Shanks (ou la formule directe si p ≡ 3 (mod 4)) fournit les racines ±√a ; le symbole −1 certifie que a n'est PAS un résidu. Pour un module composé le symbole n'est que nécessaire : −1 prouve la non-résiduosité, +1 reste non concluant (résolu par force brute quand n ≤ 10⁵). Classique : 10 est un résidu quadratique mod 13 avec racines ±6.