Cryptography Reference
In-Depth Information
Z
n
and has even order
r
, then
x
r
−
≡
(
)
if
x
is randomly chosen in
1
0
mod
n
if
x
r
/
2
x
r
/
2
. In this case
x
r
/
2
(
+
)(
−
)
≡
(
)
−
≡
(
)
and only if
1
1
0
mod
n
1
0
mod
n
2, and hence if
x
r
/
2
for otherwise the order of
x
would divide
r
/
+
1
≡
0
(
mod
n
)
x
r
/
2
we find a nontrivial factor of
n
by computing gcd
(
−
1
,
n
)
. So factoring
n
is
∈ Z
n
with even order
r
and such that
x
r
/
2
equivalent to finding an
x
)
and the probability that a randomly chosen
x
satisfies these conditions is at least
1
≡−
1
(
mod
n
2
k
−
1
−
(
1
/
)
if
n
is an odd integer with exactly
k
distinct factors. This probability
is
2if
n
has at least two distinct prime factors and hence it suffices to choose
several random
x
to have a high probability of factoring
n
. Moreover, observe that,
once we know the order of
x
, the remaining operations to find a factor of
n
can all
be done in polynomial time even by a classical computer.
Shor's quantum algorithm to find the order of an integer modulo
n
is based on a
quantum version of the Fast Fourier Transform, which we shall not describe, and we
refer to Shor's original article or to [6, 60, 102, 202] for the details.
≥
1
/
Exercise 6.29
Let
n
be an odd integer which is the product of two distinct prime
factors. Show that if
x
∈ Z
n
is chosen at random and has order
r
modulo
n
, then the
probability that
r
is even and
x
r
/
2
≡−
1
(
mod
n
)
is at least 1
/
2. (Hint: Choosing a
∈ Z
n
, where
n
p
1
p
2
, amounts to choosing random elements
x
1
∈ Z
p
1
,
random
x
=
∈ Z
p
2
. If the orders of
x
1
and
x
2
are, respectively,
r
1
=
2
k
1
s
1
,
r
2
2
k
2
s
2
with
=
x
2
s
1
,
s
2
odd, then
r
=
lcm
(
r
1
,
r
2
)
(the least common multiple of
r
1
and
r
2
). Moreover,
0 and if
r
is even and
x
r
/
2
r
is odd if and only if
k
1
=
k
2
=
≡−
1
(
mod
n
)
, then
k
1
=
k
2
.)
Shor's algorithm makes it easy to factor integers except for one thing: a quantum
computer is required to do it. In principle, there is nothing in the laws of physics to
prevent us from building quantum computers but the practical difficulties seem very
great. For now, only very small numbers such as 15 have been factored (see [103])
with experimental quantum computers that use a few qubits—often just four qubits.
But factoring integers of several thousands of bits such as those currently being
used in cryptography (especially for RSA keys) would require quantum computers
with trillions of qubits and there are many problems (some of them related to noise
and in particular to the errors produced by the interaction of the quantum computer
with the environment) that make it unclear whether such computers will be built and
suggest that, in any case, this will not happen in the near future. But, as some of the
previous examples of historical factorizations corroborate, predicting the future of
factorization is very difficult. There are, however, a few papers that present estimates
of factorizations in the near future based mainly on extrapolating from the largest
NFS factorizations so far, taking into account other factors such as Moore's law and
the security of RSA encryption.
