In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

 n is a Blum integer if n = p×q is a semiprime

Semiprime

In mathematics, a semiprime is a natural number that is the product of two prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... ....

 for which p and q are distinct prime number

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

s congruent to 3 mod

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

 4. That is, p and q must be of the form 4t+3, for some integer t. Primes of this form are referred to as Blum primes. This means that the factors of a Blum integer are Gaussian primes

Gaussian integer

In number theory, a Gaussian integer is a complex number whose real and imaginary part are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. The Gaussian integers are a special case of the quadratic...

 with no imaginary part. The first few Blum integers are

21

21 (number)

21 is the natural number following 20 and preceding 22.-In mathematics:Twenty-one is the fifth discrete Semiprime and the second in the family. With 22 it forms the second discrete Semiprime pair...

, 33

33 (number)

33 is the natural number following 32 and preceding 34.-In mathematics:33 is the largest positive integer that cannot be expressed as a sum of different triangular numbers. It is also the smallest odd repdigit that is not a prime number.33 is the eighth distinct semiprime comprising the prime...

, 57

57 (number)

57 is the natural number following 56 and preceding 58.- In mathematics :Fifty-seven is the sixteenth discrete semiprime and the sixth in the family. With 58 it forms the fourth discrete bi-prime pair. 57 has an aliquot sum of 23 and is the first composite member of the 23-aliquot tree...

, 69

69 (number)

69 is a number following 68 and preceding 70.- In mathematics:The aliquot sum of sixty-nine is 27 within the aliquot sequence 69 being the third composite number in the 13-aliquot tree.69 is a semiprime...

, 77

77 (number)

77 is the natural number following 76 and preceding 78. Seventy-seven is the smallest positive integer requiring five syllables in English.-In mathematics:...

, 93

93 (number)

93 is the natural number following 92 and preceding 94.-In mathematics:Ninety-three is the twenty-eighth distinct semiprime and the ninth of the form...

, 129

129 (number)

129 is the natural number following 128 and preceding 130.-In mathematics:129 is the sum of the first ten prime numbers...

, 133

133 (number)

133 is the natural number following 132 and preceding 134.-In mathematics:133 is an n whose divisors added up divide φ. It is an octagonal number and a Harshad number...

, 141

141 (number)

141 is the natural number following 140 and preceding 142.-In mathematics:141 is a centered pentagonal number. It is the sum of the sums of divisors of the first thirteen integers....

, 161

161 (number)

161 is an odd natural number between 160 and 162-In geography:* Bahrain and Brunei each have coastlines that are 161 kilometers in length.* Bhutan ranks #161 in world population...

, 177

177 (number)

177 is the natural number following 176 and preceding 178.-In mathematics:* 177 is an odd number* 177 is a composite number* 177 is a deficient number, as 63 is less than 177* 177 is a Leyland number since it can be expressed as 27 + 72...

, ...

Blum integers were named for computer scientist Manuel Blum

Manuel Blum

Manuel Blum is a computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".-Biography:Blum attended MIT, where he received his bachelor's degree and...

.

Properties

Given n = p×q a Blum integer, Q_n the set of all quadratic residues modulo n, and a ∈ Q_n. Then:

• a has precisely 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² mod n is a permutation. The inverse function of f is: f ^-1(x) = x^{((p-1)(q-1)+4)/8} mod n.
• For every Blum integer n, -1 has a Jacobi symbol
  Jacobi symbol
  The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in...
  
   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.