---
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.