"""H05 — Can the automorphism orbits of a j = 0 curve be given a group structure that makes the DLP a problem of size n/6?

Claim under test: the quotient map E(F_p) → E(F_p)/Aut(E) (orbits {±P, ±φP, ±φ²P}) is compatible with addition,
so that the DLP could be solved in a group of order ≈ n/6 (and lifted). Verdict: FALSE. The orbit relation is not a
congruence: P ~ φP and Q ~ Q do not imply P + Q ~ φP + Q. We exhibit explicit counterexamples on synthetic j = 0 curves
and count how often compatibility fails for random pairs (it fails for essentially all pairs).
Note: the orbit set nevertheless carries the structure needed by Pollard rho (a well-defined *iteration* on classes),
which is exactly the √6 constant-factor speed-up (Wiener–Zuccherato 1999; Duursma–Gaudry–Morain 1999) and no more.
"""
import json, random, sys, time, pathlib
ROOT = pathlib.Path(__file__).resolve().parents[2]
sys.path.insert(0, str(ROOT / "src"))
from wp34.ec import random_prime_order_curve, cube_roots_of_unity
from wp34.provenance import record


def main():
    rng = random.Random(34); t0 = time.time(); rows = []
    for bits in (16, 20, 24):
        E = random_prime_order_curve(bits, rng, j0=True)
        beta = cube_roots_of_unity(E.p)[0]
        phi = lambda P: (beta * P[0] % E.p, P[1])
        def orbit(P):
            o = set()
            for Pi in (P, phi(P), phi(phi(P))):
                o.add(Pi); o.add(E.neg(Pi))
            return frozenset(o)
        fails, trials, example = 0, 500, None
        for _ in range(trials):
            P, Q = E.random_point(rng), E.random_point(rng)
            S = E.add(P, Q)
            S2 = E.add(phi(P), Q)   # P ~ φP, so compatibility would require S2 ∈ orbit(S)
            if S2 is None or S is None:
                continue
            if S2 not in orbit(S):
                fails += 1
                if example is None:
                    example = {"P": [str(P[0]), str(P[1])], "Q": [str(Q[0]), str(Q[1])],
                               "P+Q": [str(S[0]), str(S[1])], "phiP+Q": [str(S2[0]), str(S2[1])]}
        rows.append({"bits": bits, "p": str(E.p), "n": str(E.n), "beta": str(beta), "trials": trials,
                     "compatibility_failures": fails, "failure_rate": fails / trials, "counterexample": example,
                     "orbit_size_check": len(orbit(E.G)) == 6})
        print(bits, "bits: compatibility fails in", fails, "/", trials, "random pairs; |orbit(G)| = 6:", len(orbit(E.G)) == 6)
    record("orbit_quotient_counterexample", {"sizes": [16, 20, 24]}, {"rows": rows},
           seed=34, out=str(ROOT / "results/theory/orbit_quotient_counterexample.json"), started=t0)


if __name__ == "__main__":
    main()