Shor Algorithm by the Numbers

Published by Fudgy McFarlen on June 2, 2012June 2, 2012

Numeric Example of the Shor Algorithm

See Chapter 10 of the book: Algorithms for greater detail.

LibreOffice SpreadSheet with these same calculations: Shor-Algorithm-By-The-Numbers-Amarketplaceofideas-com.ods

The RSA setup

You start by picking two large secret primes p and q, then compute:

N = p · q — the modulus. In the article's example, p = 7, q = 11, so N = 77. N is public.
φ(N) = (p − 1)(q − 1) — Euler's totient of N. Size of the multiplicative group mod N, and it's secret. For N = 77, φ(77) = 6 · 10 = 60.
e — the public encryption exponent. You pick any e with 1 < e < φ(N) and gcd(e, φ(N)) = 1. Common choice is e = 65537. e is public.
d — the private decryption exponent. It's the modular inverse of e mod φ(N), i.e. the unique d with e · d ≡ 1 (mod φ(N)). d is secret.

The keys

Public key = (N, e) — you publish this. Anyone can encrypt a message m by computing c = m? mod N.
Private key = (N, d) — you keep this. You decrypt with m = c? mod N.

It works because of Euler's theorem: m^(ed) ≡ m^(1 + kφ(N)) ≡ m (mod N).

p and q are the secret primes you use to derive d. If an attacker learns p and q, they can compute φ(N) and then d, so factoring N breaks RSA. That's exactly why Shor's algorithm matters: it factors N efficiently on a quantum computer, which hands the attacker φ(N), then d, then the private key.

$p,q = 7,11$

$p*q= 7 * 11 = 77$

Factoring the product is a difficult computation task in the case of large prime numbers. In this case it is obvious for the example's purposes

Factor 77 using Shor's algorithm

Pick a number that is relative prime to both 7 and 11. Here we choose 5 for the example.

$(5^r) mod(77)$ will be periodic in r. The following would be set up in a quantum register to have all the values in the register simultaneously and calculate the function results simultaneously.

$5^1mod(77)=5$
$5^2mod(77)=25$
$5^3mod(77)=48$
$5^4mod(77)=9$
$5^5mod(77)=45$
$5^6mod(77)=71$
$5^7mod(77)=47$
$5^8mod(77)=4$
$5^9mod(77)=20$
$5^10mod(77)=23$
$5^11mod(77)=38$
$5^12mod(77)=36$
$5^13mod(77)=26$
$5^14mod(77)=53$
$5^15mod(77)=34$
$5^16mod(77)=16$
$5^17mod(77)=3$
$5^18mod(77)=15$
$5^19mod(77)=75$
$5^20mod(77)=67$
$5^21mod(77)=27$
$5^22mod(77)=58$
$5^23mod(77)=59$
$5^24mod(77)=64$
$5^25mod(77)=12$
$5^26mod(77)=60$
$5^27mod(77)=69$
$5^28mod(77)=37$
$5^29mod(77)=31$
$5^30mod(77)=1$ Starts repeating here
$5^31mod(77)=5$ Calculate one more to check up above to convince yourself the exponential function is indeed periodic

Here we see the form of even power of the variable with 1 left over after the mod. That allows transforming the equation to the easily factored form of an even power minus one that can be factored. The even power is not guaranteed to you keep trying solutions till you get an even periodicity.

$(x^2-1)=0mod(77)$

$(x-1)(x+1)=0mod(77)$

After the above results are piled simultaneously in the quantum register a quantum FFT is performed and the period r found to be 30 with high probability. All the above mod result values are in the register at the same time and not indexed per time or pure number index as far as I know. A quantum FFT does not yield a spectrum. It yields a frequency estimate of highest probability of the input waveform. Frequency as in probability frequency. However the above mod result values are KNOWN to be in regular spacing so a frequency that we are accustomed to can be calculated.

Thus using

$5^30 -1$ have common factors with 77.

$5^30-1 = (5^15-1)(5^15+1)$

Calculators

Each of 77's 2 coprime factors have a common factor with only one of the 2 terms above. *(Not sure yet how to prove that) Use Euclid's rule to find the greatest common divisor

Perplexity: Since N | (a^r – 1) = (a^(r/2) – 1)(a^(r/2) + 1) and N ? either factor alone (because r is the smallest period), each prime factor of N must divide one of the two terms. It is also possible for both primes to divide the same term (in which case the algorithm fails and you retry with a new a); the guarantee is only probabilistic. The page's phrasing that each factor hits only one of the two terms is not generally true it happens to be true here.

Greatest Common Divisor. See chapter 1.2.3 of Algorithms.\

$5^15 -1 = 30517578124 = 11 * 2774325284$
$5^15 +1 = 30517578126 = 7 * 4359654018$
$5^30 -1: GCF ( 77 , 30517578124 ) =11$ 30517578124 = 2² × 11 × 31 × 71 × 181 × 1741
$5^30 -1: GCF ( 77 , 30517578126 ) =7$ 30517578126 = 2 × 3² × 7 × 61 × 521 × 7621