This note treats the quantum procedure as a black box. Its purpose is to explain the algebraic information that Shor's algorithm recovers and why that information compromises RSA and elliptic-curve discrete-logarithm systems.
1. The unifying idea
Shor's algorithm can efficiently recover
the period or hidden subgroup of certain functions with suitable algebraic
structure. RSA and elliptic-curve cryptography fall within this framework
because the relevant problems can be formulated using finite abelian groups.
From a modern algebraic perspective, Shor's algorithm is therefore best understood not merely as a general-purpose period-finding algorithm, but as a method for recovering hidden algebraic structure, specifically hidden subgroups of abelian groups.
- RSA factorisation reduces to order finding in a finite abelian group.
- The discrete-logarithm problem reduces to an abelian hidden-subgroup problem.
- The elliptic-curve discrete-logarithm problem is the corresponding problem in an elliptic-curve group.
2. RSA: a hidden one-dimensional period
Let
N = pq,
where p and q are distinct odd primes. Choose an integer a with 1
< a < N.
First compute gcd(a, N). If gcd(a,
N) > 1, a non-trivial factor has already been
found. Otherwise,
gcd(a, N) = 1, and the a lies in the multiplicative group modulo N.
Define the function
f : ℤ → ℤ *N, f(x) = aˣ mod N.
The multiplicative order of a modulo N is the smallest positive integer r such
that
aʳ ≡ 1
(mod N).
Consequently, f(x + r) = f(x) for every integer x. The hidden subgroup of
ℤ is
rℤ = ⟨r⟩ = { …, −2r, −r,
0, r, 2r, … }.
The order-finding part of Shor's algorithm
recovers r. The remaining factor-recovery step is classical.
2.1 Recovering the factors from the order
If
- r is even, and
- a r/2 != −1 (mod N),
then aʳ − 1 is divisible by N
and factors as
aʳ − 1 = (ar/2
− 1)( ar/2 + 1).
The two greatest common divisors
gcd(ar/2 − 1, N) and
gcd(ar/2 + 1, N)
yield non-trivial factors of N. If r is odd, or if ar/2 = −1 (mod N), choose another base a and repeat.
2.2 Example: N = 21
|
Base a |
Order r |
Outcome |
Reason |
|
4 |
3 |
Fail |
The
order is odd. |
|
5 |
6 |
Fail |
5³ ≡ −1 (mod 21), although the order is even. |
|
2 |
6 |
Success |
2³
= 8, which is neither 1 nor −1 modulo 21. |
For the successful choice a = 2,
gcd(2³ − 1, 21) = gcd(7, 21) = 7,
gcd(2³ + 1, 21) = gcd(9, 21) = 3.
3. Elliptic curves: a hidden two-dimensional relation
Let P be a point of order n, and suppose
the public point Q satisfies
Q = dP,
where d ∈ ℤₙ is the secret scalar. The
elliptic-curve discrete-logarithm problem is to recover d from P and Q.
Define the homomorphism
φ : ℤₙ × ℤₙ → ⟨P⟩, φ(a, b) = aP + bQ.
where ⟨P⟩ is the group with generator P.
The homomorphism φ maps a pair of integer to an elliptic-curve point.
Because Q = dP,
φ(a, b) = (a + bd)P.
Therefore,
(a, b) ∈ ker φ ⇔
a + bd ≡ 0 (mod n).
The kernel is the subgroup
ker φ = { (−bd, b) : b ∈ ℤₙ } = ⟨(d, −1)⟩.
Equivalently, the same subgroup may be
generated by (−d, 1). These two generators differ only by a sign.
3.1 The hidden linear periodicity
The pairs (a, b) and (a + d, b − 1) map to
exactly the same elliptic-curve point:
φ(a + d, b − 1) = (a + d)P + (b − 1)Q
= (a + d)P + (b − 1)dP = (a + bd)P = φ(a,
b).
Thus the function is constant on cosets of the hidden subgroup ⟨(d, −1)⟩. Geometrically, this subgroup defines a hidden direction in the two-dimensional grid ℤₙ × ℤₙ. Shor's discrete-logarithm procedure recovers the subgroup relation. After normalising a recovered non-trivial relation, the secret scalar d can be obtained.
4. Summary
For RSA, Shor's algorithm finds a hidden step along a line; for elliptic curves, it finds a hidden direction in a two-dimensional grid.
The quantum mechanism is essential for efficiency, but it is not required to understand the algebraic objective: identify a hidden subgroup, then use the recovered relation in a classical calculation to expose the secret structure on which the cryptosystem relies.
