dlog_asymmetry.py — src/26-pnp

1#!/usr/bin/env python32# -*- coding: utf-8 -*-3"""4dlog_asymmetry.py  (26-pnp formalization anchor)5The hyperoperation ASCENT vs DESCENT timing asymmetry on the carrier:6  ascent  f(j) = g^j mod P     -- fast exponentiation, O(log j) multiplications7  descent f^{-1}(h) = dlog(h)   -- baby-step-giant-step, O(sqrt(P)) operations8Confirms the one-way structure: ascent flat in log P, descent ~ sqrt(P).9"""10import time, math, random11from sympy import nextprime, primitive_root1213def bsgs(g, h, P, n):           # solve g^x = h mod P, x in [0,n)14    m = int(math.isqrt(n)) + 115    table = {}16    e = 117    for i in range(m):          # baby steps18        table.setdefault(e, i); e = (e*g) % P19    factor = pow(g, (P-2)*m, P) # g^{-m} mod P  (Fermat inverse)20    gamma = h21    for q in range(m):          # giant steps22        if gamma in table:23            return q*m + table[gamma]24        gamma = (gamma*factor) % P25    return None2627print(f"{'P (~)':>12} {'bits':>5} {'ascent (us)':>12} {'descent (s)':>12} {'descent/ascent':>15} {'sqrt(P)':>10}")28rows=[]29for target in (10**5, 10**6, 10**7, 10**8, 10**9):30    P = nextprime(target)31    g = primitive_root(P)32    j = random.randrange(2, P-1)33    # ascent: time many reps34    t0=time.perf_counter()35    for _ in range(2000): h = pow(g, j, P)36    asc = (time.perf_counter()-t0)/2000*1e6        # microseconds per exponentiation37    # descent38    t0=time.perf_counter()39    x = bsgs(g, h, P, P-1)40    desc = time.perf_counter()-t0                  # seconds41    assert pow(g, x, P) == h, "dlog failed"42    rows.append((P, asc, desc))43    print(f"{P:>12} {P.bit_length():>5} {asc:>12.2f} {desc:>12.4f} {desc*1e6/asc:>15.1f} {math.isqrt(P):>10}")4445import numpy as np46lP=np.log([r[0] for r in rows])47b_asc=np.polyfit(lP, np.log([r[1] for r in rows]),1)[0]   # ascent ~ P^?  (expect ~0, i.e. ~log)48b_desc=np.polyfit(np.log([r[0] for r in rows]), np.log([r[2] for r in rows]),1)[0]  # descent ~ P^?49print(f"\nscaling: ascent ~ P^({b_asc:+.3f}) (flat: cost ~ log P, polynomial in bits)")50print(f"         descent ~ P^({b_desc:+.3f}) (~0.5: cost ~ sqrt(P), exponential in bits)")51print("=> the ascent is feasible (horizon-bounded), the descent is not: the one-way structure")52print("   of the hyperoperation ladder is the candidate source of P != NP, FRC's scale/dlog map.")53