1<!-- Author: Simon-Pierre Boucher — simon-pierre.boucher@uqo.ca -->2# 🔐 Beyond the Square-Root Barrier34**UQO Working Paper No. 34** — *Automated Discovery of Algebraic and Algorithmic Shortcuts in Bitcoin Cryptography*56[](paper/main.pdf)7[](requirements.txt)8[](experiments/synthetic_ecdlp/rho_engine)9[](formal/)10[](results/)11[](https://uqo.ca)12[](mailto:simon-pierre.boucher@uqo.ca)1314> **TL;DR** — Can a systematic, automated exploration of secp256k1, ECDSA, BIP340 Schnorr and SHA-256 find a15> computational shortcut the literature has missed? We ran a six-stage discovery pipeline (verified literature16> database → 25 structured hypotheses → exact symbolic checks → seeded experiments with provenance → Lean 417> machine-checked statements → six-way classification) autonomously under a written mandate. Outcome: **no shortcut**;18> every secp256k1 invariant verified twice with exact arithmetic; the libsecp256k1 GLV constants shown to be the19> Eisenstein ideal (π̄−1): a1 = (t−f)/2 − 1, b1 = −f; the "orbit quotient group" conjecture refuted; 6 000 synthetic20> ECDLP instances (20–56 bits) giving α ∈ [0.48, 0.50] and the rho constant 1.254·√n (theory 1.2533); order-621> automorphism classes 2.42× in iterations (√6) but ≈ 1× in wall time in our engine; BIP340 batch verification 3.1×;22> reduced-step SHA-256 diffusion/bias/SAT calibrations far below the published 31-step records; bit-level SHA-25623> identities and signature facts machine-checked. Everything synthetic; nothing bears on deployed systems.2425---2627## 📌 Status2829| Item | Value |30|---|---|31| Version | 1.0 (2026-11-01) — 74 pages, 16 figures, 22 tables, 129 references |32| SSRN | not yet submitted |33| Journal | — (candidate venues: Journal of Cryptology, DCC, IACR ToSC/TCHES depending on emphasis) |34| Code & data | fully reproducible from this repository (synthetic instances only; see Appendix A of the paper) |3536## 🎯 What this paper does3738The mandate (`docs/MANDATE.md`, pasted by the author on 2026-11-01) asks an autonomous research agent to test whether39unexplored algebraic transformations or algorithmic strategies improve on the established attacks on Bitcoin's40primitives — and to reject them rigorously if not. Four axes: (A) secp256k1 structure, (B) algorithmic complexity of41the ECDLP and of signature verification, (C) reduced-step SHA-256, (D) the discovery methodology and formal42verification. Hypotheses live in `hypotheses/` (one file each, 16 mandatory fields), their evaluation in43`research_log/discovery_log.jsonl` and Table 15 of the paper.4445Core objects:4647```48E: y² = x³ + 7 over F_p, p = 2²⁵⁶ − 2³² − 977, #E = n prime49φ(x, y) = (βx, y) = [λ](x, y), End(E) = Z[ω], GLV lattice = (π̄ − 1)·Z[ω]50Q = dG (generic cost Θ(√n); √6 from Aut(E); nothing more)51sG = R + eP (BIP340); H(x) = y (SHA-256, 64 steps)52```5354## 🏆 Headline results5556| Object | Result | Classification |57|---|---|---|58| secp256k1 parameters and invariants (14 facts) | Python = PARI/GP; twist cofactor 220-bit prime; embedding degree 253-bit; no 2-torsion; 4p = t² + 3f² | known, reproduced |59| libsecp256k1 GLV constants | a1 = (t−f)/2 − 1, b1 = −f, a2 = a1 − b1, b2 = a1; lattice = ideal (π̄−1); found by the identity search, then proved | known structure, explicit form |60| Orbit-quotient "group of order n/6" | impossible (proof + 1 500/1 500 counterexamples) | rejected |61| ECDLP scaling, 3 840 generic + 2 400 j=0 instances | α ∈ [0.478, 0.500]; rho 1.254·√n [1.21, 1.30]; BSGS 1.50·√n; kangaroo 1.94·√n | known, reproduced |62| Order-6 automorphism classes | 2.42× [2.19, 2.70] fewer iterations (√6 = 2.449); wall-clock 0.95× in this engine | known, reproduced + implementation observation |63| Automated iteration-function search (25 designs) | nothing below the random-mapping constant; r = 2, 3 walks 3.8× / 2.3× worse | rejected shortcut |64| Parallel DP collision search | 22.1× on 28 threads (M3 Ultra), 14.8× on 16 | known, reproduced |65| Preprocessing | online cost 1.5·√(n/T); per-instance speed-up up to 42× | known, reproduced |66| BIP340 batch verification | 7.9 µs/sig at b = 2048, 3.10× [3.05, 3.16] vs single (k256); saturation explained | known, reproduced |67| Implementations | pure Python 7.4 ms vs libsecp256k1 13.2 µs per Schnorr verify (560×) | empirical |68| SHA-256 reduced steps | full diffusion at step 6 (W_0), no first-order regularity from step 5; generic SAT: preimages only with 16 free bits beyond 16 steps, collisions up to 18 steps (UNSAT for ≤ 8), 9-step local collision reproduced (conforming pairs for all 32 bit positions) | empirical / known |69| Lean 4 (32 s build, no sorry) | Ch/Maj identities, linearity and **bijectivity of Σ0, Σ1, σ0, σ1** (refuting our conjecture that σ0/σ1 are singular), step bijection, schedule inversion, 9-step linearised local collision, ECDSA malleability, Schnorr correctness | machine-checked |7071## 🗂 Repository layout7273```74beyond-square-root-barrier/ (git: wp34_uqo)75├── CLAUDE.md, docs/MANDATE.md # operational summary and the verbatim mandate76├── src/wp34/ # exact-arithmetic library: ec, secp256k1, ecdsa, schnorr (BIP340), sha256, dlp, provenance77├── theory/ # derivation notes + SymPy symbolic checks + cost models78├── experiments/79│ ├── baselines/ # secp256k1_facts.py (Python + PARI/GP), scalar_mult_opcount.py80│ ├── synthetic_ecdlp/ # rho_engine (Rust), ecdlp_study.py, run_batch_remote.py, analyze_ecdlp.py, preprocessing, index-calculus probe81│ ├── signature_benchmarks/ # sigbench (Rust: libsecp256k1 + k256, own Straus/Pippenger), run_bench.py82│ ├── reduced_round_sha256/ # diffusion, bias, CNF encoder, SAT/SMT preimage & collision grids, local collision83│ └── automated_discovery/ # identity_search.py, registry.py (hypothesis registry → discovery log + table)84├── formal/ # Lean 4 project (bv_decide), formal/README.md lists every theorem85├── hypotheses/ # H01–H25 structured records86├── literature/ # db.yaml (82 items), records.md, research_gaps.md, unverified.md87├── results/ # JSON results with provenance blocks (host, versions, seed, command)88├── figures/ # generated figures (copied to paper/figures)89├── tests/ # pytest gates (core, DLP reference, Rust engine fixtures, signature cross-checks, CNF)90├── scripts/ # make_tables.py (numbers.tex), write_hypotheses.py, fig_ec_geometry.py91├── research_log/ # dated narrative entries + discovery_log.jsonl92└── paper/ # main.tex, sections/, appendix/, tables/ (generated), figures/, references.bib (129 verified) → main.pdf93```9495## 🚀 Quick start9697```bash98uv venv --python 3.12 .venv && uv pip install -r requirements.txt99brew install pari cadical kissat z3 # PARI/GP (point counting), SAT/SMT solvers100.venv/bin/python -m pytest -q tests/ # cross-implementation gates101.venv/bin/python experiments/baselines/secp256k1_facts.py102.venv/bin/python experiments/automated_discovery/identity_search.py103cargo build --release --manifest-path experiments/synthetic_ecdlp/rho_engine/Cargo.toml104.venv/bin/python experiments/synthetic_ecdlp/ecdlp_study.py all # job files (PARI/GP)105.venv/bin/python experiments/synthetic_ecdlp/run_batch_remote.py --engine experiments/synthetic_ecdlp/rho_engine/target/release/rho_engine \106 --jobs results/synthetic_ecdlp/scaling_generic.jobs.json --out results/synthetic_ecdlp/scaling_generic_$(hostname -s).json --parallel 8107.venv/bin/python experiments/synthetic_ecdlp/analyze_ecdlp.py108(cd formal && lake build)109.venv/bin/python experiments/automated_discovery/registry.py && .venv/bin/python scripts/make_tables.py110(cd paper && make)111```112113## 🔬 Integrity114115Synthetic curves and keys only; no real wallets, addresses, third-party keys or blockchain data; full-strength116primitives analysed through exact algebra and legitimate implementations. Every number in the paper is generated from117a saved result file by `scripts/make_tables.py` or `analyze_ecdlp.py` (LaTeX macros in `paper/tables/numbers*.tex`).118119## 📝 Notes120121- Series standard: `Recherche-UQO/HARMONISATION.md`. Deviation: the mandate's required directories (`theory/`,122 `experiments/`, `formal/`, `hypotheses/`, `literature/`, `research_log/`) are kept at the root in addition to the123 standard `src/`, `scripts/`, `results/`, `figures/`, `paper/`.124- Built autonomously by Claude Code (Claude Fable 5.1) on 2026-11-01 on the author's laptop and MacLustr nodes125 M3U96a, M3U96b, M2U64; see `research_log/`.126