Factoring from a Period

List the powers of a modulo N until they repeat. Turn the period into the two primes with two gcds, and see which bases fail.

Quantum algorithmsFactoringdemo

Objectives

Find the period r of a^x mod N for a toy RSA modulus, including the RSA lecture's 187.
Compute the factors from r with gcd(a^(r/2) − 1, N) and gcd(a^(r/2) + 1, N), and name the two cases that fail.
Explain why finding the period is the only step that needs a quantum computer.

20%

The classical half of Shor’s algorithm: list the powers of a, find where they repeat, and turn that into the primes.

a^r mod N = 1 (a^(r/2) − 1)(a^(r/2) + 1) = a^r − 1 p = gcd(a^(r/2) − 1, N)

Pick a modulus and a base

N is a toy RSA modulus: the product of two different odd primes. The attacker knows N but not the primes. Pick any base a between 2 and N − 1. If gcd(a, N) is not 1, a already shares a prime with N, and the attacker is done. Otherwise the attacker needs the period.

modulus N = p x q

base a

gcd(a, N)

period r

List the powers until they repeat

Compute a^x mod N for x = 0, 1, 2, …. The list starts at 1 and comes back to 1. The period r is the first x > 0 where it does; after that the list repeats. Each 1 is underlined, and a rule marks where each new period starts.

x=01

x=17

x=24

x=313

x=41

x=57

x=64

x=713

x=81

7^4 mod 15 = 1, and no smaller x > 0 gives 1, so r = 4.

Turn the period into factors

Because a^r mod N = 1, the number a^r − 1 is a multiple of N. If r is even, it splits: a^r − 1 = (a^(r/2) − 1)(a^(r/2) + 1). When neither bracket is itself a multiple of N, each one shares a prime with N, and a gcd finds it. The gcd is fast even for 2048-bit numbers.

the checks

1. Is r even? r = 4: yes 2. h = a^(r/2) mod N 7^2 mod 15 = 4 3. Is h different from N − 1 = 14? yes 4. gcd(h − 1, N) = gcd(3, 15) = 3 gcd(h + 1, N) = gcd(5, 15) = 5

15 = 3 x 5. The private key of this toy RSA modulus is now computable.

Most bases work

For N = 15 = 3 x 5, 6 of the 7 bases with gcd(a, N) = 1 give the factors (86%). For a product of two different odd primes, at least half of them always work, so a few random tries are enough. Rows with a rule at the left work.

Every base coprime to 15, its period, and whether the period gives a factor.
a	r	a^(r/2) mod N	Result
2	4	4	3 x 5
4	2	4	3 x 5
7	4	4	3 x 5
8	4	4	3 x 5
11	2	11	5 x 3
13	4	4	3 x 5
14	2	14	fails: h = N − 1

Why the period is the hard part

Every step on this page is fast except the list of powers. Here the longest period is 4, so the list is short. For a 2048-bit RSA modulus the period can have about 2048 bits, and listing that many powers is impossible. No classical method is known that finds the period quickly; that would also factor N quickly.

Shor's algorithm replaces only the list. A quantum computer finds r in a number of steps that grows polynomially with the bit length of N. The next page simulates that quantum step for small N, and then does the classical steps of this page with the r it finds.

step 1/5

CPE 645 / CS 685

Factoring from a Period

A Three-Qubit Circuit

Shor's Quantum Step