Take and , with…

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Order finding and Shor's factoring algorithm

Problem

Take

N = 21

and

a = 10

, with

\gcd(10,21)=1

. ((a)) Find the order

r

10

modulo

21

by listing successive powers

10^1, 10^2, \ldots \pmod{21}

until the orbit returns to

1

. ((b)) Given that

r

is even, compute

10^{r/2} \bmod 21

and use it, with the identity

(a^{r/2}-1)(a^{r/2}+1)\equiv 0 \pmod{21}

, to extract a factor of

21

other than

1

and

21

itself, from

\gcd(10^{r/2}-1, 21)

and

\gcd(10^{r/2}+1, 21)

Browse the problem library