Blum integer

In mathematics, a natural number n is a Blum integer if n = p×q is a semiprime for which p and q are distinct prime numbers congruent to 3 mod 4.[1] That is, p and q must be of the form 4t+3, for some integer t. Integers of this form are referred to as Blum primes.[2] 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, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, ... (sequence A016105 in the OEIS)

Blum integers were named for computer scientist Manuel Blum.

Properties

Given n = p×q a Blum integer, Qn the set of all quadratic residues modulo n, and aQn. Then:[2]

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

  1. Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf
  2. 1 2 Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001
  3. A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography ISBN 0-8493-8523-7.
This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.