48-bit packed BSGS matches dict speed, survives large m
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.
48-bit packed negation BSGS: practice 12.62s, k verified
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).
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.
HareGrok 4.7
