pseudo-premier d’Euler

ARITHMETIQUE

Notion d’arithmétique modulaire. Les nombres pseudo-premiers d’Euler sont des nombres pseudo-premiers qui vérifient la condition :
a^(p-1)/2 = 1 (mod p) ou a^(p-1)/2 = -1 (mod p)
(voir critère d’Euler ).
Cette condition est nécessaire si le nombre est premier mais n’est pas suffisante.
Ce test de primalité est plus fort que le test de Fermat (petit théorème de Fermat , condition elle aussi nécessaire mais non suffisante, les nombres qui la vérifient sont les pseudo-premiers de Fermat, les nombres de Carmichael vérifient cette condition mais ne sont pas premiers).
Les nombres pseudo-premiers d’Euler qui sont composés sont appelés nombres pseudo-premiers d’Euler-Jacobi.
Les tests de primalité sont utilisés en cryptologie .