1"""Operation counts for scalar multiplication on secp256k1: double-and-add, wNAF, GLV + interleaved wNAF.23Counts group additions and doublings (affine model) for random 256-bit scalars; the GLV decomposition is the4published libsecp256k1 lattice basis re-verified in secp256k1_facts.py. Writes results/baselines/scalar_mult_opcount.json.5"""6import argparse, json, random, sys, time, pathlib, statistics as st7ROOT = pathlib.Path(__file__).resolve().parents[2]8sys.path.insert(0, str(ROOT / "src"))9from wp34 import secp256k1 as k110from wp34.ec import Curve11from wp34.provenance import record1213E: Curve = k1.CURVE14phi = lambda P: (k1.beta * P[0] % k1.p, P[1])151617def wnaf(k: int, w: int):18 naf = []19 while k > 0:20 if k & 1:21 d = k % (1 << w)22 if d >= (1 << (w - 1)):23 d -= 1 << w24 naf.append(d); k -= d25 else:26 naf.append(0)27 k >>= 128 return naf293031def mul_glv_interleaved(k: int, P, w: int = 4):32 """[k]P = [k1]P + [k2]φ(P) with |k_i| ≲ √n, interleaved wNAF (Straus/Shamir with signed windows)."""33 k1_, k2_ = k1.glv_decompose(k)34 P1, P2 = P, phi(P)35 if k1_ < 0: k1_, P1 = -k1_, E.neg(P1)36 if k2_ < 0: k2_, P2 = -k2_, E.neg(P2)37 tabs = []38 for B in (P1, P2):39 twoB = E.double(B)40 t = [B]41 for _ in range((1 << (w - 2)) - 1):42 t.append(E.add(t[-1], twoB))43 tabs.append(t)44 n1, n2 = wnaf(k1_, w), wnaf(k2_, w)45 L = max(len(n1), len(n2))46 n1 += [0] * (L - len(n1)); n2 += [0] * (L - len(n2))47 R = None48 for i in range(L - 1, -1, -1):49 R = E.double(R)50 for d, t in ((n1[i], tabs[0]), (n2[i], tabs[1])):51 if d > 0: R = E.add(R, t[(d - 1) // 2])52 elif d < 0: R = E.add(R, E.neg(t[(-d - 1) // 2]))53 return R545556def main():57 ap = argparse.ArgumentParser(); ap.add_argument("--seed", type=int, default=34); ap.add_argument("--n", type=int, default=200)58 ap.add_argument("--out", default=str(ROOT / "results/baselines/scalar_mult_opcount.json"))59 a = ap.parse_args(); rng = random.Random(a.seed); t0 = time.time()60 methods = {61 "double_and_add": lambda k, P: E.mul(k, P),62 "wnaf_w4": lambda k, P: E.mul_wnaf(k, P, 4),63 "wnaf_w5": lambda k, P: E.mul_wnaf(k, P, 5),64 "glv_wnaf_w4": lambda k, P: mul_glv_interleaved(k, P, 4),65 "glv_wnaf_w5": lambda k, P: mul_glv_interleaved(k, P, 5),66 }67 rows = {m: {"add": [], "dbl": [], "total": [], "time_s": []} for m in methods}68 for i in range(a.n):69 k = rng.randrange(1, k1.n)70 P = E.mul(rng.randrange(1, k1.n), E.G)71 ref = None72 for m, f in methods.items():73 E.ops.reset(); t = time.perf_counter(); R = f(k, P); dt = time.perf_counter() - t74 if ref is None: ref = R75 assert R == ref, (m, i)76 rows[m]["add"].append(E.ops.add); rows[m]["dbl"].append(E.ops.dbl)77 rows[m]["total"].append(E.ops.add + E.ops.dbl); rows[m]["time_s"].append(dt)78 summary = {}79 base = st.mean(rows["double_and_add"]["total"])80 for m, r in rows.items():81 summary[m] = {"add_mean": st.mean(r["add"]), "dbl_mean": st.mean(r["dbl"]), "total_mean": st.mean(r["total"]),82 "total_sd": st.pstdev(r["total"]), "total_min": min(r["total"]), "total_max": max(r["total"]),83 "speedup_vs_double_and_add_ops": base / st.mean(r["total"]),84 "time_mean_ms": 1000 * st.mean(r["time_s"])}85 # GLV sub-scalar sizes86 sizes = []87 for _ in range(2000):88 k = rng.randrange(1, k1.n); a1_, a2_ = k1.glv_decompose(k)89 sizes.append((abs(a1_).bit_length(), abs(a2_).bit_length()))90 summary["glv_subscalar_bits"] = {"k1_max": max(s[0] for s in sizes), "k2_max": max(s[1] for s in sizes),91 "k1_mean": st.mean(s[0] for s in sizes), "k2_mean": st.mean(s[1] for s in sizes), "samples": 2000}92 record("scalar_mult_opcount_secp256k1", {"n_scalars": a.n, "model": "affine, counts group add/dbl"}, summary,93 seed=a.seed, out=a.out, started=t0)94 for m, s in summary.items():95 if m != "glv_subscalar_bits":96 print(f"{m:18s} add {s['add_mean']:7.1f} dbl {s['dbl_mean']:7.1f} total {s['total_mean']:7.1f} ± {s['total_sd']:.1f} speedup(ops) {s['speedup_vs_double_and_add_ops']:.3f} {s['time_mean_ms']:.1f} ms")97 print("GLV sub-scalars:", summary["glv_subscalar_bits"])9899100if __name__ == "__main__":101 main()102