1---2id: H123title: 'Discrete logarithms with preprocessing: online cost ≈ 1.5·√(n/T) after storing T distinguished points'4axis: B5kind: algorithmic6statement: With T stored DPs produced by walks of length W = √(n/T), the online phase needs c·√(n/T) group operations with7 c ≈ 1.5, i.e. a per-instance speed-up of ≈ √T/1.5 over plain rho, consistent with ST² = Ω̃(n).8motivation: Non-uniform attacks are the one known way to go below √n per instance; measure the constant.9assumptions: Walk independent of the target (M_j = u_j G); DP mask ≈ log₂ W bits.10expected_contribution: Quantified reproduction of Bernstein–Lange on 22–26-bit groups (Python) and larger (Rust).11related_work:12- bernstein2013nonuniform13- lee2011generic14- corrigangibbs2018discrete15possible_counterexamples: Online cost not decreasing as 1/√T.16verification_strategy: experiments/synthetic_ecdlp/preprocessing_python.py (60 instances per cell).17computational_budget: ≈ 10 min laptop18status: evaluated19classification: known_reproduced20evidence:21- results/synthetic_ecdlp/preprocessing_python.json22verdict: Online/√(n/T) ratio 1.48–1.67 across T = 2^4 … 2^12 at 22 and 26 bits; per-instance speed-up 2.6× → 42× as predicted23 by √T scaling.24commands:25- .venv/bin/python experiments/synthetic_ecdlp/preprocessing_python.py26---2728# H12 — Discrete logarithms with preprocessing: online cost ≈ 1.5·√(n/T) after storing T distinguished points2930With T stored DPs produced by walks of length W = √(n/T), the online phase needs c·√(n/T) group operations with c ≈ 1.5, i.e. a per-instance speed-up of ≈ √T/1.5 over plain rho, consistent with ST² = Ω̃(n).31