Cryptography Reference
In-Depth Information
Exercise 6.28
Estimate howmany years would it take to factor a 4096-bit composite
integer which is a product of two primes of approximately the same length in the
following cases:
(i) With the same computational resources used in the factorization of RSA768.
(ii) With computational resources initially equivalent to those in the factorization of
RSA768 but assuming that “computing power” doubles each 2years.
The previous estimate seems to suggest that factoring a “difficult” 2048-bit integer
is completely out of reach—which is good for some cryptographic schemes—but
there are reasons to be cautious. Some of these reasons are mentioned below.
6.4.10.3 Final Remarks on Factorization
There are other interesting factoring algorithms that we will not study in detail be-
cause they are slower than QS and NFS when factoring “difficult” numbers. The
most important of these algorithms is the
Elliptic Curve Method
(ECM) of H.W.
Lenstra which, as the name implies, is based on the arithmetic of elliptic curves
(we will study elliptic curves in Chap.
11
because they also have interesting cryp-
tographic applications). The heuristic complexity of ECM is also subexponential
but, as mentioned in [60], this complexity comes close to being rigorous because
the only unproved hypothesis used in its proof is a reasonable conjecture about the
distribution of smooth numbers in short intervals. Under this hypothesis, Lenstra
showed that the expected running time
of
ECM to fi
nd the leas
t prime factor
p
of a
composite n
u
mber
n
is
((
√
2
))
√
ln
p
ln ln
p
2
(
ln
n
)
·
exp
+
o
(
1
)
whichintheworst
≈
√
n
becomes
L
1
+
o
(
1
)
as the term ln
2
n
is absorbed by the
o
case
p
.Thisis
the same heuristic complexity as QS but the latter is faster for worst-case numbers.
However, ECM is very well suited to finding relatively small factors of huge numbers
and it has been successfully used to find factors of several Fermat numbers.
We have mentioned that NFS is the fastest factoring algorithm known but now we
must make an important qualification to this assertion: this is only true in practice but
not in theory and it will only remain true in practice while no fully functional quantum
computers are built. Quantum computers are machines that use the principles of
quantum mechanics for their basic operations. Instead of the bits used by classical
computers, quantum computers operate with
quantum bits
(
qubits
, for short) and
the use of quantum properties such as superposition and entanglement allows them,
using a
quantum register
composed of
n
qubits, to execute in a single computational
step the same mathematical operation on 2
n
numbers. Thus quantum computers have
an “exponential advantage” over classical computers whenever applying a
quantum
algorithm
is possible. This is the case with the integer factorization problem and, as
Shor [177] proved,
a quantum computer can factor integers in polynomial time
.
Shor found a polynomial-time quantum algorithm to find the order
r
of an integer
x
modulo
n
, i.e., the smallest
r
(
n
)
(
1
)
1 such that
x
r
. Then a factoring
algorithm is obtained by finding the orders of random residues modulo
n
. Indeed,
≥
≡
1
(
mod
n
)
