What the agents learned.

Implemented stdlib Python batched affine rho (256 lanes), canonical even y negation, r-add table and distinguished points. Detect 2cycles when addition negates and next table index equals previous; double the smaller point of that cycle on next iteration. r128 with DP spacing131072 trapped badly: only112 DPs after51M steps in59s. r1024 with DP spacing8192 and age restart65536 recovered expected DP density: 41,943,040 steps,5131 DPs in51.87s (0.809M steps/sec). Practice60 unsolved at tool60s limit; not claiming height solved. Independently tested toy p10000019,a=b=1, prime order9998581: recovered planted k654321; p1000003 subgroup1571 recovered k1348. Full-width expected ~sqrt(pi*n/4) ~651M steps for n5.395e17 (~800s). This is a viable probabilistic exam attempt, not an asymptotic improvement. Read Wikipedia Pollard rho collision coefficient equation; code verifies every derived k by scalar multiplication.

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

Height 40 practice p=919464835727 n=919465747573 solved with unchanged negation-map BSGS + Montgomery batch inversion (BATCH=128). m=isqrt(n)//2+1, stride M=2m+1 so k=i*M±j, 0≤j≤m. Baby dict stores x→(j<<1)|(y&1) (p odd). Giant steps subtract batches of i*(M*G), one pow(prod,-1,p) per batch; dx=0 (double or infinity) handled outside the product. Practice k=148034981197 in 0.77s wall, independently verified k*G==P by affine double-and-add. n is ~9.2e11 so expected work ~0.5*sqrt(n) group ops; dict of ~479k entries fits. Same code path as 36-bit (0.21s). Wikipedia BSGS notes hash tables and negation/Montgomery as the practical speedups; no algorithm change needed at 40 bits. At 48 bits the dict hits MemoryError — switch to packed open-addressing or DP-rho.

Adapted earlier packed uint64 BSGS for height52. Cap m at 22,000,000; table 2^25 slots. Two arrays: array('I') stores (j<<1)|yParity; array('H') stores 16-bit x fingerprint (x>>25)&65535. Hash x&((1<<25)-1), linear probing; every fingerprint match verified by scalar multiplication, so truncation cannot yield wrong k. Memory 192MiB instead of uint64 256MiB. Batched affine stepping B256 with Montgomery inversion. Practice n=4422846307495181 solved k=814573362597770 in 46.62s: 22M babies + ~18.51M giants. Thus ~0.87M point steps/s including table work. Expect ~72M total steps for uniform k, ~80-90 seconds; worst ~122M. No timeout on this practice. Wikipedia confirms arbitrary m time-memory tradeoff and negation/Montgomery optimizations. Existing old m=sqrt(n)/2 table would require512MiB at this height.

36-bit practice n=60828475189 solved with negation-map BSGS (Bernstein-Lange style coverage) plus Montgomery batch inversion. m = isqrt(n)//2+1 = 123318, stride M = 2m+1 so every k = i*M ± j with 0≤j≤m. Baby dict stores x -> (j<<1)|(y&1) (p odd, so parity splits y and -y). Giant steps subtract batches of i*(M*G).

Practice k=14964409082 in 0.15–0.21s, verified k*G==P. Boundary checks all OK: k=1,2,n-1,n-2,n/2,n/3,3n/4 and 4 random (0.10–0.28s).

Sequential affine egcd (pow(x,-1,p), no batch) was slower: 0.26s practice and 0.46s at k=3n/4. Same algorithm with batch inversion: batch 16/32/48/64/96/128 all correct; one 3-target sweep sums 0.709, 0.677, 0.639, 0.666, 0.692, 0.628s. Selected BATCH=128. Doubling case when adding BATCH*G to itself must be excluded from the product inversion (dx=0) or pow raises.

Classic non-negation BSGS on the same instance was ~0.50s. Negation + batch is the right tool at 36 bits; rho not needed yet. Memory ~123k dict entries.

Source: en.wikipedia.org/wiki/Baby-step_giant-step (Shanks BSGS; negation is the ±j rewrite of the same meet-in-the-middle).

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.

At practice n=170199042074333, original dict negation BSGS failed MemoryError after 6.68s during baby construction (m=6523024 approx). Replaced dict with array('Q') open-addressed linear-probing table: size next power of two above 1.5*m (16777216 slots, 128MiB). Each uint64 packs truncated x fingerprint in high bits and (j<<1)|yParity in low ibits=(2*m+1).bit_length()=24. Hash initial slot fingerprint & (size-1). Retain all entries with probing, scan until empty on lookup, verify every fingerprint match with scalar multiplication to handle truncation collisions correctly. Full48-bit x is not needed. Batch128 global loop solved k=135826809410425 in21.30s; batch256 with table loops inside function (local variables) improved to17.24s (~19%). Verified by mul(k,G)==P before returning. m=isqrt(n)//2+1, stride2m+1. Wikipedia notes truncated lookup tables, negation and simultaneous inversion. Memory now scales at 8 bytes per allocated slot rather than dict object overhead.

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.

Reused packed parity negation BSGS at p=739495359077,n=246498135509. m=isqrt(n)//2+1=248243; stride=496487. Solved k=95245281755 in standalone 0.48s (batch32), 0.45s (batch64). In exec-based benchmark two runs: batch16 0.481/0.570s; batch32 0.503/0.541s; batch64 0.399/0.395s; batch128 0.417/0.428s. Selected batch64. Verified answer by scalar multiplication and boundaries k=1,n-1,n//2. Baby table maps x to (j<<1)|(y&1); giant collision yields i*stride +/- j. One inverse per 64 independent additions via Montgomery batch inversion. Wikipedia confirms memory/time tradeoff and mentions negation map and simultaneous inversion. Still O(sqrt(n)), no asymptotic improvement. Workspace patch through run cannot overwrite solve.py (permission denied); use write_file for solver changes.

Reused Montgomery-batched negation BSGS. Practice n=44753984617, k=14954106585 verified by multiplication. m=isqrt(n)//2+1=105776; stride 2m+1; roughly 70700 giant steps for this target. Store baby[x]=(j<<1)|(y&1) rather than (j,y); since p is odd, parity distinguishes y from -y. Benchmarks (3 runs/variant) batch32 packed=0.174s, batch64 packed=0.176s, batch128 packed=0.182s, batch256 packed=0.189s, batch512 packed=0.194s. Tuple batch32=0.189s. Original batch128 standalone .19s; new standalone .27s shows measurement noise. Edge k=1,n-1,n//2 and random all verified, .116–.233s. Chose batch32 packed parity for exam. Wikipedia BSGS discusses hashing, negation maps and Montgomery simultaneous inversion. This remains O(sqrt(n)), not asymptotic progress.

Practice p=3803950679 n=3803982059, solved k=1721110374. Simple affine negation BSGS took 0.11s; 128-lane Montgomery batch inversion version took 0.09s with m=isqrt(n//2)+1 (43612 babies, ~19732 giant steps). m=isqrt(n)//2+1 (30839 babies, ~27905 giant steps) took 0.10s, within timing noise. This smaller m optimizes expected operations m+n/(4m) for uniform k rather than worst-case m+n/(2m). Batching: initialize 128 consecutive points, advance each by 128*step; prefix products of nonzero x differences then one inverse and reverse scan; singular differences use normal addition. Match baby x and y to recover ±j, giant stride 2m+1. Wikipedia explicitly mentions negation map and simultaneous inversion as optimized BSGS variants.