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 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:

Théorème — Soit $p,q$ deux nombres premiers congrus à 3 modulo 4 et soit $n=pq$ un entier de Blum et soit $a$ un résidu quadratique modulo $n$. Il existe un unique nombre entier $k$ inférieur à $n$ qui vérifie les deux propriétés ci-dessous :

• $k$ est un résidu quadratique modulo $n$ ;
• $k^{2}\equiv a\mod n$.

De plus $k\equiv a^{\frac {(p-1)(q-1)+4}{8}}\mod n$. On appelle $k$ la racine principale de $a$ modulo $n$ et on la note ${\sqrt {\dot {a}}}$.

En plus de sa racine principale modulo $n$, 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.

Théorème — Soit $p,q$ deux nombres premiers congrus à 3 modulo 4, soit $n=pq$ un entier de Blum et soit $a$ un résidu quadratique inversible modulo $n$. Alors il existe quatre entiers $k_{1},k_{2},k_{3},k_{4}$ inférieurs à $n$ tels que pour tout $i\in \{1,2,3,4\},k_{i}^{2}\equiv a\mod n$.

De plus pour tout $i\in \{1,2,3,4\}$ on a $k_{i}\equiv \pm a^{\frac {p+1}{4}}\mod p$ et $k_{i}\equiv \pm a^{\frac {q+1}{4}}\mod q$.

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.