Entier de Blum
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Nuvola_apps_password.svg/35px-Nuvola_apps_password.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/35px-Racine_carr%C3%A9e_bleue.svg.png)
Cet article est une ébauche concernant la cryptologie et les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En arithmétique, un entier de Blum est un nombre composé produit de deux nombres premiers distincts congrus à 3 modulo 4.
Ces nombres sont utilisés dans le cryptosystème de Rabin[1] et dans l'algorithme Blum Blum Shub.
Les dix premiers entiers de Blums sont : 21, 33, 57, 69, 77, 93, 129, 133, 141 et 161 (pour les 1 000 premiers, voir la suite A016105 de l'OEIS).
L'intérêt des entiers de Blum pour leurs applications algorithmiques vient des deux théorèmes suivants, qui permettent de calculer facilement des racines carrées modulaires[1]:
Théorème — Soit deux nombres premiers congrus à 3 modulo 4 et soit un entier de Blum et soit un résidu quadratique modulo . Il existe un unique nombre entier inférieur à qui vérifie les deux propriétés ci-dessous :
- est un résidu quadratique modulo ;
- .
De plus . On appelle la racine principale de modulo et on la note .
En plus de sa racine principale modulo , un résidu quadratique modulo un entier de Blum admet trois autres racines carrées. Les quatre racines carrées peuvent être calculées efficacement grâce au second théorème ci-dessous et au théorème des restes chinois[1].
Théorème — Soit deux nombres premiers congrus à 3 modulo 4, soit un entier de Blum et soit un résidu quadratique inversible modulo . Alors il existe quatre entiers inférieurs à tels que pour tout .
De plus pour tout on a et .
Les formules précédentes permettent de calculer aisément des racines carrées et ne s'appliquent que pour des facteurs premiers congrus à 3 modulo 4, ce qui est le cas des entiers de Blum. Calculer une racine carrée modulo un nombre dont certains facteurs premiers sont congrus à 1 modulo 4 nécessite l'application d'autres méthodes comme l'algorithme de Tonelli et Shanks (en) qui est plus coûteux en temps de calcul[2].
Références
Portail de la cryptologie
Arithmétique et théorie des nombres