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

| instance | algorithm / options | threads | group ops | ops / CPU-s per thread | ops / wall-s | iterations / expected |
|---|---|---|---|---|---|---|
| 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 |
| 48b | rho dp `--neg --r 128` | 1 | 11.2 M | 30.7 M | 30.6 M | 0.99 |
| 48b | rho dp `--neg --r 512` | 1 | 8.1 M | 30.6 M | 30.3 M | 0.72 |
| 48b | kangaroo [0, n) | 1 | 28.4 M | 48.9 M | 48.3 M | 1.14 |
| 48b | bsgs (m = 2^24, 288 MB RSS) | 1 | 24.8 M | 41.1 M | 39.2 M | — |
| 48b | rho Brent (single walk, 1 inversion/step) | 1 | 33.9 M | 9.0 M | 8.9 M | 2.17 |
| 56b | rho dp | 1 | 126 M | **48.5 M** | 48.4 M | 0.44 |
| 56b | rho dp `--neg --r 128` | 1 | 189 M | 30.5 M | 30.1 M | 0.91 |
| 56b | kangaroo [0, n) | 1 | 757 M | 48.4 M | 47.8 M | 1.65 |
| 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 |
| 62b | rho dp | 16 | 1.82 G | 40.3 M | 608 M | 0.86 (wall 3.0 s) |
| 62b | rho dp `--neg --r 128` | 16 | 1.45 G | 26.8 M | 397 M | 0.96 (wall 3.6 s) |
| 62b-j0 | rho dp `--neg --aut3 --r 128` | 16 | 0.70 G | 18.2 M | 275 M | 0.76 (wall 2.6 s) |
| 62b | kangaroo [0, n) | 16 | 4.61 G | 39.1 M | 580 M | 1.37 (wall 8.0 s) |

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.