Inteiro de Blum

Em matemática, um número natural n é um inteiro de Blum se n = p × q for um semiprimo para o qual p e q são números primos distintos congruentes a 3 mod 4.^[1] Ou seja, p e q devem ser da forma 4t + 3, para algum número inteiro t. Os números inteiros dessa forma são chamados de números primos de Blum.^[2] Isso significa que os fatores de um número inteiro de Blum são primos gaussianos sem parte imaginária. Os primeiros números inteiros de Blum são

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, ... (sequência A016105 na OEIS)

Os números inteiros foram nomeados em homenagem ao cientista da computação Manuel Blum.^[3]

Propriedades

Dado n = p × q um número inteiro de Blum, Q_n o conjunto de todos os resíduos quadráticos módulo n e coprimos de n e a ∈ Q_n. Então:^[2]

• a tem quatro raízes quadradas no módulo n, sendo que exatamente uma delas também está em Q_n

• A única raiz quadrada de a em Q_n é chamada de raiz quadrada principal de a módulo n

• A função f : Qn → Qn definida por f(x) = x² mod n é uma permutação. A função inversa de f é: f⁻¹(x) = x^{((p−1)(q−1)+4)/8} mod n.^[4]

• Para todo número inteiro Blum n, -1 tem um símbolo de Jacobi mod n de +1, embora -1 não seja um resíduo quadrático de n:

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

Nenhum número inteiro de Blum é a soma de dois quadrados.

História

Antes do desenvolvimento de algoritmos de fatoração modernos, como o MPQS e o NFS, acreditava-se que era útil selecionar números inteiros de Blum como módulos RSA. Isso não é mais considerado uma precaução útil, pois o MPQS e o NFS são capazes de fatorar números inteiros de Blum com a mesma facilidade que os módulos RSA construídos a partir de primos selecionados aleatoriamente.

Referências

1. https://www.gilith.com/talks/cambridge1997.pdf
2. «Lecture Notes of Cryptography». web.archive.org. Consultado em 31 de maio de 2024 
3. «A016105 - OEIS». oeis.org. Consultado em 31 de maio de 2024 
4. «Handbook of applied cryptography | WorldCat.org». search.worldcat.org. Consultado em 31 de maio de 2024