#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
closure_pnp.py  (26-pnp/validation)  -- FINITE, no continuum, NO RANDOM NUMBER GENERATOR.
=========================================================================================
The arithmetic-hierarchy closure as the algebraic foundation of the one-way structure (sec:owf).
The ladder counting -> addition -> multiplication -> exponentiation closes: the fifth operation is
iteration of the power map P_k(x)=x^k, which on a finite carrier is orbit-counting (finite-orbit
closure), so it returns to the first role.  Consequences for P vs NP:

  T1  ASCENT DYNAMICS / closure phase formula.  In the scale chart x=g^m (g primitive, m in Z_{P-1}),
      the fourth role acts by m->k m and its iteration by  P_k^r(g^m)=g^{k^r m mod (P-1)}.  The ascent
      a_P(j)=g^j is orbit traversal j->j+1 => g^{j+1}=g*g^j: one multiplication per COUNTED step.
  T2  THE FOUR FORWARD ROLES ARE EACH poly(ell).  counting (+1), addition (+a), multiplication (m*),
      exponentiation/ascent (g^j by square-and-multiply) all cost <= O(ell) modular operations.
  T3  ONLY THE INVERSE OF THE FOURTH ROLE BREAKS.  the descent d_P=dlog_g (recover the COUNT m from
      g^m) scales as sqrt(P) (baby-step-giant-step); ascent/descent op-ratio grows ~ sqrt(P)/ell.
      So all irreversibility is localised to inverting the last primitive role -- not a forbidden op
      but the orbit-POSITION problem the forward 'return to counting' does not supply.
  T4  BIJECTIVE vs COMPRESSIVE.  P_k is a bijection of F_P^x iff gcd(k,P-1)=1, else its image has size
      (P-1)/gcd(k,P-1); the iteration orbit r->k^r m is finite and eventually periodic (closure).

PINNED before the numbers.  No np.random anywhere.  Dependencies: sympy.
"""
import math
from sympy import isprime, primitive_root, primerange

PASS=0
def ok(t,c,m):
    global PASS
    assert c, f"FAIL {t}: {m}"
    print(f"PASS {t}: {m}"); PASS+=1

# ---------- T1: closure / ascent phase formula ----------
print("T1  closure phase formula  P_k^r(g^m) = g^{k^r m mod (P-1)}  (iterating the 4th role = phase index x k^r)")
viol=0; nch=0
for P in (13,101,1009,10009):
    g=int(primitive_root(P)); n=P-1
    for k in (2,3,5,7,10):
        for m in (1,2,7):
            for r in (0,1,2,3,5):
                x=pow(g,m,P)
                for _ in range(r): x=pow(x,k,P)        # iterate the power map r times
                rhs=pow(g,(pow(k,r,n)*m)%n,P)          # closed form
                nch+=1
                if x!=rhs: viol+=1
print(f"     checked {nch} (P,k,m,r) cases across 4 carriers")
ok("T1", viol==0, f"the fourth role iterates as m->k^r m in the phase-index ring Z_(P-1) ({viol} violations) -- "
   "the ascent g^j is counting along the power-map orbit (g^{j+1}=g*g^j)")

# ---------- T2: the four forward roles are each poly(ell) ----------
print("\nT2  the four forward roles are each poly(ell):  modular-op count per application")
print(f"  {'P':>10} {'ell':>4} {'count(+1)':>9} {'add(+a)':>8} {'mult(m*)':>9} {'ascent g^j (sq&mul)':>20}")
def ascent_ops(g,j,P):                                   # modmuls in square-and-multiply
    ops=0; r=1; b=g; e=j
    while e>0:
        if e&1: r=(r*b)%P; ops+=1
        e>>=1
        if e>0: b=(b*b)%P; ops+=1
    return ops
roles_poly=True
for P in (10007,1000003,100000007):
    ell=P.bit_length(); g=int(primitive_root(P))
    asc=ascent_ops(g,P-2,P)                               # worst-ish exponent
    # counting=1 op, addition=O(ell) bit (1 modular add), multiplication=1 modular mult
    if not (asc<=2*ell+2): roles_poly=False
    print(f"  {P:>10} {ell:>4} {1:>9} {1:>8} {1:>9} {asc:>20} (<= 2 ell = {2*ell})")
ok("T2", roles_poly, "every forward role -- counting, addition, multiplication, exponentiation -- costs O(ell) "
   "modular operations; the closed ladder is poly(ell) in the forward direction")

# ---------- T3: only the inverse of the fourth role breaks ----------
print("\nT3  only the INVERSE of the fourth role is hard:  ascent (sq&mul) vs descent dlog (BSGS)")
def dlog_bsgs(g,h,P):                                     # returns (x, group-op count)
    n=P-1; m=math.isqrt(n)+1; tbl={}; e=1; ops=0
    for j in range(m): tbl.setdefault(e,j); e=(e*g)%P; ops+=1
    fac=pow(g,(n-1)*m % n,P); gamma=h%P
    for i in range(m):
        if gamma in tbl: return i*m+tbl[gamma], ops+i
        gamma=(gamma*fac)%P
    return None, ops+m
print(f"  {'P':>10} {'ell':>4} {'ascent ops':>10} {'descent ops':>12} {'ratio':>10}")
ratios=[]
for P in (10007,1000003,100000007):
    ell=P.bit_length(); g=int(primitive_root(P))
    m_true=P//3; h=pow(g,m_true,P)
    asc=ascent_ops(g,m_true,P)
    x,desc=dlog_bsgs(g,h,P); assert pow(g,x,P)==h
    ratios.append(desc/asc)
    print(f"  {P:>10} {ell:>4} {asc:>10} {desc:>12} {desc/asc:>10.1f}")
ok("T3", ratios[-1]>ratios[0]*5, f"descent/ascent op-ratio grows {ratios[0]:.0f}->{ratios[-1]:.0f} (~sqrt(P)/ell): "
   "all irreversibility sits in inverting the last role -- recovering the count from its orbit position (dlog)")

# ---------- T4: bijective vs compressive; orbit closure ----------
print("\nT4  P_k bijective iff gcd(k,P-1)=1; image size (P-1)/gcd; iteration orbit eventually periodic")
print(f"  {'P':>6} {'k':>3} {'gcd(k,P-1)':>10} {'image size':>11} {'(P-1)/gcd':>10} {'orbit period':>13}")
dich_ok=True
for P in (1009,10009):
    n=P-1; g=int(primitive_root(P))
    for k in (2,3,4,6,7):
        img=len(set(pow(x,k,P) for x in range(1,P)))
        pred=n//math.gcd(k,n)
        # iteration orbit r->k^r m mod n (m=1): period
        seen={}; m=1%n; r=0
        while m not in seen:
            seen[m]=r; m=(k*m)%n; r+=1
        period=r-seen[m]
        if img!=pred: dich_ok=False
        print(f"  {P:>6} {k:>3} {math.gcd(k,n):>10} {img:>11} {pred:>10} {period:>13}")
ok("T4", dich_ok, "image size = (P-1)/gcd(k,P-1) exactly (bijection iff gcd=1), and the iteration orbit closes "
   "(eventually periodic) -- the fifth step is a finite counted orbit, not a new primitive role")

print(f"\nclosure_pnp: all checks passed ({PASS} checks). FINITE throughout, NO random number generator.")
print("RESULT: the arithmetic ladder closes at four roles; the ascent is counting along the orbit of the fourth")
print("(power) role; the one-way function of record (Assumption: scale-descent hardness) is exactly the INVERSE")
print("of that last role -- recovering the count from its orbit position (dlog) -- so the irreversibility is")
print("localised to one step and is not a forbidden primitive but the orbit-position problem.")