Cryptography Reference
In-Depth Information
two different primes (otherwise, the factorization is easy). Let
i
be such that
λ
can be
written as
2
i
k
with
k
odd. There is at least a prime factor
p
of
n
such that
2
i
divides
1
and
(
p
−
1)
/
2
i
is odd. Obviously,
x
∈
Z
n
is a quadratic residue modulo
p
if and
only if
x
2
i
−
1
k
mod
p
is equal to 1. Let
q
be another prime factor of
n
.If
2
i
does not
divide
q
−
1
, then we have
x
2
i
−
1
k
mod
q
=
1
for all
x
∈
Z
n
. Otherwise this holds if and
only if
x
is a quadratic residue modulo
q
. From these two facts (modulo
p
and
q
) and
the Chinese Remainder Theorem we infer that
x
2
i
−
1
k
modulo
p
and
x
2
i
−
1
k
modulo
q
are
different with probability
p
−
1
2
, but that
x
2
i
−
1
k
is a square root of 1. This means that there is
a probability of
1
2
that
gcd(
x
2
i
−
1
k
n
)
yields a nontrivial factor of
n
for a random
−
1 mod
n
,
Z
n
. We can iterate this process until we find all factors of
n
.
x
∈
Finding an element order is a separate problem. We can first notice that finding
element orders implies finding the group exponent. Indeed, the exponent is equal to
the lcm of all element orders by Lemma 7.3. Therefore, computing the lcm of orders
of a few elements quickly reaches the exponent as the number of elements grows.
Therefore, finding the order of an element is at least as hard as computing the group
exponent which is equivalent to the factorization problem in the case of
Z
n
.
7.3.2 Computing Element Orders in Groups
As we saw in the previous section, computing element orders is at least as hard as
computing the group exponent.
In some particular groups, computation is easy. For instance, in
Z
n
, we can compute
the order of
x
even though we do not know how to factorize
n
. The order is the smallest
nonnegative
k
such that
kx
≡
0 (mod
n
)
, namely such that
n
divides
kx
. The order is
simply given by the formula
k
=
lcm(
n
,
x
)
x
.
When the complete factorization of the exponent of a group
G
is known, it is also
easy to compute the order of any group element
x
: let
λ
be the exponent of
G
and let
p
α
1
1
p
α
r
r
be the complete factorization of
λ
(all
p
i
are pairwise different primes, and
all
α
i
are nonnegative integers). We want to compute the order of
x
∈
G
. We know that
it is a factor of
λ
.Weset
k
=
λ
as a first app
ro
ximation for the order of
x
. For any
i
from 1 to
n
, we replace
k
by
k
/
p
i
as long as
x
p
i
···
1
in
G
. (We assume the group to be
multiplicatively denoted.) At the end we are ensured that
k
is the smallest nonnegative
power of
x
which is such that
x
k
=
1
.
=
In the case of
Z
n
we obtain that
knowledge of the factorization of
λ
(
n
)
=⇒
ability to compute element orders in
Z
n
=⇒
knowledge of
λ
(
n
)
⇐⇒
knowledge of the factorization of
n
Search WWH ::
Custom Search