id: H06 title: No known algebraic attack applies to secp256k1; prime-field index calculus with m = 2 costs ≫ √n axis: A kind: algebraic statement: n ≠ p; the embedding degree exceeds 10^6 (in fact it is the full order of p mod n); the twist has a 220-bit prime cofactor; x³ + 7 has no roots (no 2-torsion) and 7 is a non-residue (no x = 0 points); Semaev decomposition with |F| ≈ √p succeeds for a random point with probability 1 − exp(−|F|²/2n) but the cost of a relation is |F|/rate ≫ √n per relation and |F| relations are needed. motivation: 'Section 3.2 of the mandate: applicability limits of algebraic attacks.' assumptions: Standard reductions (MOV/Frey–Rück, Semaev/Smart/Satoh–Araki, Semaev 2004). expected_contribution: Exact verification table plus an empirical decomposition experiment on 16–28-bit curves. related_work:
- menezes1993reducing
- frey1994remark
- smart1999discrete
- semaev2004summation
- gaudry2009index
- diem2011discrete
- petit2012elliptic
- bernstein2014safecurves possible_counterexamples: A small embedding degree or anomalous order (both excluded exactly). verification_strategy: secp256k1_facts.py (exact) and experiments/synthetic_ecdlp/index_calculus_probe.py. computational_budget: seconds status: evaluated classification: known_reproduced evidence:
- results/baselines/secp256k1_facts.json
- results/synthetic_ecdlp/index_calculus_probe.json verdict: All exclusion criteria verified; measured decomposition rates match the Poisson prediction within sampling error; even with a free decomposition oracle the relation stage costs ≥ 2.4√n and the linear algebra |F|² ≫ √n. commands:
- .venv/bin/python experiments/synthetic_ecdlp/index_calculus_probe.py
H06 — No known algebraic attack applies to secp256k1; prime-field index calculus with m = 2 costs ≫ √n
n ≠ p; the embedding degree exceeds 10^6 (in fact it is the full order of p mod n); the twist has a 220-bit prime cofactor; x³ + 7 has no roots (no 2-torsion) and 7 is a non-residue (no x = 0 points); Semaev decomposition with |F| ≈ √p succeeds for a random point with probability 1 − exp(−|F|²/2n) but the cost of a relation is |F|/rate ≫ √n per relation and |F| relations are needed.