What the agents learned.

Evaluated negation-map BSGS with stride M = 2m+1 on 36-bit curve (p=44382896699, n=4438300897). With m = isqrt(n)//2 + 1 = 33311 baby steps, the table size is ~33k entries using packed integer keys (j<<1)|(y&1) mapping x-coordinates. Practice instance solved k=1664885196 in 0.12s total execution time. Verification of k*G == P succeeded.

Performance analysis:

• Baby-step generation took ~33,311 affine additions with egcd pow(x, -1, p).
• Target search required 25,004 giant steps (total time ~0.12s).
• Comparison with standard Pollard rho: Pollard rho requires ~sqrt(pi*n/2) ~ 83,500 operations, while negation BSGS with m = isqrt(n)//2 + 1 averages ~0.75*sqrt(n) ~ 49,967 curve ops, achieving >6x wall-clock speedup due to low per-step Python overhead.
• Memory usage is negligible (<5MB) at 36 bits. BSGS remains the optimal choice for heights <= 40 bits before table RAM pressure at 44+ bits forces transition to distinguished points rho/kangaroo.

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

Pure-Python BSGS is the right tool at 32 bits (n≈3.23e9, m≈56845). Practice instance solved in 0.10 s (k=105540012), verified k*G==P. Random k times 0.06–0.12 s.

Speed: pow(x, -1, p) (extended gcd) is ~6× faster than Fermat pow(x, p-2, p) at 32-bit: 20k inverses 10 ms vs 64 ms. Baby-step walk of 57k adds is ~76 ms, of which ~49 ms is inverses and ~4 ms is the dict. Montgomery batch inversion did not beat per-step egcd (batch-64 was slightly slower) because CPython loop overhead dominates the saved inverses.

Jacobian mixed-add baby steps were slower (81 ms walk + 51 ms to batch-normalize and insert), so stay in affine.

multiprocessing is blocked by the sandbox. Negation map / rho not worth it yet: BSGS early-exits on giant steps and is already well under a Python rho.

Next heights: keep this BSGS through ~36–40 bits. Around 40 bits switch to Pollard rho + distinguished points + negation + batch inversion. n is prime (no PH); curves are random (no MOV/Smart).