Cryptology 405The algorithm is actually quite simple. Take a number, N, to factor.
Choose a value, A, that is less than N. This value should also be relatively
prime to N, but assuming that N is the product of two prime numbers
(which will always be the case when trying to factor numbers to break RSA),
if A isn’t relatively prime to N, then A is one of N’s factors.
Next, load up the superposition with sequential numbers counting
up from 1 and feed every one of those values through the function
f(x)=Ax(modN). This is all done at the same time, through the magic
of quantum computation. A repeating pattern will emerge in the results,
and the period of this repetition must be found. Luckily, this can be done
quickly on a quantum computer with a Fourier transform. This period will
be called R.
Then, simply calculate gcd(AR/2 + 1, N) and gcd(AR/2 − 1, N). At least one
of these values should be a factor of N. This is possible because AR=1(modN)
and is further explained below.
AR =1(modN)
(AR/2)^2 =1(modN)
(AR/2)^2 −1=0(modN)
(AR/2−1) · (AR/2+1)=0(modN)
This means that (AR/2 − 1) · (AR/2 + 1) is an integer multiple of N. As
long as these values don’t zero themselves out, one of them will have a factor
in common with N.
To crack the previous RSA example, the public value N must be factored.
In this case N equals 143. Next, a value for A is chosen that is relatively prime to
and less than N, so A equals 21. The function will look like f(x)=21x(mod143).
Every sequential value from 1 up to as high as the quantum computer will
allow will be put through this function.
To keep this brief, the assumption will be that the quantum computer
has three quantum bits, so the superposition can hold eight values.
Here the period is easy to determine by eye: R is 4. Armed with this
information, gcd(21^2 − 1143) and gcd(21^2 + 1143) should produce at
least one of the factors. This time, both factors actually appear, since
gcd(440, 143) = 11 and gcd(442, 142) = 13. These factors can then be
used to recalculate the private key for the previous RSA example.
x= 1 211(mod143) = 21
x= 2 212(mod143) = 12
x= 3 213(mod143) = 109
x= 4 214(mod143) = 1
x= 5 215(mod143) = 21
x= 6 216(mod143) = 12
x= 7 217(mod143) = 109
x= 8 218(mod143) = 1