Teste  de Solovay-Strassen

• Définition: Soit p impair, premier et  . On dit que x est un résidu quadratique modulo p si:




admet une solution dans 



• Résidus quadratiques de 11 sont 1,3,4,5,9 car (  ,  ,  ,  ,  )
  
  
  
•  Critère d'Euler:. x est un résidu quadratique modulo p sss:






• Ex:






• Symbole de Legendre: 


0          si 
1          si a est un résidu quadratique mod p


-1       si a n'est pas un résidu quadratique mod p



•  Donc






• Pour n entier impair, le Jacobi de n est 




sont les facteurs premiers de n



•  Ex: