Entier de Blum

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

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

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

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

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