Challenge 3: Breaking RSA Classically — Shor's Order-Finding Circuits

# Overview

Subnet 63's third challenge brings the network into contact with real-world quantum computing for the first time. Where peaked circuits tested provable quantum advantage and hidden stabilizers explored Clifford circuit obfuscation, this challenge tackles the problem that put quantum computing on the map: breaking RSA encryption via Shor's algorithm.

Why Shor's Algorithm Matters

RSA security relies on the practical difficulty of factoring a semiprime N = pq into its prime components. Peter Shor showed that a quantum computer can solve this in polynomial time by reducing factoring to group-theoretic order-finding, then extracting the order via quantum phase estimation. This isn't a niche algorithm — it's the foundational example of why coherent quantum devices are fundamentally different from classical ones.

How the Challenge Works

Miners receive a quantum circuit implementing quantum phase estimation on modular multiplication by some a modulo N. They must execute the circuit and compute the order r of the multiplication — the core subroutine in Shor's factoring algorithm.

Unlike the previous challenges, these circuits mix quantum execution with classical post-processing: miners analyze the output probability distribution or measurement outcomes to recover the order, then apply number-theoretic techniques to extract factors. This mirrors how real-world quantum algorithms actually work.

What Makes This Challenge Different

From the subnet's perspective, order-finding circuits are an excellent addition because quantum phase estimation is well-ordered — circuits are fast to generate in a way that depends only weakly on problem content. This contrasts sharply with hidden stabilizers (which required obfuscation) and peaked circuits (which required tensor network optimization). Order-finding circuits scale freely to larger qubit counts.

Strategies for Miners

The paper details several approaches beyond the basic continued-fractions recovery:

• Single-sample and multi-sample recovery — continued fraction convergents from QPE outputs, with rapid convergence as samples accumulate
• Peak spacing via GCD — exploiting the regular spacing of QPE output peaks to directly estimate the order
• Lattice-based methods — casting multi-sample recovery as a short-vector problem, competitive with number-theoretic approaches
• Bayesian and MLE estimators — scoring candidate orders against Dirichlet-kernel values, particularly effective with tight shot budgets

The paper provides a basic reference implementation, but miners are encouraged to innovate on both the quantum and classical steps of the algorithm.

Read the Full Paper

The complete technical description covers the number theory foundations, quantum phase estimation, Shor's algorithm mechanics, and advanced miner strategies with full mathematical treatment.

[Download the paper (PDF)](/shors-order-finding.pdf)