1# 2026-11-01 — Native ECDLP engine `rho_engine` (Research Axis A, synthetic instances)23**Deliverable.** `experiments/synthetic_ecdlp/rho_engine/` (Rust 1.95 crate, library + binary), fixture4`tests/fixtures/ecdlp_instances.json`, pytest `tests/test_rho_engine.py`. Documentation of the iteration5functions, canonical representatives and cycle handling with references: `rho_engine/README.md`.67## Design decisions891. **Field arithmetic.** p < 2^62 in Montgomery form (R = 2^64, u128 products, one conditional subtraction);10 extended-Euclid inversion on i64; Montgomery's simultaneous inversion for every batched phase. Rejected11 alternative: `u128 % p` per multiplication (compiles to `__umodti3`, ≈ 10× slower). Exact integer12 arithmetic everywhere; floats appear only in the `expected_iterations` figure and timers.132. **Affine points, per-thread counters** `{add, dbl, inv, mul}` with the same semantics as `wp34.ec.OpCounter`14 (1 inversion per add/dbl; 3 resp. 4 multiplications), plus the batch-inversion multiplications and the15 Montgomery conversions used by the canonical representatives, so the Rust `mul` is an upper bound.163. **Rho iteration.** Teske r-adding walk (r = 20 default), partition from a splitmix64 mix of the17 Montgomery x residue (multiply-high, no division); distinguished points from the low bits of the same mix.18 Walk starts ‖uG + vQ‖ via two 16×16 comb tables (≤ 31 additions, counted). vOW parallelism: `--walks`19 walks per thread advanced with one simultaneous inversion, shared `Mutex<HashMap>` of distinguished points,20 restart after each distinguished point, abandon after 64·2^dp steps. Floyd and Brent single-walk versions21 use one inversion per step (no batching possible on a sequential chain).224. **Negation map.** Literal rule `y = min(y, p − y)` on the standard form (one Montgomery conversion per23 step; a residue-ordering rule would save it but was not chosen, to keep the representative as specified).24 2-cycles: Bos–Kleinjung–Lenstra "next partition" look-ahead (f stays a function of P). Observation: this rule25 leaves residual 2-cycles at rate ≈ 1/(2r³) per step (a second rejection from R re-uses the partition that26 produced R); measured 96 two-cycles / 26 649 steps at r = 4 and 1 / 6 569 at r = 20, consistent. They27 are caught by the periodic check (one remembered point every K = 32 steps, one comparison per step), as28 are the 4-, 6-, …-cycles (rate ≈ 1/(4r²)) and the 3-cycles of the order-3 automorphism. Escape by29 doubling the minimum point of the cycle (Bernstein–Lange–Schwabe 2011), restart if the same cycle is met30 twice. The expected overhead with r = 20 is visible: at 48 bits `--neg` with r = 20 produced 2 74331 fruitless cycles and 181 k look-ahead rejections for 3.3 M steps, versus 162 cycles / 86 k rejections for32 10.9 M steps with r = 128 — use `--r 128` or more with `--neg`, as BLS recommend.335. **Order-3 automorphism.** `--aut3` requires β, λ from the caller (Python computes them) and verifies34 β³ = 1 (p), λ³ = 1 (n) and (β·gx, gy) = λ·G at start-up (wrong pairs abort with exit 2). Canonical x =35 min{x, βx, β²x} (standard form), scalars × λ^i; composed with the negation rule for the order-6 orbit.366. **Kangaroo.** vOW tame/wild herds with distinguished points, power-of-two jumps with mean ≈ N√w/437 (Pollard 2000), positions kept mod n, same-herd merges and runaway kangaroos (travel > 3w + 4·m·2^dp)38 restart at a fresh random position. The runaway guard was added after a test on a 199-element group hung:39 the jump map's functional graph had disjoint cycles, so the herds never met.407. **Determinism.** Every RNG is ChaCha20 seeded from (`--seed`, thread index, purpose); 1-thread runs are41 bit-for-bit reproducible (tested). Multi-thread runs are reproducible only in distribution.428. **Memory / time.** Per-thread CPU time by `CLOCK_THREAD_CPUTIME_ID` (summed into `cpu_s`), wall-clock,43 `getrusage` peak RSS, hash-table capacities × entry size. The binary links only `libSystem`/`libiconv`44 (arm64 Mach-O, 880 kB), no OpenSSL, so it can be copied to the Mac Studio nodes.459. **No `rayon`.** `std::thread::scope` suffices (one worker per thread, shared tables behind a mutex);46 it avoids a dependency with no benefit for this access pattern.4748## Correctness tests (all passing, 2026-11-01)4950* `cargo test --release`: 8 tests — Montgomery arithmetic, batch inversion, Tonelli–Shanks, group law vs51 repeated addition; **small curves** (primes 101…32771, prime-order curves found by Legendre point counting,52 1 052 (curve, d) pairs brute-forced, each solved by bsgs ×3 settings, rho ×8 settings (Floyd, Brent, dp 1/253 threads, neg, neg+Brent r = 3, neg+mixed, mixed) and kangaroo ×3 interval/thread settings); **fixtures**54 (60 instances, 20–32 bits, 10 of them j = 0 per size, generated by `scripts/gen_fixtures.py` from55 `src/wp34/ec.py` + PARI/GP, seed 34): bsgs (default and `--memory 1000 --threads 2`), rho floyd / brent /56 dp 1 thread / dp 4 threads / neg / neg+brent / mixed 4, aut3 / neg+aut3 / neg+aut3 floyd / neg+aut3 457 threads on j = 0 curves, kangaroo on [0, n), 4 threads, and on a tight interval; 1-thread determinism;58 wrong β / wrong λ rejected. Runtime 2.2 s.59* `.venv/bin/python -m pytest tests/test_rho_engine.py`: **553 passed in 3.5 s** — the release binary on every60 fixture × {bsgs, rho floyd, rho brent, rho dp 1 thread, rho dp 4 threads, rho neg, rho mixed, kangaroo61 [0, n)} and × {aut3, neg+aut3, neg+aut3 brent} on the 20 j = 0 instances; each answer re-verified in pure62 Python (`Curve.mul(d, G) == Q`); determinism; batch mode; interval / memory overrides; wrong β abort.63* Two bugs found and fixed by the small-curve tests: (i) Brent/Floyd meeting an earlier point of the64 *augmented* trajectory (after an escape) is not an f-cycle — `cycle_length` is now bounded and the walk65 restarts; (ii) the kangaroo runaway guard above.6667## Measured throughput (laptop, Apple M5 Max, 18 cores, macOS 27.0, rustc 1.95.0; single runs, seed 1 unless noted)6869Instances: `rho_engine/bench/instances.json` (40/48/56/62-bit prime-order curves, seed 3434); raw JSON of70every run with host provenance: `rho_engine/bench/results-laptop-2026-11-01.json`. These are engine71validation numbers (one run each), not the repeated-measurement scaling experiment, which belongs to the72scaling driver.7374| instance | algorithm / options | threads | group ops | ops / CPU-s per thread | ops / wall-s | iterations / expected |75|---|---|---|---|---|---|---|76| 48b | rho dp (r 20, 128 walks), seeds 1–3 | 1 | 15.5–31.5 M | **45.8 M** | 45.6 M | 0.97 / 1.58 / 1.97 |77| 48b | rho dp `--neg --r 128` | 1 | 11.2 M | 30.7 M | 30.6 M | 0.99 |78| 48b | rho dp `--neg --r 512` | 1 | 8.1 M | 30.6 M | 30.3 M | 0.72 |79| 48b | kangaroo [0, n) | 1 | 28.4 M | 48.9 M | 48.3 M | 1.14 |80| 48b | bsgs (m = 2^24, 288 MB RSS) | 1 | 24.8 M | 41.1 M | 39.2 M | — |81| 48b | rho Brent (single walk, 1 inversion/step) | 1 | 33.9 M | 9.0 M | 8.9 M | 2.17 |82| 56b | rho dp | 1 | 126 M | **48.5 M** | 48.4 M | 0.44 |83| 56b | rho dp `--neg --r 128` | 1 | 189 M | 30.5 M | 30.1 M | 0.91 |84| 56b | kangaroo [0, n) | 1 | 757 M | 48.4 M | 47.8 M | 1.65 |85| 56b | rho dp | 2 / 4 / 8 / 12 / 16 | 253 / 503 / 438 / 466 / 620 M | 45.9 / 45.5 / 41.8 / 41.0 / 40.5 M | 89 / 178 / 327 / 483 / **613 M** | 0.87–2.14 |86| 62b | rho dp | 16 | 1.82 G | 40.3 M | 608 M | 0.86 (wall 3.0 s) |87| 62b | rho dp `--neg --r 128` | 16 | 1.45 G | 26.8 M | 397 M | 0.96 (wall 3.6 s) |88| 62b-j0 | rho dp `--neg --aut3 --r 128` | 16 | 0.70 G | 18.2 M | 275 M | 0.76 (wall 2.6 s) |89| 62b | kangaroo [0, n) | 16 | 4.61 G | 39.1 M | 580 M | 1.37 (wall 8.0 s) |909140-bit (runs of 25–60 ms, dominated by start-up): rho 36 M, `--neg` 25.5 M, `--neg --aut3` 19.4 M,92kangaroo 46.6 M, bsgs 38.8 M ops / CPU-s per thread; 16 threads 330 M ops / wall-s.9394* **Target (≥ 20 M group additions / s / thread on a 40-bit curve): met** for every mode except the95 order-6 class (`--neg --aut3`, 18–19 M/s), whose literal canonical rule costs 2 extra multiplications and96 4 extra Montgomery conversions per step; it still *solves* faster per unit time than `--neg` alone97 because of the √3 reduction in iterations (62b-j0: 2.6 s vs 3.6 s wall).98* Per-thread rate falls from 48 M (1 thread) to 40 M (16 threads): the M5 Max has performance and99 efficiency cores and the DP table mutex is taken once per batch; wall-clock scaling 1 → 16 threads is100 12.6× on the 56-bit instance.101* The iterations/expected ratios (0.3–2.2 on single runs) are what the √(πn/2) heavy-tailed distribution102 predicts; the scaling study must use ≥ 10 seeds per point (CONVENTIONS.md §4).103* Kangaroo on the full interval costs ≈ 2√n vs ≈ 1.25√n for rho, as expected; its per-step cost is lower104 (no canonicalisation, no restarts).105106## Usage for the scaling driver107108```109BIN=experiments/synthetic_ecdlp/rho_engine/target/release/rho_engine110$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 \111 --threads 16 --seed 7 --expected-d D --json112$BIN batch --file jobs.json --out results.json --verbose # jobs: JSON array with the same keys113```114Each result carries `d, ok, ops{add,dbl,inv,mul}, iterations, dp_count, dp_bytes, fruitless_cycles,115threads, wall_s, cpu_s, table_entries, peak_rss_bytes, params` (big integers as decimal strings).116117## Classification118119Engine construction and validation — `known_reproduced` (BSGS, Pollard rho with r-adding walks, vOW120distinguished points, negation and order-3/6 classes with fruitless-cycle handling, Pollard kangaroo); no121hypothesis evaluated yet. Open items for later sessions: a residue-ordering variant of the canonical122representatives (speed), Monte-Carlo estimate of the constant in front of √n for each class size with ≥ 10123seeds per point, and the negative control (random mapping) for the rho family.124