id: H11 title: 'Time–memory trade-off: BSGS with memory m costs m + n/m operations; rho with DP density θ stores ≈ θ·√(πn/2) points' axis: B kind: algorithmic statement: Measured (time, memory) points for BSGS at m ∈ {n^0.25 … n^0.5} and for DP-rho at several θ lie on the predicted curves; BSGS is deterministic and rho has coefficient of variation ≈ 0.52 (Rayleigh). motivation: 'Mandate §9: report the time–memory trade-off for each algorithm.' assumptions: Hash-table memory counted as entries × bytes. expected_contribution: Trade-off figure. related_work:
- shanks1971class
- vanoorschot1999parallel
- bernstein2012two possible_counterexamples: Deviation from m + n/m (would indicate an implementation error). verification_strategy: Rust engine bsgs --memory sweep; rho --dp sweep. computational_budget: ≈ 1 node-hour status: evaluated classification: known_reproduced evidence:
- results/synthetic_ecdlp/tmto_M2U64.json
- results/synthetic_ecdlp/analysis.json verdict: BSGS cost matches m + n/(2m) within 7.8 % for m from 2^10 to 2^20 at 36 bits; DP-rho at 40 bits spans 1.17–4.95 M operations as the DP density goes from 2^-12 (optimum, ≈ √(πn/2)) to 2^-2 (restart-dominated) and 2^-14 (overshoot-dominated).
H11 — Time–memory trade-off: BSGS with memory m costs m + n/m operations; rho with DP density θ stores ≈ θ·√(πn/2) points
Measured (time, memory) points for BSGS at m ∈ {n^0.25 … n^0.5} and for DP-rho at several θ lie on the predicted curves; BSGS is deterministic and rho has coefficient of variation ≈ 0.52 (Rayleigh).