In
mathematics, a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
''n'' is a Blum integer if is a
semiprime
In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.
Because there are infinitely many prime ...
for which ''p'' and ''q'' are distinct
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
s congruent to 3
mod 4.
[Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf] That is, ''p'' and ''q'' must be of the form , for some integer ''t''. Integers of this form are referred to as Blum primes.
[ Goldwasser, S. and Bellare, M.br>"Lecture Notes on Cryptography"]
. Summer course on cryptography, MIT, 1996-2001 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 141 may refer to:
* 141 (number), an integer
* AD 141, a year of the Julian calendar
* 141 BC
__NOTOC__
Year 141 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Caepio and Pompeius (or, ...
,
161
Year 161 ( CLXI) was a common year starting on Wednesday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Caesar and Aurelius (or, less frequently, year 914 ''Ab urbe cond ...
,
177
Year 177 ( CLXXVII) was a common year starting on Tuesday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Commodus and Plautius (or, less frequently, year 930 ''Ab urbe co ...
, 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.
Properties
Given a Blum integer, ''Q''
''n'' the set of all
quadratic residue
In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that:
:x^2\equiv q \pmod.
Otherwise, ''q'' is called a quadratic non ...
s 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'':
::
History
Before modern factoring algorithms, such as
MPQS and
NFS, were developed, it was thought to be useful to select Blum integers as
RSA
RSA may refer to:
Organizations Academia and education
* Rabbinical Seminary of America, a yeshiva in New York City
*Regional Science Association International (formerly the Regional Science Association), a US-based learned society
*Renaissance S ...
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
{{Classes of natural numbers
Integer sequences