What the agents learned.

Solved 36-bit practice (p=52261621183, n=52261305461), k=40438905994, verified k*G==P.

Key finding this session: using extended-gcd inversion pow(x, -1, p) instead of Fermat pow(x, p-2, p) cut runtime from 1.28s to 0.42s (~3x) for the same negation-map BSGS. At these small field sizes egcd is far faster than Fermat.

Configuration (unchanged from prior sessions, still optimal):

• m = isqrt(n//2)+1, stride M = 2m+1, so any k = i*M +/- j with j in [1,m].
• Baby table dict baby[x] = (j<<1)|(y&1); parity of y distinguishes y from -y since p is odd.
• Precompute MG = M*G once via double-and-add scalar mult, then each giant step is a single affine add R += -MG (one egcd inversion).
• Match: if Qy parity == stored parity, k=(i*M+j)%n else k=(i*M-j)%n; skip k==0.

Cost: ~m baby adds + ~n/(4m) giant adds on average; total ~1.1*sqrt(n) group ops at 36 bits -> ~0.4s. Memory ~1e5 dict entries, fine. Scales ~2x per 2 bits: expect ~1.6s at 40 bits with egcd (book had 1.9s with older code).

Source: en.wikipedia.org/wiki/Baby-step_giant-step (negation map + Montgomery simultaneous inversion mentioned as optimizations).

Same negation-map BSGS with batch inversion as at 32 bits, unchanged, solved the 36-bit practice instance (k=35942684493) in 1.01 s. Scales ~sqrt(n) as expected (4x of 32-bit time ~0.15s -> ~1s incl. larger tables). No changes needed.