In mathematics, more specifically in number theory, a natural number n is a Blum integer if n = pq is a semiprime for which p and q are distinct prime numbers congruent to 3 mod 4. That is, p and q must be of the form 4t+3, for some integer t. This means that the factors of a Blum integer are Gaussian primes with no imaginary part. The first few Blum integers are 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, ... (sequence A016105 in OEIS)
Blum integers were named for computer scientist Manuel Blum.
Properties of Blum integers
Given n = pq a Blum integer, Qn the set of all quadratic residues modulo n, and a ∈ Qn. Then:
- a has precisely four square roots modulo n, exactly one of which is also in Qn
- The unique square root of a in Qn is called the principal square root of a modulo n
- The function f: Qn → Qn defined by f(x) = x2 mod n is a permutation. The inverse function of f is: f -1(x) = x((p-1)(q-1)+4)/8 mod n.[1]
- For every Blum integer n, -1 has a Jacobi symbol mod n of +1, although -1 is not a quadratic residue of n:
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
- ^ A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography ISBN 0-8493-8523-7.
 |
This number theory-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
