[Submitted on 19 Sep 2026 (v1), last revised 19 Sep 2026 (this version, v2)]
Title:An 833-Qubit secp256k1 Discrete-Logarithm Algorithm with Machine-Checked Correctness and Resource Bounds
Abstract: We describe a quantum algorithm that recovers every nonzero secp256k1 private scalar with probability greater than 99 percent in one execution, using 833 logical qubits and at most 16,923,769,370 Toffoli-class operations. Lean proofs connect the generated hybrid program to exact group arithmetic, restored quantum workspace, its Fourier-output distribution, a bounded classical decoder, and pathwise and expected resource counts. The construction combines packed Euclidean arithmetic, five-bit scalar windows, complete point translations, an initial public lookup, and measurement with phase correction. The stated Toffoli bound uses a 26-bit initial lookup with a 4 GiB packed public table and at most 34,493,956,094 lookup CNOTs. Smaller tables give nearby Toffoli bounds. The decoder uses 514 scalar multiplications, at most 66,049 comparisons, and at most one modular inversion. We give the algorithm, the recovery argument, the allocation and cost derivations, and a map to the checked statements. We compare published low-qubit and low-Toffoli constructions, distinguishing universal formal proofs, circuit tests, statistical guarantees, and cryptographic attestations of tests. The result concerns ideal logical operations with exact Fourier phases. Physical error correction, phase synthesis, and complete depth and CNOT accounting require further analysis.
| Comments: | 17 pages. Author and affiliation corrected. |
| Subjects: | Logic in Computer Science (cs.LO); Computational Complexity (cs.CC) |
| Cite as: | marXiv:2609.00013 [cs.LO] (or marXiv:2609.00013v2 [cs.LO] for this version) |
Submission history
[v1] Sat, 19 Sep 2026 16:57:02 UTC (380 KB)
[v2] Sat, 19 Sep 2026 17:14:56 UTC (379 KB)
Related work
- marXiv:2609.00003
- This stand-alone report gives the completed 833-qubit algorithm, extending the intermediate optimization report.
- marXiv:2609.00004
- This stand-alone report incorporates the arithmetic reductions and gives the complete algorithm, recovery argument, and literature comparison.