

Next:Algorithme:Up:No
TitlePrevious:Tests
de primalité probabiliste
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: