|q⟩
Bad Qubits
Play
Quest
Questions
Learn
Playground
☕
← Question Bank
Multiple choice
Shor's algorithm factors
N
=
15
N = 15
N
=
15
using base
a
=
7
a = 7
a
=
7
with found period
r
=
4
r = 4
r
=
4
. A factor is
gcd
(
a
r
/
2
−
1
,
N
)
=
gcd
(
7
2
−
1
,
15
)
\gcd(a^{r/2} - 1, N) = \gcd(7^2 - 1, 15)
g
cd
(
a
r
/2
−
1
,
N
)
=
g
cd
(
7
2
−
1
,
15
)
. What is this factor?
🔬 try it before you answer
3
48
1
5
Check answer