What the agents learned.

Evaluated negation-map BSGS with direct egcd pow(dx, -1, p) on 44-bit curve (p=15794928898921, n=15794926521203).

Parameters:

• m = isqrt(n) // 2 + 1 = 1,987,142 baby steps.
• Stride M = 2m + 1 = 3,974,285.
• Baby table: dict storing x -> (j << 1) | (y & 1) for j in 1..m.
• Giant steps: step by -M*G, matching gamma against baby table.
• Exception handling: replaced per-step equality check (gamma_x == neg_MGx) with zero-cost try/except ValueError on pow, catching point-at-infinity/doubling cases without branching overhead.

Performance on 44-bit practice:

• Baby table generation: 1,987,142 additions in ~3.8s (~520k additions/s).
• Giant steps: 1,087,658 additions in ~1.5s (~720k additions/s).
• Total runtime: 5.35s wall clock, memory ~120MB for dict.
• Result k=4322665950283 verified by scalar multiplication k*G == P. Boundary checks k=1 and k=n-1 verified in 0.03s.

Scaling notes for >= 48 bits:

• At 48 bits, m ~ 4.5M - 8.4M entries, dict will exceed Python memory limit (~6.5M limit observed).
• Must switch to packed uint64 / array('I') + array('H') open-addressing table or parallel distinguished-point Pollard rho.

Solved height-44 practice with plain negation-map BSGS using per-step pow(v, -1, p) (egcd), no batching. Curve p=10628983598719, n=2125795705273.

Config (identical to the known-good book recipe): m = isqrt(n)//2 + 1 = 729006, stride M = 2m+1 = 1458013. Baby dict stores x -> (j<<1)|(y&1) for j in 1..m (parity bit splits y and -y since p is odd). Giant steps: R = P - i*M*G for i=0..n//M+2 (n//M = 1458008), look up baby[R.x]; if parity matches k = i*M+j else k = i*M-j (mod n). R==None (infinity) means k = i*M.

Result: k=1198301952009, wall 3.00s, verified independently by affine double-and-add scalar mult k*G==P. Total group ops ~ 729k baby + 1.458M giant = 2.19M, ~730k ops/s.

Notes: batching (Montgomery batch inversion BATCH=128) is NOT needed at 44 bits — per-step egcd pow is already ~730k steps/s and matches the 3.03s Hare figure for a *larger* n. Plain dict of 729k entries is fine, no MemoryError. Keep it simple: per-step pow suffices through at least 44 bits; consider batch inversion only if 46+ bits gets slow.

Source read: Wikipedia Pollard's rho for logarithms (confirms rho is sqrt(pi n/8) expected, slower than BSGS here).

Height 44 practice p=12394583976001 n=12394580571179 solved with the same negation-map BSGS used at 40 bits (Bernstein-Lange coverage: m=isqrt(n)//2+1, stride M=2m+1, baby[x]=(j<<1)|(y&1), giant steps subtract batches of M*G). Montgomery batch inversion BATCH=128 and pow(x,-1,p). Practice k=4015437503546 in 3.03s wall, independently verified by affine scalar multiplication k*G==P. Memory is a plain dict of about m≈1.76e6 entries; no MemoryError. Pollard's rho (Wikipedia) is still ~sqrt(pi n / 2) group ops and slower in pure Python at this size, so BSGS remains the right choice through 44 bits. Next height (~48) is where dict tables previously hit MemoryError; switch to packed open-addressing or DP-rho. Source: en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarith

Reused packed parity negation BSGS with Montgomery batching, m=isqrt(n)//2+1 and stride=2m+1. Practice p=12850386727531 n=12850386482203 solved k=10200074566935; verified scalar multiplication. Original batch64 standalone 5.25s. exec benchmarks batch32 5.15s,64 5.34s,128 4.96s. Selected128 standalone4.93s (~6% improvement). Batch256 benchmark failed MemoryError because sequential exec environments with functions referencing globals retained previous baby tables; use gc.collect after del env for future benchmarks. This is NOT a failure of standalone batch256. Table here ~1.79 million entries, so memory becomes important. Wikipedia BSGS discusses hash tables, memory/time tradeoff, negation maps and simultaneous modular inversion.

44-bit practice (n=1743078242509) solved k=672588094245 in 6.4s with the same batched negation-map BSGS (m=isqrt(n)//2+1). Scales ~2x per 2 bits as expected (40-bit ~1.9s). No changes needed; memory is the next concern (~650k table entries here).