Cryptography Reference
In-Depth Information
One advantage of this computing model is the notion of free massive parallelism.
With a single quantum bit of memory we can basically do
2
n
computations in parallel
for any
n
. One problem is that we cannot collect all results. With some special cases,
we can make the results interact (for instance through a discrete Fourier transform)
to derive a single result. This case is very well suited to the problem of factoriza-
tion. Indeed, the Shor algorithm can factorize any integer
N
within a complexity of
O
((log
N
)
2
(log log
N
)(log log log
N
))
on a quantum computer. The only remaining problem
is to construct a machine with
log
N
quantum bits of memory.
4
7.3
Computing Orders in Groups
7.3.1 Finding the Group Exponent
As explained in Section 7.1.2, we recall that the
exponent
of a group is the smallest
nonnegative integer
λ
such that
x
λ
=
1
for all
x
in the group (assuming that the group
is multiplicatively denoted). For cyclic groups, the exponent is obviously the order of
the group. For instance in
Z
n
(which is additively denoted), the exponent is
n
since
n
is the smallest
x
such that
x
.
1
≡
0 (mod
n
)
and we have
n
.
x
≡
0 (mod
n
)
for any
x
∈
Z
n
.
In the case of
Z
n
,
λ
is denoted
λ
(
n
)
as the
Carmichael function
. We can easily prove
that if
n
=
p
α
1
1
is the factorization of
n
, then
λ
(
n
)
=
lcm
(
p
1
−
1)
p
α
1
−
1
1
···
p
α
r
r
,...,
(
p
r
−
1)
p
α
r
−
1
r
which should be compared to
1)
p
α
1
−
1
1
1)
p
α
r
−
1
r
ϕ
(
n
)
=
(
p
1
−
···
(
p
r
−
.
Finding the exponent of
Z
n
is not easy. It is actually as hard as factoring
n
: obviously,
the factorization of
n
allows to compute
(
n
)
by the above formula. The opposite is a
little more subtle. Let us assume that we can compute
λ
=
λ
(
n
)
and let us factorize
n
.
λ
Let us first take an example with
n
=
pq
with
p
and
q
different primes such that
p
≡
q
≡
3 (mod 4)
. This way we have
λ
=
2
.
lcm
p
−
1
2
and the lcm is odd. We know that
q
−
1
2
,
x
p
−
1
1
if and only if
x
is a quadratic residue modulo
p
, and that
x
q
−
1
mod
p
=
mod
q
=
1
2
2
if and only if
x
is a quadratic residue modulo
q
. Hence the two reductions of
x
2
1
modulo
p
and modulo
q
are equal with probability
2
, namely if the quadratic residuosity
is the same for both modulo
p
and modulo
q
. This means that we can find factors of
n
by computing
gcd(
n
,
x
2
−
−
1 mod
n
)
with a random
x
.
More generally, let us assume without loss of generality that
n
is odd (we can
get rid of even factors by using the Chinese Remainder Theorem) and has at least
4
For more information, see Ref. [140].
Search WWH ::
Custom Search