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. 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 premiers, voir la ).
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:
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.
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-Shanks qui est plus coûteux en temps de calcul..
Références
Catégorie:Entier naturel