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