08 / Advanced algorithms · LESSON 18 / 27 · 25 MIN
Shor, order finding and cryptographic limits.
Relate modular periodicity to factoring without overclaiming.
f(x)=aˣ mod N aʳ ≡ 1 (mod N)
Reduce factoring to order
Choose a coprime a and find its order r modulo N. If r is even and a^(r/2) is not −1 modulo N, gcd(a^(r/2)±1,N) can yield factors. For N=15 and a=2, the sequence 1,2,4,8 repeats with r=4.
Quantum and classical work
Quantum period finding uses modular arithmetic and Fourier structure; continued fractions and gcd calculations are classical. Unhelpful choices require retries. Modular exponentiation is a substantial reversible circuit, not a free oracle.
Security timeline
Shor threatens RSA and related discrete-log cryptosystems on sufficiently capable fault-tolerant machines. This simulator is not such hardware and cannot break modern RSA keys. Post-quantum migration is a systems project; symmetric cryptography has different considerations.
CHECK YOUR UNDERSTANDING
Lesson quiz
Answer all 2 questions correctly. Unlimited retries.
0/2 answered
Checking your account…
