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 = 35

and

a = 4

, with

\gcd(4,35)=1

. ((a)) Find the order

r

4

modulo

35

by repeated squaring or successive multiplication until the orbit returns to

1

. ((b)) Use

4^{r/2} \bmod 35

and the gcd construction of the factoring-to-order-finding reduction to find a factor of

35

other than

1

and

35

itself.

Browse the problem library