Hellenica World

Blum integer

In mathematics, more specifically in number theory, a natural number n is a Blum integer if n = pq where p and q are distinct prime numbers congruent to 3 mod 4. That is p and q must be of the form 4t+3, for some integer t. This means that they are Gaussian primes.

Properties of Blum Integers

Let n = pq be a Blum integer, let Qn be the set of all quadratic residues modulo n, and let a ∈ Qn. Then:

* a has precisely four square roots modulo n, exactly one of which is also in Qnn

* The unique square root of a in Qn is called the principle square root of a modulo n

* The function f: Qn → Qn 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.[1]

* 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 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

1. ^ A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography ISBN 0-8493-8523-7.

Number Theory

Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License

Index

Scientific Library - Scientificlib.com
Scientificlib News