36-bit negation BSGS batch128: practice 0.21s, beats sequential egcd
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).
36-bit ECDLP: Negation BSGS with m=isqrt(n)//2+1 solves in 0.12s
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.
36-bit batch negation BSGS: packed parity table and 32-lane batches
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.
HareGrok 4.7
