chart_localization.py — src/26-pnp

1"""2chart_localization.py  --  the description-length vs counting-distance gap.34Supports Definition (localizing chart), Proposition (existence is free; the5selector is the content) and the lucky-chart Remark of Section 5 of the6P-vs-NP paper.  Exact, deterministic, no randomness.78Claim exhibited.  In the scale chart x = g^m of F_P the discrete logarithm m9is the *counting distance* from the identity to x along the orbit (one step =10x -> g*x).  The map x |-> m is a bijection of F_P^x onto {1,...,P-1}; hence the11counting distance is spread uniformly up to P-1 = 2^ell - O(1), while the12witness m is *named* in ell = ceil(log2 P) bits.  Short to name (ell bits) is13not short to find (up to 2^ell counting steps).  The ascent g^m is O(ell) by14square-and-multiply.  This is exactly the gap that makes a localizing chart15exist for free (it is named by m) yet not be forward-selectable.16"""17import math181920def generator(P):21    """Least primitive root mod P (P prime), by a direct orbit check."""22    for g in range(2, P):23        x, seen = 1, set()24        for _ in range(P - 1):25            x = (x * g) % P26            seen.add(x)27        if len(seen) == P - 1:28            return g29    raise RuntimeError("no generator found")303132def report(P):33    g = generator(P)34    # counting distance to each element = its discrete log (orbit ordinal)35    x, dlog = 1, {}36    for k in range(1, P):37        x = (x * g) % P38        dlog.setdefault(x, k)39    # the counting distances are exactly a permutation of 1..P-1 (a bijection)40    assert sorted(dlog.values()) == list(range(1, P)), "dlog not a bijection"41    ell = math.ceil(math.log2(P))                  # bits to NAME a witness42    mean_count = sum(dlog.values()) / (P - 1)       # mean steps to FIND it43    max_count = max(dlog.values())                  # = P-1 = 2^ell - O(1)44    ascent_bits = sum(k.bit_length() for k in range(1, P)) / (P - 1)45    return g, ell, mean_count, max_count, ascent_bits464748if __name__ == "__main__":49    print(f"{'P':>8} {'g':>4} {'ell=name bits':>14} {'mean find-steps':>16} "50          f"{'max find-steps':>15} {'ascent bits':>12}")51    for P in [101, 1009, 10007, 100003]:52        g, ell, mc, xc, ab = report(P)53        print(f"{P:>8} {g:>4} {ell:>14} {mc:>16.1f} {xc:>15} {ab:>12.1f}")54    print()55    print("find-steps ~ 2^ell  (exponential in input size ell);")56    print("name-bits and ascent ~ ell  (polynomial in input size).")57    print("dlog is a bijection onto the orbit ordinals 1..P-1: a witness's")58    print("coordinate is O(ell) bits, its counting distance is up to 2^ell.")59    print("Hence the localizing chart exists (named by the answer) but is not")60    print("forward-selectable -- short to name is not short to find.")61