Entero de Blum

En matemáticas , un número natural n es un entero de Blum si n = p × q es un semiprimo para el cual p y q son números primos distintos congruentes con 3 mod 4. ^{[ 1 ]} Es decir, p y q deben ser de la forma 4 t + 3 , para algún entero t . Los enteros de esta forma se denominan primos de Blum. ^{[ 2 ]} Esto significa que los factores de un entero de Blum son primos gaussianos sin parte imaginaria. Los primeros enteros de Blum son

21 , 33 , 57 , 69 , 77 , 93 , 129 , 133 , 141 , 161 , 177 , 201 , 209 , 213 , 217 , 237 , 249 , 253 , 301 , 309 , 321 , 329 , 341 , 381 , 393 , 413 , 417 , 437 , 453 , 469 , 473 , 489 , 497 , ... (secuencia A016105 en el OEIS )

Los números enteros recibieron su nombre en honor al científico informático Manuel Blum . El entero de Blum más grande conocido es (2 ^82,589,933 - 1)(2 ^136,279,841 - 1), un número con 65,886,368 dígitos.

Dado n = p × q un entero de Blum, Q _n el conjunto de todos los residuos cuadráticos módulo n y coprimos con n y a ∈ Q _n . Entonces: ^{[ 2 ]}

• a tiene cuatro raíces cuadradas módulo n , exactamente una de las cuales también está en Q _n
• La única raíz cuadrada de a en Q _n se llama raíz cuadrada principal de a módulo n
• La función f  : Q _n → Q _n definida por f ( x ) = x ² mod n es una permutación. La función inversa de f es: f ⁻¹ ( x ) = x ^{(( p − 1)( q − 1)+4)/8} mod n . ^{[ 3 ]}
• Para cada entero de Blum n , −1 tiene un símbolo de Jacobi módulo n de +1, aunque −1 no es un residuo cuadrático de n :

${\displaystyle \left({\frac {-1}{n}}\right)=\left({\frac {-1}{p}}\right)\left({\frac {-1}{q}}\right)=(-1)^{2}=1}$

Ningún número entero de Blum es la suma de dos cuadrados .

Antes del desarrollo de algoritmos de factorización modernos, como MPQS y NFS , se consideraba útil seleccionar enteros de Blum como módulos RSA . Sin embargo, esto ya no se considera una precaución útil, puesto que MPQS y NFS pueden factorizar enteros de Blum con la misma facilidad que los módulos RSA construidos a partir de primos seleccionados aleatoriamente.