Entier de Blum
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 Modèle: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]: Modèle:Théorème 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]. Modèle:Théorème
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'Modèle:Lien qui est plus coûteux en temps de calcul[2].
Références
- ↑ 1,0 1,1 et 1,2 Modèle:Ouvrage.
- ↑ Modèle:Ouvrage.