Blum integer

Properties

Given a Blum integer, Q**n the set of all quadratic residues modulo n and coprime to n and a ∈ Q**n. Then:

• a has four square roots modulo n, exactly one of which is also in Q**n
• The unique square root of a in Q**n is called the principal square root of a modulo n
• The function f : Q**n → Q**n defined by f(x) = x2 mod n is a permutation. The inverse function of f is: f(x) = x((p−1)(q−1)+4)/8 mod n.
• For every Blum integer n, −1 has a Jacobi symbol mod n of +1, although −1 is not a quadratic residue of n: :: \left(\frac{-1}{n}\right)=\left(\frac{-1}{p}\right)\left(\frac{-1}{q}\right)=(-1)^2=1

No Blum integer is the sum of two squares.

History

Before modern factoring algorithms, such as MPQS and NFS, were developed, it was thought to be useful to select Blum integers as RSA moduli. This is no longer regarded as a useful precaution, since MPQS and NFS are able to factor Blum integers with the same ease as RSA moduli constructed from randomly selected primes.

References

References

1. Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf
2. [[Shafi Goldwasser. Goldwasser, S.]] and [[Mihir Bellare. Bellare, M.]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"] {{Webarchive. link. (2012-04-21 . Summer course on cryptography, MIT, 1996-2001)
3. {{Cite OEIS. A016105. Blum integers: numbers of the form p * q where p and q are distinct primes congruent to 3 (mod 4)
4. (1997). "Handbook of applied cryptography". CRC Press.