id: H12 title: 'Discrete logarithms with preprocessing: online cost ≈ 1.5·√(n/T) after storing T distinguished points' axis: B kind: algorithmic statement: With 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). motivation: Non-uniform attacks are the one known way to go below √n per instance; measure the constant. assumptions: Walk independent of the target (M_j = u_j G); DP mask ≈ log₂ W bits. expected_contribution: Quantified reproduction of Bernstein–Lange on 22–26-bit groups (Python) and larger (Rust). related_work:

• bernstein2013nonuniform
• lee2011generic
• corrigangibbs2018discrete possible_counterexamples: Online cost not decreasing as 1/√T. verification_strategy: experiments/synthetic_ecdlp/preprocessing_python.py (60 instances per cell). computational_budget: ≈ 10 min laptop status: evaluated classification: known_reproduced evidence:
• results/synthetic_ecdlp/preprocessing_python.json verdict: 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 predicted by √T scaling. commands:
• .venv/bin/python experiments/synthetic_ecdlp/preprocessing_python.py

# H12 — Discrete logarithms with preprocessing: online cost ≈ 1.5·√(n/T) after storing T distinguished points

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