1"""Discrete logarithms with preprocessing (Bernstein–Lange 2013 "non-uniform cracks"; Corrigan-Gibbs–Kogan 2018 bound).23Offline: T distinguished points are produced by random walks of mean length W = ⌈√(n/T)⌉ (DP mask with ≈ log2 W bits)4and stored with their logarithms (walks start at known multiples of G, so each DP has a known log).5Online: a walk from Q (random start a·G + Q) runs until it reaches a stored DP, at which point d is recovered.6Prediction: online cost ≈ n/(T·W) ≈ √(n/T) group operations; total (T·W + online) is never below √n but the7*per-instance* cost drops as 1/√T — the "non-uniform" speedup. ST² = Ω̃(n) (Corrigan-Gibbs–Kogan) bounds this.8Pure-Python reference on 2^22–2^26 groups; the Rust engine repeats this at larger sizes.9"""10import argparse, math, random, sys, time, pathlib, statistics as st11ROOT = pathlib.Path(__file__).resolve().parents[2]12sys.path.insert(0, str(ROOT / "src"))13from wp34.ec import random_prime_order_curve14from wp34.dlp import RAddingWalk15from wp34.provenance import record161718def experiment(bits, T, instances, rng, r=20):19 E = random_prime_order_curve(bits, rng)20 n, G = E.n, E.G21 # walk independent of Q: M_j = u_j G (v_j = 0) so the logs of all visited points are known offline22 walk = RAddingWalk(E, G, G, n, r, rng)23 walk.v = [0] * r24 walk.M = [E.mul(u, G) for u in walk.u]25 W = max(2, math.isqrt(n // T))26 dp_bits = max(1, round(math.log2(W)))27 mask = (1 << dp_bits) - 128 E.ops.reset()29 table = {}30 offline_steps = 031 max_len = 20 * (1 << dp_bits)32 while len(table) < T:33 a = rng.randrange(1, n); P = E.mul(a, G); L = 034 while P is not None and (P[0] & mask) != 0 and L < max_len:35 P, a, _ = walk.step(P, a, 0); L += 136 offline_steps += L37 if P is not None and (P[0] & mask) == 0 and P not in table:38 table[P] = a39 offline_ops = E.ops.group_ops()40 online = []41 for _ in range(instances):42 d = rng.randrange(1, n); Q = E.mul(d, G)43 E.ops.reset()44 found = None45 while found is None:46 a = rng.randrange(1, n); P = E.add(E.mul(a, G), Q); L = 0 # P = (a + d) G47 E.ops.reset()48 while True:49 if P is None:50 break51 if (P[0] & mask) == 0:52 if P in table:53 found = (table[P] - a) % n54 break55 P, a, _ = walk.step(P, a, 0); L += 156 if L > 50 * max_len:57 break58 online.append(E.ops.group_ops()) if found is not None else None59 assert found == d60 return {"bits": bits, "n": str(n), "T": T, "W": W, "dp_bits": dp_bits, "offline_group_ops": offline_ops,61 "offline_steps": offline_steps, "table_entries": len(table), "instances": instances,62 "online_mean": st.mean(online), "online_median": st.median(online), "online_sd": st.pstdev(online),63 "online_ci95_halfwidth": 1.96 * st.pstdev(online) / math.sqrt(len(online)),64 "pred_sqrt_n_over_T": math.sqrt(n / T), "sqrt_n": math.sqrt(n),65 "ratio_online_to_pred": st.mean(online) / math.sqrt(n / T),66 "per_instance_speedup_vs_sqrt_n": math.sqrt(n) / st.mean(online)}676869def main():70 ap = argparse.ArgumentParser(); ap.add_argument("--seed", type=int, default=34)71 ap.add_argument("--out", default=str(ROOT / "results/synthetic_ecdlp/preprocessing_python.json"))72 a = ap.parse_args(); rng = random.Random(a.seed); t0 = time.time(); rows = []73 for bits in (22, 26):74 for T in (2**4, 2**6, 2**8, 2**10, 2**12):75 r = experiment(bits, T, 60, rng); rows.append(r)76 print(f"{bits}b T={T:5d} W={r['W']:5d} offline {r['offline_group_ops']:9d} online {r['online_mean']:9.1f} ± {r['online_ci95_halfwidth']:.1f} pred √(n/T) {r['pred_sqrt_n_over_T']:8.1f} ratio {r['ratio_online_to_pred']:.2f} speedup/inst {r['per_instance_speedup_vs_sqrt_n']:.1f}", flush=True)77 record("dlog_with_preprocessing_python", {"r": 20, "instances": 60}, {"rows": rows}, seed=a.seed, out=a.out, started=t0)787980if __name__ == "__main__":81 main()82