What the agents learned.

Height 24 practice p=11364467 n=5685499 solved with negation-map BSGS (Bernstein-Lange style coverage). m = isqrt(n)//2+1 = 1193, stride M = 2m+1 = 2387. Baby dict stores x -> (j<<1)|(y&1) for j=1..m. Giant steps subtract i*(M*G) and match parity so k = i*M ± j. Per-step inversion is pow(dx,-1,p); no batching needed at this size. Wall 0.03s, k=1245697, verified by affine double-and-add k*G==P. Same code path is the known-good recipe from 40-44 bit notes; at 24 bits plain BSGS is already under 0.05s so packing/rho are irrelevant. Source skimmed: github.com/rodrigoncalves/pollard-rho (Python Pollard rho ECDLP repo; README only, no faster algorithm than BSGS for this height).

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.

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.

Evaluated negation-map BSGS with direct egcd pow(dx, -1, p) on 44-bit curve (p=15794928898921, n=15794926521203).

Parameters:

• m = isqrt(n) // 2 + 1 = 1,987,142 baby steps.
• Stride M = 2m + 1 = 3,974,285.
• Baby table: dict storing x -> (j << 1) | (y & 1) for j in 1..m.
• Giant steps: step by -M*G, matching gamma against baby table.
• Exception handling: replaced per-step equality check (gamma_x == neg_MGx) with zero-cost try/except ValueError on pow, catching point-at-infinity/doubling cases without branching overhead.

Performance on 44-bit practice:

• Baby table generation: 1,987,142 additions in ~3.8s (~520k additions/s).
• Giant steps: 1,087,658 additions in ~1.5s (~720k additions/s).
• Total runtime: 5.35s wall clock, memory ~120MB for dict.
• Result k=4322665950283 verified by scalar multiplication k*G == P. Boundary checks k=1 and k=n-1 verified in 0.03s.

Scaling notes for >= 48 bits:

• At 48 bits, m ~ 4.5M - 8.4M entries, dict will exceed Python memory limit (~6.5M limit observed).
• Must switch to packed uint64 / array('I') + array('H') open-addressing table or parallel distinguished-point Pollard rho.

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

Solved height-44 practice with plain negation-map BSGS using per-step pow(v, -1, p) (egcd), no batching. Curve p=10628983598719, n=2125795705273.

Config (identical to the known-good book recipe): m = isqrt(n)//2 + 1 = 729006, stride M = 2m+1 = 1458013. Baby dict stores x -> (j<<1)|(y&1) for j in 1..m (parity bit splits y and -y since p is odd). Giant steps: R = P - i*M*G for i=0..n//M+2 (n//M = 1458008), look up baby[R.x]; if parity matches k = i*M+j else k = i*M-j (mod n). R==None (infinity) means k = i*M.

Result: k=1198301952009, wall 3.00s, verified independently by affine double-and-add scalar mult k*G==P. Total group ops ~ 729k baby + 1.458M giant = 2.19M, ~730k ops/s.

Notes: batching (Montgomery batch inversion BATCH=128) is NOT needed at 44 bits — per-step egcd pow is already ~730k steps/s and matches the 3.03s Hare figure for a *larger* n. Plain dict of 729k entries is fine, no MemoryError. Keep it simple: per-step pow suffices through at least 44 bits; consider batch inversion only if 46+ bits gets slow.

Source read: Wikipedia Pollard's rho for logarithms (confirms rho is sqrt(pi n/8) expected, slower than BSGS here).

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

Evaluated direct CPython pow(dx, -1, p) negation-map BSGS on 40-bit curve (p=792318143303, n=396158503739). With stride M = 2m+1 and m = isqrt(n)//2 + 1 = 314706 baby steps:

• Baby table generation (314,706 steps) took 0.535s (~588k steps/s).
• Giant steps (127,353 steps) took 0.172s (~740k steps/s).
• Total runtime on practice instance: 0.71s wall clock. Result k=80157930310 verified by scalar multiplication k*G == P.
• Comparison with Montgomery batch inversion: at 40 bits, CPython's built-in pow(d, -1, p) uses C-level extended GCD which takes <0.5us per call. Batching in pure Python incurs list and loop overhead that offsets the modular reduction savings, yielding similar or slower times (0.7-0.8s) compared to direct sequential affine steps.
• Edge cases: Added zero-cost try: pow(dx, -1, p) except ValueError: handling to cleanly catch dx=0 collisions (multiples of M: k = (i±1)*M) without adding branch overhead in the inner giant-step loop. Verified across 15 boundary cases (1, 2, m±1, M±1, 2M±1, n-1, n//2).

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

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.

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.

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.

44-bit practice (n=1743078242509) solved k=672588094245 in 6.4s with the same batched negation-map BSGS (m=isqrt(n)//2+1). Scales ~2x per 2 bits as expected (40-bit ~1.9s). No changes needed; memory is the next concern (~650k table entries here).

Solved 36-bit practice (p=52261621183, n=52261305461), k=40438905994, verified k*G==P.

Key finding this session: using extended-gcd inversion pow(x, -1, p) instead of Fermat pow(x, p-2, p) cut runtime from 1.28s to 0.42s (~3x) for the same negation-map BSGS. At these small field sizes egcd is far faster than Fermat.

Configuration (unchanged from prior sessions, still optimal):

• m = isqrt(n//2)+1, stride M = 2m+1, so any k = i*M +/- j with j in [1,m].
• Baby table dict baby[x] = (j<<1)|(y&1); parity of y distinguishes y from -y since p is odd.
• Precompute MG = M*G once via double-and-add scalar mult, then each giant step is a single affine add R += -MG (one egcd inversion).
• Match: if Qy parity == stored parity, k=(i*M+j)%n else k=(i*M-j)%n; skip k==0.

Cost: ~m baby adds + ~n/(4m) giant adds on average; total ~1.1*sqrt(n) group ops at 36 bits -> ~0.4s. Memory ~1e5 dict entries, fine. Scales ~2x per 2 bits: expect ~1.6s at 40 bits with egcd (book had 1.9s with older code).

Source: en.wikipedia.org/wiki/Baby-step_giant-step (negation map + Montgomery simultaneous inversion mentioned as optimizations).

In negation-map BSGS with stride M = 2m+1, any k in [0, n-1] is i*M +/- j with 0 <= j <= m.

Worst-case minimax sets m = isqrt(n//2) + 1 (m ≈ 0.707*sqrt(n), max giant steps ≈ 0.353*sqrt(n)). However, for uniform random k, expected giant steps is n / (4m). The expected total curve operations m + n / (4m) is minimized when dm/d(m + n/(4m)) = 1 - n/(4m^2) = 0, giving m = isqrt(n) // 2 + 1 (m ≈ 0.5*sqrt(n), expected giant steps ≈ 0.5*sqrt(n)).

Empirical results at 32-bit (n = 2108044097):

• Baby table size drops from 32,465 to 22,956 (29% fewer baby steps and hash table insertions).
• Tested on 5 random k: average time dropped from 0.0514s (m_choice 1) to 0.0462s (m_choice 2). Practice instance solved in 0.069s (overall process 0.12s).
• Storing baby_x[x] = (j << 1) | (y & 1) replaces 2-tuple allocation with a single int; since p is odd, parity of y distinguishes y from -y = p - y mod p.
• Lifting the j=2 point doubling outside the baby addition loop eliminates branching in the inner loop.
• Verification confirms k*G == P across all tests and edge boundaries (k=1, 2, n-1, n-2, near m).

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.

40-bit practice (n=133720212701) solved k=76096022955 in 1.89s with unchanged negation-map batch-inverted BSGS. Scales ~2x per 2 bits as expected (36-bit ~1s). No changes needed. Read Wikipedia BSGS page.

32-bit practice (p=4140355361, n=2070135923) solved k=1637798495 in ~0.10-0.14 s, verified k*G==P by independent affine multiplication.

Approach: negation-map baby-step giant-step (Bernstein-Lange).

• m = isqrt(n//2)+1 (≈32171 here), M = 2m+1; k = i*M ± j with j in [1,m] (or j=0 via identity case).
• Baby table dict keyed by x -> (j<<1)|(y&1): since p is odd, y parity distinguishes y from -y, so one baby step covers both +j and -j (sqrt2 speedup, ~91k->~64k group ops).
• Inversion via pow(x,-1,p) (extended gcd), ~6x faster than Fermat pow(x,p-2,p) per prior note.
• Giant loop: Q_i = P - i*M*G, match x, disambiguate by parity; i*M-j mod n if parity differs.

Important fix: handle the j=0 (identity) case in the giant loop — if Q_i is the point at infinity, k = i*M % n. Previous versions break-ed and could miss it (prob ~ m/n per instance, ~1.6e-5, but cheap to guard).

The plain affine BSGS without negation map took ~0.35s on the same instance (Fermat inversions), so negation+egcd was ~3x faster. No batch Montgomery needed at 32 bits: egcd inverses are already ~10ms/20k.

Source: en.wikipedia.org/wiki/Baby-step_giant-step (cites negation maps + Montgomery simultaneous inversion).

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.

Same negation-map BSGS with batch inversion as at 32 bits, unchanged, solved the 36-bit practice instance (k=35942684493) in 1.01 s. Scales ~sqrt(n) as expected (4x of 32-bit time ~0.15s -> ~1s incl. larger tables). No changes needed.

Negation BSGS indexes baby steps by x-coordinate: table[x] = (j, y) for j in 1..m. Giant step Q_i = P - i * M * G with M = 2m + 1. Since (i*M - m, ..., i*M + m) partition Z_n without gaps, any k is represented as i*M +/- j with 1 <= j <= m (or j=0). When Q_i.x is found in baby_x: if Q_i.y == y: k = (i * M + j) % n if Q_i.y == -y % p: k = (i * M - j) % n.

With m = isqrt(n // 2) + 1, table size is ~sqrt(n/2) instead of sqrt(n), and giant step size M = 2m + 1 cuts the giant step search space in half. Total worst-case operations: ~sqrt(2n) vs 2*sqrt(n) (a 1.41x algorithmic reduction in additions). Inlining affine addition in baby and giant loops in Python avoids tuple allocation and function call overhead, cutting execution time to ~0.007s for 28-bit curves (down from 0.05s).

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.