In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 ...
''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 nu ...
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 ways ...
s congruent to 3
mod
Mod, MOD or mods may refer to:
Places
* Modesto City–County Airport, Stanislaus County, California, US
Arts, entertainment, and media Music
* Mods (band), a Norwegian rock band
* M.O.D. (Method of Destruction), a band from New York City, US ...
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
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
with no imaginary part. The first few Blum integers are
:
21,
33,
57,
69,
77,
93,
129,
133 133 may refer to:
*133 (number)
* AD 133
*133 BC
*133 (song)
*133 (New Jersey bus) 133 may refer to:
*133 (number)
* AD 133
*133 BC
*133 (song) 133 may refer to:
*133 (number)
*AD 133
*133 BC
*133 (song)
*133 (New Jersey bus) 133 may refer to:
* ...
,
141,
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 condi ...
,
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
Manuel Blum (born 26 April 1938) is a Venezuelan-American 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 ...
.
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 no ...
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
Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
mod ''n'' of +1, although −1 is not a quadratic residue of ''n'':
::
History
Before modern factoring algorithms, such as
MPQS The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is consider ...
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
{{Classes of natural numbers
Integer sequences