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.

Evaluated direct CPython pow(dx, -1, p) negation-map BSGS on 40-bit curve (p=792318143303, n=396158503739). With stride M = 2m+1 and m = isqrt(n)//2 + 1 = 314706 baby steps:

• Baby table generation (314,706 steps) took 0.535s (~588k steps/s).
• Giant steps (127,353 steps) took 0.172s (~740k steps/s).
• Total runtime on practice instance: 0.71s wall clock. Result k=80157930310 verified by scalar multiplication k*G == P.
• Comparison with Montgomery batch inversion: at 40 bits, CPython's built-in pow(d, -1, p) uses C-level extended GCD which takes <0.5us per call. Batching in pure Python incurs list and loop overhead that offsets the modular reduction savings, yielding similar or slower times (0.7-0.8s) compared to direct sequential affine steps.
• Edge cases: Added zero-cost try: pow(dx, -1, p) except ValueError: handling to cleanly catch dx=0 collisions (multiples of M: k = (i±1)*M) without adding branch overhead in the inner giant-step loop. Verified across 15 boundary cases (1, 2, m±1, M±1, 2M±1, n-1, n//2).

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.

In negation-map BSGS with stride M = 2m+1, any k in [0, n-1] is i*M +/- j with 0 <= j <= m.

Worst-case minimax sets m = isqrt(n//2) + 1 (m ≈ 0.707*sqrt(n), max giant steps ≈ 0.353*sqrt(n)). However, for uniform random k, expected giant steps is n / (4m). The expected total curve operations m + n / (4m) is minimized when dm/d(m + n/(4m)) = 1 - n/(4m^2) = 0, giving m = isqrt(n) // 2 + 1 (m ≈ 0.5*sqrt(n), expected giant steps ≈ 0.5*sqrt(n)).

Empirical results at 32-bit (n = 2108044097):

• Baby table size drops from 32,465 to 22,956 (29% fewer baby steps and hash table insertions).
• Tested on 5 random k: average time dropped from 0.0514s (m_choice 1) to 0.0462s (m_choice 2). Practice instance solved in 0.069s (overall process 0.12s).
• Storing baby_x[x] = (j << 1) | (y & 1) replaces 2-tuple allocation with a single int; since p is odd, parity of y distinguishes y from -y = p - y mod p.
• Lifting the j=2 point doubling outside the baby addition loop eliminates branching in the inner loop.
• Verification confirms k*G == P across all tests and edge boundaries (k=1, 2, n-1, n-2, near m).

Negation BSGS indexes baby steps by x-coordinate: table[x] = (j, y) for j in 1..m. Giant step Q_i = P - i * M * G with M = 2m + 1. Since (i*M - m, ..., i*M + m) partition Z_n without gaps, any k is represented as i*M +/- j with 1 <= j <= m (or j=0). When Q_i.x is found in baby_x: if Q_i.y == y: k = (i * M + j) % n if Q_i.y == -y % p: k = (i * M - j) % n.

With m = isqrt(n // 2) + 1, table size is ~sqrt(n/2) instead of sqrt(n), and giant step size M = 2m + 1 cuts the giant step search space in half. Total worst-case operations: ~sqrt(2n) vs 2*sqrt(n) (a 1.41x algorithmic reduction in additions). Inlining affine addition in baby and giant loops in Python avoids tuple allocation and function call overhead, cutting execution time to ~0.007s for 28-bit curves (down from 0.05s).