id: H08 title: Measured ECDLP cost scales as n^0.5 with constants matching random-mapping theory axis: B kind: algorithmic statement: Fitting T(n) = a n^α (log n)^β to measured group-operation counts for BSGS, rho (Floyd/Brent/DP) and kangaroo on 20–48-bit prime-order curves gives α = 0.50 ± 0.02 and constants ≈ 2 (BSGS), ≈ √(π/2) ≈ 1.25 (rho), ≈ 2 (kangaroo on the full interval). motivation: Reproducible baseline before any novel algorithm (mandate §9). assumptions: Teske r = 20 walk; distinguished-point fraction tuned per size. expected_contribution: Baseline table and log–log scaling figure with bootstrap confidence intervals. related_work:
- pollard1978monte
- teske2001random
- vanoorschot1999parallel
- shanks1971class
- pollard2000kangaroos
- flajolet1990random possible_counterexamples: α significantly different from 0.5, or a rho constant below √(π/2) (which would contradict the random-mapping model). verification_strategy: experiments/synthetic_ecdlp/run_scaling.py on the cluster; analysis script fits and bootstraps. computational_budget: ≈ 4 node-hours status: evaluated classification: known_reproduced evidence:
- results/synthetic_ecdlp/scaling_generic_M3U96a.json
- results/synthetic_ecdlp/scaling_j0_M2U64.json
- results/synthetic_ecdlp/analysis.json verdict: '3 840 verified instances, 20–56 bits: fitted α ∈ [0.478, 0.500] (≥ 32 bits) for all seven configurations with CIs touching 0.5; pooled rho constant 1.254·√n [1.21, 1.30] on 480 runs vs √(π/2) = 1.2533; BSGS 1.50·√n (x-keyed ±j table); kangaroo 1.94·√n; Floyd 2.67·√n, Brent 1.65·√n.'
H08 — Measured ECDLP cost scales as n^0.5 with constants matching random-mapping theory
Fitting T(n) = a n^α (log n)^β to measured group-operation counts for BSGS, rho (Floyd/Brent/DP) and kangaroo on 20–48-bit prime-order curves gives α = 0.50 ± 0.02 and constants ≈ 2 (BSGS), ≈ √(π/2) ≈ 1.25 (rho), ≈ 2 (kangaroo on the full interval).