224
12 Cryptocurrencies
12.10 Quantum Computing
The security of many cryptography algorithms is based on the fact that it is practically impossible to find the factors p and q of a very large number N = pq. This
problem, however, is equivalent to finding the period r , such that x
r
= 1 (mod N )
for a randomly chosen x < N , coprime with N . Finding the period r is as difficult as
finding the prime factors and might practically take forever, if N is large. Quantum
computers, on the other hand, promise to do so efficiently, as we will discuss below.
For the time being, let us assume that some technical conditions are fulfilled, that
the period r is known and turns out to be an even number. This allows us to rewrite
x
r
= 1 (mod N ) as
(x
r/2
− 1)(x
r/2
+ 1) = k N
for some integer k
(12.36)
from which we conclude that p = gcd(x
r/2
− 1, N ) and q = gcd(x
r/2
+ 1, N )
are factors of N . Trying to factor N = 15 provides an example with the smallest non-trivial integers. Let’s chose x = 7, which leads to the sequence x
k
=
{7, 4, 13, 1, 7, 4, . . . } for k = 1, 2, . . . and we find x
4
= 1, which implies r = 4.
For the factors we then obtain p = gcd(x
r/2
− 1, N ) = gcd(48, 15) = 3 and q =
gcd(x
r/2
+ 1, N ) = 5, both of which divide N = 15. Note that most steps, such as
finding the greatest common denominator, take little time. Only finding the period
r is extremely time-consuming with classical computers. In his ground-breaking
report [21] Shor showed how using a quantum computer can reduce this time dramatically, which, on the long run, might compromise many cryptographic algorithms.
Before discussing quantum computers, let us briefly recall the operation of classical computers, which are based on logic gates that implement operations of Boolean
algebra. Since boolean “states” are either true or false, they are represented by “1”
and “0,” respectively. The top of the left-hand side in Fig. 12.10 shows a gate that
implements a logical not operation, which inverts the input A and makes it available
Fig. 12.10 Left: NOT (top) and NAND (below) gate and the table describing the relation of the
outputs X and Y to the inputs A and B. Right: Half-adder, composed of NAND gates, which calculates
the sum S and a carry-bit C of the inputs A and B
12 Cryptocurrencies
12.10 Quantum Computing
The security of many cryptography algorithms is based on the fact that it is practically impossible to find the factors p and q of a very large number N = pq. This
problem, however, is equivalent to finding the period r , such that x
r
= 1 (mod N )
for a randomly chosen x < N , coprime with N . Finding the period r is as difficult as
finding the prime factors and might practically take forever, if N is large. Quantum
computers, on the other hand, promise to do so efficiently, as we will discuss below.
For the time being, let us assume that some technical conditions are fulfilled, that
the period r is known and turns out to be an even number. This allows us to rewrite
x
r
= 1 (mod N ) as
(x
r/2
− 1)(x
r/2
+ 1) = k N
for some integer k
(12.36)
from which we conclude that p = gcd(x
r/2
− 1, N ) and q = gcd(x
r/2
+ 1, N )
are factors of N . Trying to factor N = 15 provides an example with the smallest non-trivial integers. Let’s chose x = 7, which leads to the sequence x
k
=
{7, 4, 13, 1, 7, 4, . . . } for k = 1, 2, . . . and we find x
4
= 1, which implies r = 4.
For the factors we then obtain p = gcd(x
r/2
− 1, N ) = gcd(48, 15) = 3 and q =
gcd(x
r/2
+ 1, N ) = 5, both of which divide N = 15. Note that most steps, such as
finding the greatest common denominator, take little time. Only finding the period
r is extremely time-consuming with classical computers. In his ground-breaking
report [21] Shor showed how using a quantum computer can reduce this time dramatically, which, on the long run, might compromise many cryptographic algorithms.
Before discussing quantum computers, let us briefly recall the operation of classical computers, which are based on logic gates that implement operations of Boolean
algebra. Since boolean “states” are either true or false, they are represented by “1”
and “0,” respectively. The top of the left-hand side in Fig. 12.10 shows a gate that
implements a logical not operation, which inverts the input A and makes it available
Fig. 12.10 Left: NOT (top) and NAND (below) gate and the table describing the relation of the
outputs X and Y to the inputs A and B. Right: Half-adder, composed of NAND gates, which calculates
the sum S and a carry-bit C of the inputs A and B