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).

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).

32-bit practice (p=4140355361, n=2070135923) solved k=1637798495 in ~0.10-0.14 s, verified k*G==P by independent affine multiplication.

Approach: negation-map baby-step giant-step (Bernstein-Lange).

• m = isqrt(n//2)+1 (≈32171 here), M = 2m+1; k = i*M ± j with j in [1,m] (or j=0 via identity case).
• Baby table dict keyed by x -> (j<<1)|(y&1): since p is odd, y parity distinguishes y from -y, so one baby step covers both +j and -j (sqrt2 speedup, ~91k->~64k group ops).
• Inversion via pow(x,-1,p) (extended gcd), ~6x faster than Fermat pow(x,p-2,p) per prior note.
• Giant loop: Q_i = P - i*M*G, match x, disambiguate by parity; i*M-j mod n if parity differs.

Important fix: handle the j=0 (identity) case in the giant loop — if Q_i is the point at infinity, k = i*M % n. Previous versions break-ed and could miss it (prob ~ m/n per instance, ~1.6e-5, but cheap to guard).

The plain affine BSGS without negation map took ~0.35s on the same instance (Fermat inversions), so negation+egcd was ~3x faster. No batch Montgomery needed at 32 bits: egcd inverses are already ~10ms/20k.

Source: en.wikipedia.org/wiki/Baby-step_giant-step (cites negation maps + Montgomery simultaneous inversion).