1"""Stage 2–3 automation: exhaustive search for exact integer / modular identities among the secp256k1 constants.23The generator enumerates candidate relations of bounded complexity and the checker evaluates each one with exact4arithmetic. Every surviving identity is then classified against the literature (CM theory of j = 0 curves,5GLV lattice structure). This is a deliberately simple "discovery engine": its purpose is to measure how many of the6known structural identities an automated search rediscovers, and whether it finds any that are NOT explained by theory.78Search spaces9 Q1 binary quadratic forms: u² + c·u·v + d·v² = target for (u, v) among constant pairs, |c|,|d| ≤ 6, target ∈ {p, n, 4p, 4n, …}10 Q2 modular polynomial relations: x² + c·x + d ≡ 0 (mod m) for x ∈ {β, λ, …}, m ∈ {p, n}, |c|,|d| ≤ 611 Q3 linear relations among the GLV basis entries: a2 = e1·a1 + e2·b1, b2 = e3·a1 + e4·b1, |e_i| ≤ 312 Q4 "λ ≡ polynomial(β)" style cross-modulus relations (expected to fail: different moduli) — negative control13 Q5 small-coefficient relations between Gx, Gy, β, p (expected to fail — the generator is not special) — negative control14Writes results/automated_discovery/identity_search.json.15"""16import itertools, json, math, sys, time, pathlib17ROOT = pathlib.Path(__file__).resolve().parents[2]18sys.path.insert(0, str(ROOT / "src"))19from wp34 import secp256k1 as k120from wp34.provenance import record2122p, n, beta, lam = k1.p, k1.n, k1.beta, k1.lam23t = p + 1 - n24f = math.isqrt((4 * p - t * t) // 3)25consts = {"p": p, "n": n, "t": t, "f": f, "a1": k1.a1, "b1": k1.b1, "a2": k1.a2, "b2": k1.b2,26 "beta": beta, "lambda": lam, "Gx": k1.Gx, "Gy": k1.Gy}27KNOWN = {28 "Q1:t^2+0*t*f+3*f^2=4p": "CM theory: 4p = t² + 3f² for j = 0 (Frobenius π = (t + f√−3)/2 ∈ Z[ω])",29 "Q1:a1^2-1*a1*b1+1*b1^2=n": "n = N(a1 + b1·ω): the GLV basis vector has Eisenstein norm n (GLV 2001 / Z[ω] structure)",30 "Q1:a2^2-1*a2*b2+1*b2^2=n": "same for the second basis vector",31 "Q3:a2=1*a1-1*b1": "second GLV vector = ω·(first) up to sign: (a1,b1)·ω rotates the lattice (Eisenstein units)",32 "Q3:b2=1*a1+0*b1": "same",33 "Q2:beta^2+1*beta+1=0 mod p": "β is a primitive cube root of unity (β² + β + 1 = 0)",34 "Q2:lambda^2+1*lambda+1=0 mod n": "λ is a primitive cube root of unity in Z/nZ",35 "Q1:t^2+0*t*b1+3*b1^2=4p": "b1 = −f: the GLV vector's second coordinate is the CM conductor (4p = t² + 3f²)",36}37# Closed form found by the search and then explained (CM theory): the GLV lattice {(k1,k2): k1 + k2·λ ≡ 0 (mod n)} is the38# principal ideal (π̄ − 1)·Z[ω] of Z[ω] where π̄ = (t − f√−3)/2 is the Frobenius conjugate mapping ω ↦ λ, hence39# a1 = (t − f)/2 − 1, b1 = −f, a2 = (t + f)/2 − 1 = a1 − b1, b2 = a1, and a1² − a1·b1 + b1² = N(π̄ − 1) = n.40CLOSED_FORM = {"a1": (t - f) // 2 - 1, "b1": -f, "a2": (t + f) // 2 - 1, "b2": (t - f) // 2 - 1}41EISENSTEIN_NORM_FAMILY = "quadratic form u² ± uv + v² = n among {a1, b1, a2, b2, f}: all are Eisenstein norms of unit multiples / conjugates of π̄ − 1 (CM theory, GLV lattice = ideal (π̄ − 1))"424344def search():45 found, tested = [], 046 names = list(consts)47 targets = {"p": p, "n": n, "4p": 4 * p, "4n": 4 * n, "2p": 2 * p, "3p": 3 * p, "3n": 3 * n, "p-1": p - 1, "n-1": n - 1}48 # Q1 binary quadratic forms (ordered pairs; forms u² + c uv + d v²)49 for u, v in itertools.permutations(names, 2):50 U, V = consts[u], consts[v]51 for c in range(-6, 7):52 for d in range(-6, 7):53 val = U * U + c * U * V + d * V * V54 tested += 155 for tn, tv in targets.items():56 if val == tv:57 cs = f"{c:+d}" if c else ""58 found.append({"space": "Q1", "id": f"Q1:{u}^2{c:+d}*{u}*{v}{d:+d}*{v}^2={tn}".replace("+", "+").replace("^2+0*", "^2+0*"),59 "relation": f"{u}^2 {c:+d}·{u}·{v} {d:+d}·{v}^2 = {tn}"})60 # Q2 modular quadratics61 for xname in ("beta", "lambda", "Gx", "Gy", "t", "f", "a1", "b1"):62 X = consts[xname]63 for mname, m in (("p", p), ("n", n)):64 for c in range(-6, 7):65 for d in range(-6, 7):66 tested += 167 if (X * X + c * X + d) % m == 0:68 found.append({"space": "Q2", "id": f"Q2:{xname}^2{c:+d}*{xname}{d:+d}=0 mod {mname}",69 "relation": f"{xname}^2 {c:+d}·{xname} {d:+d} ≡ 0 (mod {mname})"})70 # Q3 linear relations in the GLV basis71 for e1, e2 in itertools.product(range(-3, 4), repeat=2):72 tested += 273 if k1.a2 == e1 * k1.a1 + e2 * k1.b1:74 found.append({"space": "Q3", "id": f"Q3:a2={e1:+d}*a1{e2:+d}*b1", "relation": f"a2 = {e1}·a1 {e2:+d}·b1"})75 if k1.b2 == e1 * k1.a1 + e2 * k1.b1:76 found.append({"space": "Q3", "id": f"Q3:b2={e1:+d}*a1{e2:+d}*b1", "relation": f"b2 = {e1}·a1 {e2:+d}·b1"})77 # Q4 negative control: λ ≡ c0 + c1 β + c2 β² (mod n) for small c_i and also mod p — must not hold (except trivialities)78 q4 = 079 for c0, c1, c2 in itertools.product(range(-6, 7), repeat=3):80 tested += 281 if (c0 + c1 * beta + c2 * beta * beta - lam) % n == 0 or (c0 + c1 * beta + c2 * beta * beta - lam) % p == 0:82 q4 += 183 found.append({"space": "Q4", "id": f"Q4:lambda={c0}+{c1}beta+{c2}beta^2", "relation": "cross-modulus relation (unexpected)"})84 # Q5 negative control: Gy² ≡ Gx³ + 7 is the curve equation (expected, trivial) — exclude it; look for85 # small-coefficient linear relations c1·Gx + c2·Gy + c3·beta + c4 ≡ 0 (mod p), |c_i| ≤ 6, not all zero86 q5 = 087 for c in itertools.product(range(-6, 7), repeat=4):88 if not any(c):89 continue90 tested += 191 if (c[0] * k1.Gx + c[1] * k1.Gy + c[2] * beta + c[3]) % p == 0:92 q5 += 193 found.append({"space": "Q5", "id": f"Q5:{c}", "relation": "small linear relation among Gx, Gy, beta (unexpected)"})94 return found, tested, q4, q5959697def main():98 t0 = time.time()99 found, tested, q4, q5 = search()100 # normalise ids and classify101 out = []102 for h in found:103 hid = h["id"].replace("+0*", "+0*")104 known = None105 for k, v in KNOWN.items():106 # tolerant matching on structure107 kk = k.replace("+", "").replace("-", "").replace("*", "")108 hh = hid.replace("+", "").replace("-", "").replace("*", "")109 if kk == hh:110 known = v111 if known is None and h["space"] == "Q1" and h["relation"].endswith("= n") and all(v in h["relation"] for v in ["^2"]):112 known = EISENSTEIN_NORM_FAMILY113 h["classification"] = "known_reproduced" if known else ("unexpected_investigate" if h["space"] in ("Q4", "Q5") else "found_unclassified")114 h["explanation"] = known115 out.append(h)116 # The expected count of chance hits for Q5: 13^4 trials, each true with prob 1/p ≈ 2^-256 → 0.117 closed_ok = all(getattr(k1, k) == v for k, v in CLOSED_FORM.items())118 meas = {"candidates_tested": tested, "identities_found": len(out), "found": out,119 "closed_form_glv_basis": {k: str(v) for k, v in CLOSED_FORM.items()}, "closed_form_matches_libsecp256k1": closed_ok,120 "closed_form_statement": "a1 = (t−f)/2 − 1, b1 = −f, a2 = (t+f)/2 − 1, b2 = a1 with 4p = t² + 3f²; lattice = ideal (π̄−1)Z[ω]",121 "negative_controls": {"Q4_cross_modulus_hits": q4, "Q5_small_linear_hits": q5,122 "expected_chance_hits": tested / p},123 "unexplained": [h for h in out if h["classification"] != "known_reproduced"]}124 record("identity_search_secp256k1_constants", {"spaces": ["Q1", "Q2", "Q3", "Q4", "Q5"], "coeff_bound": 6}, meas,125 out=str(ROOT / "results/automated_discovery/identity_search.json"), started=t0)126 print(f"tested {tested} candidates, found {len(out)} identities; negative controls Q4={q4} Q5={q5}; closed-form GLV basis matches: {closed_ok}")127 for h in out:128 print(f" [{h['classification']}] {h['relation']} — {h['explanation'] or ''}")129130131if __name__ == "__main__":132 main()133