Blum integer
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, a natural number n is a Blum integer if 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 , for some integer t. Integers of this form are referred to as Blum primes. 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, ... The integers were named for computer scientist Manuel Blum. The largest known Blum integer is (2 82,589,933 - 1)(2 136,279,841 - 1), a number with 65,886,368 digits.
In mathematics, a natural number n is a Blum integer if 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 , for some integer t. Integers of this form are referred to as Blum primes. 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, ... The integers were named for computer scientist Manuel Blum. The largest known Blum integer is (2 82,589,933 - 1)(2 136,279,841 - 1), a number with 65,886,368 digits.
Properties
Given a Blum integer, Q n the set of all quadratic residues modulo n and coprime to n and . 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) = x 2 mod n is a permutation. The inverse function of f is: f (x) = . 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
Text derived from https://en.wikipedia.org/w/index.php?oldid=1346288808 under CC BY-SA 4.0; modifications have been made.