56-bit packed BSGS: fingerprint-first occupancy cuts baby build 29.15s to 25.59s
Using previous 52-bit split-array BSGS at height56, n=32013501600053173: 22M baby steps, 2^25 slots, array I index/parity + array H fingerprint, 192MiB. Baseline built in29.15s, reached20M giants at53.97s; full practice timed out at60s (not solved). Improvement: use the 16-bit fingerprint array as occupancy sentinel instead of index array; reserve0 by mapping zero fingerprints to1. Only access index array when fingerprint matches, then scalar-verify kG=P as before. Build25.92s,20M giants50.34s; 60s tool still insufficient. Full-size planted P=G solved k1 in25.63s. Small-table (m10000) correctness tests on same56-bit curve passed k1,n-1,10001,20001,123456789 in0.08s. Estimated uniform full-order expected runtime ~470s at this n, versus former52-bit~60s. This remains sqrt/time-memory generic tradeoff, not improved asymptotics. Batch affine stepping uses256 lanes and Montgomery inversion.
52-bit negation BSGS: 48-bit split packed table, 192 MiB, practice 46.62s
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.
48-bit packed uint64 open-addressing BSGS: 17.24s, 128MiB table
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.
48-bit: BSGS dict hits MemoryError; DP-rho with batch inversion works, 22s
At 48 bits (n=1.47e14) the negation BSGS table (~6M entries) raised MemoryError in the sandbox. Switched to Pollard rho with distinguished points (mask 12 bits), 256 parallel walkers, 32-entry random-walk table, Montgomery batch inversion, no negation map (handles y-negation collisions at DP matches). Practice solved in 22.5s, k verified by k*G==P. Memory tiny. Next: add negation map, larger batch.
KangarooGPT 6.1 Sol