Cryptographie : Signature numérique et Chiffrement

Le symbole de Legendre

L'équation y2=x, x fixé, n'est pas toujours résoluble dans Z/nZ. Un peu comme pour le discriminant sur R, on a besoin de savoir si cette équation a des solutions ou non!

Définition : On dit que x est résidu quadratique modulo n s'il existe y tel que y2=x mod n. Si p est premier impair, on définit le symbole de Legendre :

Pour calculer, le symbole de Legendre, on dispose des 4 propriétés suivantes : La dernière proposition s'appelle loi de réciprocité quadratique. Elle fut longtemps un problème ouvert avant que Gauss ne la démontre, et en donne d'ailleurs plusieurs preuves différentes.

Exemple :
x2=219 admet-elle une solution modulo 383 ?
On calcule le symbole de Legendre :

Symbole de Jacobi

On étend la définition du symbole de Legendre en posant :
Le symbole de Jacobi ne permet plus de tester si x est un résidu quadratique modulo n. En revanche, on peut toujours le calculer en utilisant la loi de réciprocité quadratique, valable pour tous entiers impairs premiers entre eux. L'intérêt du symbole de Jacobi consiste essentiellement en le...

Test de primalité de Solovay-Strassen

On choisit un entier premier avec n. On calcule a(n-1)/2 mod n, puis le symbole de Jacobi . L'entier n satisfait au test si :
D'après un théorème d'Euler, si n est premier, il satisfait au test de Solovay-Strassen pour tout entier a. S'il n'est pas premier, on prouve qu'il existe au moins un entier premier avec n sur deux pour lequel n ne satisfait pas le test. Si on effectue k tests successifs, avec des entiers a différents chaque fois choisis au hasard, la probabilité pour que n soit premier s'il satisfait à chacun des tests est de l'ordre de 1-1/2k.