MATH36206 Advanced Cryptology Week 3

3 Shor’s algorithm
This relatively simple factoring algorithm provides a great starting point for exploring the impacts
of quantum computing and importance of time complexity theory. Assume that we want to factor
a modulus, N = p · q, for the usual reasons. Here is a classical version of Shor’s algorithm (modified
to be functional and easy to implement):

3.1 Shor’s algorithm

1. randomly select a base 1 < g < N .

2. compute powers of g mod N : g 2 , g 3 , ..., g 9001 , ...

3. Find the period t such that g x ≡ g x+t mod N .

4. If t is even, compute a = g t/2 − 1 and b = g t/2 + 1.

5. Compute the GCD(a, N ) and GCD(b, N ) to get the factors p and q.

3.2 examples of factoring N = 221

With base g = 38 we find a period of t = 4 and p = 13 and q = 17:

With base g = 5 we find a period of t = 16 and p = 13 and q = 17:

joshua.schneider@sheridancollege.ca page 1
MATH36206 Advanced Cryptology Week 3

3.3 examples of factoring N = 221; limitations of the algorithm

If GCD(g, N ) = ̸ 1, then the algorithm has (trivially) found a factor without completing steps
t
2,3,4,5. Shor’s algorithm will fail if t is odd, or if g 2 ≡ −1 mod N :

3.3.1 GCD(g, N ) ̸= 1
With base g = 26 we find a period of t = 8 but can only get the factor q directly because
GCD(a, N )=1:

This case results in the successful factorization of N but in many implementations these types of
cases are screened out by computing GCD(g, N ) before computing steps 2,3,4,5. If GCD(g, N ) ̸= 1
then the algorithm stops (because it has already found the factor).

3.3.2 t is odd
With base g = 35 we find an odd period:

In this case we cannot factor, and we go back and select another random base g.
t
3.3.3 g 2 ≡ −1 mod N
With base g = 47 we find a period of t = 4 but can’t get any factors because b ≡ 0 mod N and
GCD(a, N )=1:

In this case we cannot factor, and we go back and select another random base g.

joshua.schneider@sheridancollege.ca page 2
MATH36206 Advanced Cryptology Week 3

3.4 Theory
If GCD(g, N )=1, then by Euler’s theorem we have that g ϕ(N ) ≡ 1 mod N .

So when GCD(g, N )=1 a period t exists that is either equal to ϕ(N ) or it divides ϕ(N ) such
that if g x ≡ r mod N then g x+t ≡ r mod N .

With x = 0 we obtain g t ≡ 1 mod N .

gt ≡ 1 mod N
t
g −1≡0 mod N
t t
(g − 1)(g + 1) ≡ 0
2 2 mod N
(a)(b) ≡ 0 mod N

Assuming that neither a or b are a multiple of N then a and b contains factors of N .

joshua.schneider@sheridancollege.ca page 3
MATH36206 Advanced Cryptology Week 3

Exercises
3.1 Factor N using Shor’s algorithm with the given base g.
State the period, t, the values a and b, and the factors p and q.

a) N = 77, g = 12.
b) N = 299, g = 91.
c) N = 1147, g = 249.
d) N = 1073, g = 117.
e) N = 2993, g = 27.

3.2 Determine why N cannot be factored using Shor’s algorithm with the given base:

a) N = 77, g = 23
b) N = 77, g = 6
c) N = 2993, g = 877

joshua.schneider@sheridancollege.ca page 4
MATH36206 Advanced Cryptology Week 3

3.5 Time complexity

Step 2. in the algorithm is the bottleneck. We may have to exponentiate g x mod N up to ϕ(N )
times to be able to find the period. If we let n be the number of bits required to encode N then
n = log2 (N ) and step 2. will take O(2n ) steps, which is exponential time (and not polynomial time).
√
Compare this to trial division where up to N divisions may be required to find a factor. This
requires O(2n/2 ) steps, which is also exponential time. So using Shor’s classical algorithm on a
standard computer is no better than trial division.

The trick is to implement step 2. on a quantum computer that can exponentiate g x mod N
using a superposition of all values of x all at once, and then measure the computation for some
random remainder r. Then what will be left (apparently!) is an array of exponents, x, that yield
the same remainder r mod N which can be used to find the period t. Step 5. is the only other
computationally significant step, but it can be accomplished in polynomial time using the Euclidean
Algorithm.

3.6 Problem reductions

Shor’s algorithm takes advantage of the fact that the problem of factoring can be reduced to the
problem of order finding using a reduction.

F ACT OR = {N |N = pq, for integers p, q > 1}

ORDER = {⟨N, g, t⟩|t is the smallest positive integer such that g t ≡ 1 mod N }

Order finding is the problem of finding the smallest t ≥ 1 such that g t ≡ 1 mod N . (We have
called t the period but it is also called the order of g).

3.7 Quantum computing and information security

Under the assumption that quantum computers are feasible (for computations involving more than
a few bits...):

• The problems of factoring and order finding will no longer require exponential time to solve.

• Cryptosystems that are based on integer factorization (like RSA) will no longer be secure.

• New cryptosystems based on “more computationally difficult” problems will be required in

the short term.

joshua.schneider@sheridancollege.ca page 5
MATH36206 Advanced Cryptology Week 3

Exercises
3.3 Let F ACT OR = {N |N = pq, for integers p, q > 1}

a) Is N = 23 ∈ F ACT OR?
b) Is N = 377 ∈ F ACT OR?
c) Is N = 101 ∈ F ACT OR?

3.4 Let ORDER = {⟨N, g, t⟩|t is the smallest positive integer such that g t ≡ 1 mod N }

a) Is ⟨13, 6, 12⟩ ∈ ORDER?

b) Is ⟨13, 3, 6⟩ ∈ ORDER?
c) Is ⟨13, 3, 3⟩ ∈ ORDER?
d) Is ⟨11, 8, 9⟩ ∈ ORDER?
e) Is ⟨33, 5, 10⟩ ∈ ORDER?
f) Is ⟨33, 5, 32⟩ ∈ ORDER?

joshua.schneider@sheridancollege.ca page 6
MATH36206 Advanced Cryptology Week 3

Answers
3.1 t = 6, a = 33, b = 35, p = GCD(77, 33) = 11, q = GCD(77, 35) = 7
t = 2, a = 90, b = 92, q = GCD(299, 92) = 23
t = 6, a = 775, b = 777, p = GCD(1147, 775) = 31, q = GCD(1147, 777) = 37
t = 4, a = 812, b = 814, p = GCD(1073, 812) = 29, q = GCD(1073, 814) = 37
t = 8, a = 1679, b = 1681, p = GCD(2993, 1679) = 73, q = GCD(2993, 1681) = 41

3.2 t = 3
10
t = 10 but g 2 ≡ −1 mod 77
t=5

3.3 no
yes
no

3.4 yes
no
yes
no
yes
no

joshua.schneider@sheridancollege.ca page 7