Blum integer

Blum integer

In mathematics, more specifically in number theory, a natural number "n" is a Blum integer if "n = pq" 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 4"t"+3, for some integer "t". 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, ... OEIS|id=A016105

Properties of Blum integers

Given "n" = "pq" 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) = x2" mod "n" is a permutation. The inverse function of "f" is: "f -1(x) = x((p-1)(q-1)+4)/8" mod "n".A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, [http://cacr.math.uwaterloo.ca/hac/ Handbook of Applied Cryptography] ISBN 0-8493-8523-7.]
*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} ight)=left(frac{-1}{p} ight)left(frac{-1}{q} ight)=(-1)^2=1

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Blum-Goldwasser cryptosystem — The Blum Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum Goldwasser is a probabilistic, semantically secure cryptosystem with a constant size ciphertext expansion.… …   Wikipedia

  • Blum — Blume means flower in German. In English, the name Blum can either be pronounced /blʌm/, /blu:m/ or /blum/.People*Brad Blum CEO of Burger King from 2002 until 2004. *Geoff Blum baseball player *H Steven Blum three star general of the United… …   Wikipedia

  • Blum Blum Shub — (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986).Blum Blum Shub takes the form:: x n +1 = ( xn )2 mod M where M=pq is the product of two large primes p and q . At each… …   Wikipedia

  • Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia

  • Entier de Blum — En mathématiques, on désigne par entier de Blum tout nombre entier naturel qui est égal au produit de deux nombres premiers distincts p et q tels que . Un entier de Blum est donc un nombre composé. Un entier de Blum est un nombre RSA. Ces nombres …   Wikipédia en Français

  • Zero-knowledge proof — In cryptography, a zero knowledge proof or zero knowledge protocol is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement.A… …   Wikipedia

  • 210 (number) — 210 is the natural number following 209 and preceding 211. In mathematics 210 is a composite number, an abundant number, and the product of the first four prime numbers (2, 3, 5, and 7), and thus a primorial. It is also the sum of eight… …   Wikipedia

  • 33 (number) — ← 32 34 → 33 ← 30 31 32 33 34 35 36 …   Wikipedia

  • 77 (number) — 77 (seventy seven) is the natural number following 76 and preceding 78. Seventy seven is the smallest positive integer requiring five syllables in English. ← 76 78 → 77 …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”