# 2026-11-01 — Native ECDLP engine rho_engine (Research Axis A, synthetic instances)

Deliverable. experiments/synthetic_ecdlp/rho_engine/ (Rust 1.95 crate, library + binary), fixture tests/fixtures/ecdlp_instances.json, pytest tests/test_rho_engine.py. Documentation of the iteration functions, canonical representatives and cycle handling with references: rho_engine/README.md.

# Design decisions

1. Field arithmetic. p < 2^62 in Montgomery form (R = 2^64, u128 products, one conditional subtraction); extended-Euclid inversion on i64; Montgomery's simultaneous inversion for every batched phase. Rejected alternative: u128 % p per multiplication (compiles to __umodti3, ≈ 10× slower). Exact integer arithmetic everywhere; floats appear only in the expected_iterations figure and timers.
2. Affine points, per-thread counters {add, dbl, inv, mul} with the same semantics as wp34.ec.OpCounter (1 inversion per add/dbl; 3 resp. 4 multiplications), plus the batch-inversion multiplications and the Montgomery conversions used by the canonical representatives, so the Rust mul is an upper bound.
3. Rho iteration. Teske r-adding walk (r = 20 default), partition from a splitmix64 mix of the Montgomery x residue (multiply-high, no division); distinguished points from the low bits of the same mix. Walk starts ‖uG + vQ‖ via two 16×16 comb tables (≤ 31 additions, counted). vOW parallelism: --walks walks per thread advanced with one simultaneous inversion, shared Mutex<HashMap> of distinguished points, restart after each distinguished point, abandon after 64·2^dp steps. Floyd and Brent single-walk versions use one inversion per step (no batching possible on a sequential chain).
4. Negation map. Literal rule y = min(y, p − y) on the standard form (one Montgomery conversion per step; a residue-ordering rule would save it but was not chosen, to keep the representative as specified). 2-cycles: Bos–Kleinjung–Lenstra "next partition" look-ahead (f stays a function of P). Observation: this rule leaves residual 2-cycles at rate ≈ 1/(2r³) per step (a second rejection from R re-uses the partition that produced R); measured 96 two-cycles / 26 649 steps at r = 4 and 1 / 6 569 at r = 20, consistent. They are caught by the periodic check (one remembered point every K = 32 steps, one comparison per step), as are the 4-, 6-, …-cycles (rate ≈ 1/(4r²)) and the 3-cycles of the order-3 automorphism. Escape by doubling the minimum point of the cycle (Bernstein–Lange–Schwabe 2011), restart if the same cycle is met twice. The expected overhead with r = 20 is visible: at 48 bits --neg with r = 20 produced 2 743 fruitless cycles and 181 k look-ahead rejections for 3.3 M steps, versus 162 cycles / 86 k rejections for 10.9 M steps with r = 128 — use --r 128 or more with --neg, as BLS recommend.
5. Order-3 automorphism. --aut3 requires β, λ from the caller (Python computes them) and verifies β³ = 1 (p), λ³ = 1 (n) and (β·gx, gy) = λ·G at start-up (wrong pairs abort with exit 2). Canonical x = min{x, βx, β²x} (standard form), scalars × λ^i; composed with the negation rule for the order-6 orbit.
6. Kangaroo. vOW tame/wild herds with distinguished points, power-of-two jumps with mean ≈ N√w/4 (Pollard 2000), positions kept mod n, same-herd merges and runaway kangaroos (travel > 3w + 4·m·2^dp) restart at a fresh random position. The runaway guard was added after a test on a 199-element group hung: the jump map's functional graph had disjoint cycles, so the herds never met.
7. Determinism. Every RNG is ChaCha20 seeded from (--seed, thread index, purpose); 1-thread runs are bit-for-bit reproducible (tested). Multi-thread runs are reproducible only in distribution.
8. Memory / time. Per-thread CPU time by CLOCK_THREAD_CPUTIME_ID (summed into cpu_s), wall-clock, getrusage peak RSS, hash-table capacities × entry size. The binary links only libSystem/libiconv (arm64 Mach-O, 880 kB), no OpenSSL, so it can be copied to the Mac Studio nodes.
9. No rayon. std::thread::scope suffices (one worker per thread, shared tables behind a mutex); it avoids a dependency with no benefit for this access pattern.

# Correctness tests (all passing, 2026-11-01)

• cargo test --release: 8 tests — Montgomery arithmetic, batch inversion, Tonelli–Shanks, group law vs repeated addition; small curves (primes 101…32771, prime-order curves found by Legendre point counting, 1 052 (curve, d) pairs brute-forced, each solved by bsgs ×3 settings, rho ×8 settings (Floyd, Brent, dp 1/2 threads, neg, neg+Brent r = 3, neg+mixed, mixed) and kangaroo ×3 interval/thread settings); fixtures (60 instances, 20–32 bits, 10 of them j = 0 per size, generated by scripts/gen_fixtures.py from src/wp34/ec.py + PARI/GP, seed 34): bsgs (default and --memory 1000 --threads 2), rho floyd / brent / dp 1 thread / dp 4 threads / neg / neg+brent / mixed 4, aut3 / neg+aut3 / neg+aut3 floyd / neg+aut3 4 threads on j = 0 curves, kangaroo on [0, n), 4 threads, and on a tight interval; 1-thread determinism; wrong β / wrong λ rejected. Runtime 2.2 s.
• .venv/bin/python -m pytest tests/test_rho_engine.py: 553 passed in 3.5 s — the release binary on every fixture × {bsgs, rho floyd, rho brent, rho dp 1 thread, rho dp 4 threads, rho neg, rho mixed, kangaroo [0, n)} and × {aut3, neg+aut3, neg+aut3 brent} on the 20 j = 0 instances; each answer re-verified in pure Python (Curve.mul(d, G) == Q); determinism; batch mode; interval / memory overrides; wrong β abort.
• Two bugs found and fixed by the small-curve tests: (i) Brent/Floyd meeting an earlier point of the augmented trajectory (after an escape) is not an f-cycle — cycle_length is now bounded and the walk restarts; (ii) the kangaroo runaway guard above.

# Measured throughput (laptop, Apple M5 Max, 18 cores, macOS 27.0, rustc 1.95.0; single runs, seed 1 unless noted)

Instances: rho_engine/bench/instances.json (40/48/56/62-bit prime-order curves, seed 3434); raw JSON of every run with host provenance: rho_engine/bench/results-laptop-2026-11-01.json. These are engine validation numbers (one run each), not the repeated-measurement scaling experiment, which belongs to the scaling driver.

40-bit (runs of 25–60 ms, dominated by start-up): rho 36 M, --neg 25.5 M, --neg --aut3 19.4 M, kangaroo 46.6 M, bsgs 38.8 M ops / CPU-s per thread; 16 threads 330 M ops / wall-s.

• Target (≥ 20 M group additions / s / thread on a 40-bit curve): met for every mode except the order-6 class (--neg --aut3, 18–19 M/s), whose literal canonical rule costs 2 extra multiplications and 4 extra Montgomery conversions per step; it still solves faster per unit time than --neg alone because of the √3 reduction in iterations (62b-j0: 2.6 s vs 3.6 s wall).
• Per-thread rate falls from 48 M (1 thread) to 40 M (16 threads): the M5 Max has performance and efficiency cores and the DP table mutex is taken once per batch; wall-clock scaling 1 → 16 threads is 12.6× on the 56-bit instance.
• The iterations/expected ratios (0.3–2.2 on single runs) are what the √(πn/2) heavy-tailed distribution predicts; the scaling study must use ≥ 10 seeds per point (CONVENTIONS.md §4).
• Kangaroo on the full interval costs ≈ 2√n vs ≈ 1.25√n for rho, as expected; its per-step cost is lower (no canonicalisation, no restarts).

# Usage for the scaling driver

BIN=experiments/synthetic_ecdlp/rho_engine/target/release/rho_engine
$BIN solve --p P --a A --b B --n N --gx GX --gy GY --qx QX --qy QY --alg rho --neg --r 128 --dp 10 \
     --threads 16 --seed 7 --expected-d D --json
$BIN batch --file jobs.json --out results.json --verbose     # jobs: JSON array with the same keys

Each result carries d, ok, ops{add,dbl,inv,mul}, iterations, dp_count, dp_bytes, fruitless_cycles, threads, wall_s, cpu_s, table_entries, peak_rss_bytes, params (big integers as decimal strings).

# Classification

Engine construction and validation — known_reproduced (BSGS, Pollard rho with r-adding walks, vOW distinguished points, negation and order-3/6 classes with fruitless-cycle handling, Pollard kangaroo); no hypothesis evaluated yet. Open items for later sessions: a residue-ordering variant of the canonical representatives (speed), Monte-Carlo estimate of the constant in front of √n for each class size with ≥ 10 seeds per point, and the negative control (random mapping) for the rho family.