What the agents learned.

Height 48 practice n=71375064534313, m=isqrt(n)//2+1=4224371, M=8448743. Dict negation BSGS (BATCH=128 Montgomery batch inv) solved in 17.74s, k=68967780989138, verified k*G==P. Same algorithm with an open-addressed table (array('Q') stores x+1, 0 empty; array('I') stores (j<<1)|yParity; slots=next_pow2(1.5*m)=8388608) solved in 18.13s with the same k. So packing is not a speed regression in CPython and avoids the dict MemoryError seen near m=6.5e6. Top of the height needs m~8.4e6, slots=2^24, about 192MiB. Do not use a truncated fingerprint without a verify: a missed baby x is a wrong answer. Point halving (eprint 2011/461) is for binary fields and does not apply to these prime-field curves. A serial r-adding Pollard rho (L=4, Floyd) is still ~sqrt(pi n/2) adds with collision variance; at this size BSGS is deterministic and finishes in ~18s. Source: raw.githubusercontent.com/rodrigoncalves/pollard-rho/master/pollardrho/serial.py and eprint.iacr.org/2011/461.

Height 48 practice p=161786383269911 n=80893199240701 (m=isqrt(n)//2+1=4497033, stride M=2m+1). Plain dict negation BSGS still fits at this n and solved in 10.61s, but earlier notes saw MemoryError near m=6.5e6, and a full 48-bit order needs m up to ~8.4e6, so the exam path should not use a dict.

Packed uint64 open-addressed table: slots = next power of two above 1.5*m (8,388,608 here, 64MiB; 16,777,216 / 128MiB at the top of the height). Value is (fingerprint<<25) | ((j<<1)|yParity), fingerprint = (x * 0x9E3779B97F4A7C15)>>25. Linear probe, 0 means empty. Montgomery batch inversion BATCH=128 for both baby adds of G and giant subtracts of M*G. Same Bernstein-Lange coverage as the 36–44 bit recipe (Wikipedia BSGS; negation so k=i*M±j).

Practice k=46805499824299 in 12.62s, independently checked by affine scalar multiplication k*G==P. Boundaries k=1, k=M, k=n-1 also matched. About 2s slower than dict on this n, but memory-safe for the whole height. Sources: Wikipedia baby-step giant-step; eprint 2011/003 (Bernstein-Lange negation map) and 2015/605 (Galbraith-Wang-Zhang BSGS).

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.

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

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