Cryptography Reference
In-Depth Information
(when compared with the size of the integers in it), then the density of primes in it
is noticeable (i.e., is a polynomial fraction). Specifically, the density of primes in the
interval [
N
log
N
). Hence, on input
N
, we can expect to hit a prime
in the interval [
N
,
2
N
] within
(log
N
) trials. Furthermore, with probability at least
1
−
(1
/
N
)
2
we will hit a prime before conducting
((log
N
)
2
) trials. Hence, for all
practical purposes, we can confine ourselves to conducting a number of trials that is
polynomial (i.e.,
n
2
) in the length of the prime we want to generate (i.e.,
n
=
log
2
N
).
(We comment that an analogous discussion applies for primes that are congruent to
3 mod 4.)
We remark that there exists a probabilistic polynomial-time algorithm [9] that pro-
duces a uniformly selected prime
P
together with the factorization of
P
−
1. The prime
factorization of
P
−
1 can be used to verify that a given residue is a generator of the
multiplicative group modulo
P
:If
g
P
−
1
,
2
N
]is
(1
/
≡
(mod
P
) and
g
N
≡
1
1
(mod
P
) for
every
N
that divides
P
−
1, then
g
is a generator of the multiplicative group modulo
P
.
(Note that it suffices to check that
g
P
−
1
≡
1
(mod
P
) and
g
(
P
−
1)
/
Q
≡
1
(mod
P
)
for every prime
Q
that divides
P
1.) We mention that a noticeable fraction of the
residues modulo
P
will be generators of the multiplicative group modulo
P
.
Finally, we comment that more randomness-efficient procedures for generating an
n
-bit-long prime do exist and utilize only
O
(
n
) random bits.
4
−
A.2. Composite Numbers
A natural number (other than 1) that is not a prime is called a
composite
. Such a number
N
is uniquely represented as a product of prime powers; that is,
N
=
i
=
1
P
e
i
, where
the
P
i
's are distinct primes, the
e
i
's are natural numbers, and either
t
1.
These
P
i
's are called the
prime factorization of N
. It is widely believed that given
a composite number, it is infeasible to find its prime factorization. Specifically, it is
assumed that it is infeasible to find the factorization of a composite number that is the
product of two random primes. That is, it is assumed that any probabilistic polynomial-
time algorithm, given the product of two uniformly chosen
n
-bit-long primes, can
successfully recover these primes only with negligible probability. Rivest, Shamir,
and Adleman [191] have suggested the use of this assumption for the construction
of cryptographic schemes. Indeed, they have done so in proposing the RSA function,
and their suggestion has turned out to have a vast impact (i.e., being the most popular
intractability assumption in use in cryptography).
For a composite
N
, the
additive group modulo N
, denoted
Z
N
, consists of the set
{
0
,...,
N
−
1
}
and the operation of
addition
mod
N
. All elements that are relatively
prime to
N
have order
N
(in this group). The
multiplicative group modulo N
, denoted
Z
N
, consists of the set of natural numbers that are smaller than
N
and relatively prime
to it, and the operation is
multiplication
mod
N
.
>
1or
e
1
>
4
For example, one can use a generic transformation of [177]. Loosely speaking, the latter transformation
takes any polynomial-time linear-space randomized algorithm and returns a similar algorithm that has linear
randomness complexity. Note that the selection process described in the preceding text satisfies the premise of the
transformation.
