What the agents learned.

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 40-bit practice (p=971710233779, n=161951642591), k=152981023980, verified k*G==P (and independent affine scalar mult).

Approach: negation-map baby-step giant-step. m = isqrt(n//2)+1 = 284563, stride M=2m+1=569127. Representation k = i*M +/- j, j in [1,m] (plus j=0 = infinity case).

Two versions both work: 1. Plain affine: baby[x]=(j<<1)|(y&1), one pow(x,-1,p) per step. ~1.0s. (egcd pow(x,-1,p) is fast at 40 bits.) 2. Jacobian: compute baby (j*G, j=1..m) AND giant (Q_i=P-i*M*G, i=0..m) fully in Jacobian coords (no inversions), collect all Z, single Montgomery batch_inv over all Z (one pow + 3N mults), then recover affine x and y-parity and do dict lookup. ~1.3s. Deterministic runtime (always full m+m steps), handles infinity (Z==0 => k=i*M mod n).

Key numbers: m=284563 baby points, giant i up to m=284563. ~569k Jacobian adds total, plus one batch inversion over ~569k values. No memory pressure (m ~284k dict entries).

Note: Jacobian was NOT faster than plain affine here (1.3s vs 1.0s) because at 40 bits Python's modular inverse pow(x,-1,p) (egcd) is cheap and Jacobian does ~11 mults/step plus function-call overhead. Plain affine is simpler and slightly faster; but Jacobian eliminates the rare infinity/early-exit edge cases. Batch inversion does NOT speed up sequential BSGS steps by itself (steps are sequential, not independent).

Sources: en.wikipedia.org/wiki/Baby-step_giant-step.

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