# rho_engine — native ECDLP experimentation engine (WP34-UQO, Research Axis A)

Rust crate (library + binary) solving synthetic elliptic-curve discrete logarithms Q = d·G on prime-order
short Weierstrass curves y² = x³ + ax + b over F_p with **p < 2^62**, by the established generic methods, with
exact operation counts, memory and time measurements. Synthetic instances only (see `docs/MANDATE.md` §2):
the engine takes the curve and the two points from the command line; it never touches real keys.

Conventions match the Python reference `src/wp34/ec.py`: affine points, the point at infinity is a separate
flag, one group addition = one field inversion + 3 multiplications (λ, λ², λ·(x₁−x₃)), one doubling = one
inversion + 4 multiplications (x², λ, λ², λ·(x₁−x₃)); the `mul` counter also includes the multiplications of
Montgomery's simultaneous inversion (3 per element) and the Montgomery-form conversions used by the canonical
representatives (documented below), so `mul` is an upper bound of "pure" multiplication counts.

```
cargo build --release          # → target/release/rho_engine (arm64 Mach-O, links only libSystem/libiconv)
cargo test --release           # unit tests + small-curve brute force + 60 fixture instances
```

## CLI

```
rho_engine solve --p P --a A --b B --n N --gx GX --gy GY --qx QX --qy QY --alg {bsgs,rho,kangaroo}
                 [--seed S] [--threads T] [--json] [--label L] [--expected-d D]
      rho:       [--cycle floyd|brent|dp] [--r 20] [--dp BITS] [--walks 128] [--mixed K] [--neg]
                 [--aut3 --beta B --lambda L] [--cycle-check 32] [--max-walk-len N]
      kangaroo:  [--lo LO] [--hi HI] [--dp BITS] [--walks W]
      bsgs:      [--memory M] [--chains 64]
rho_engine batch --file jobs.json --out results.json [--verbose]
```

All integers are decimal strings (also in JSON). `solve` prints one JSON object and exits 0 on success
(2 if the log was not found / not verified, with an `"error"` field for invalid inputs). `batch` reads a JSON
array of job objects with the same keys as the flags (`p, a, b, n, gx, gy, qx, qy, alg, seed, threads, r,
cycle, dp, walks, mixed, neg, aut3, beta, lambda, lo, hi, memory, label, expected_d`), runs them sequentially
(parallelism is inside each job) and writes a JSON array of result objects.

Result object (common keys):

| key | meaning |
|---|---|
| `d` | the discrete logarithm (decimal string) |
| `ok` | `d·G == Q` re-verified inside Rust after the search |
| `match` | `d == expected_d` when `--expected-d` was given |
| `ops` | `{add, dbl, inv, mul}` summed over all threads (setup, walks, verification) |
| `group_ops`, `group_ops_per_cpu_s`, `group_ops_per_wall_s` | `add + dbl` and throughput |
| `iterations` | steps of the iteration function (rho/kangaroo) or giant steps computed (bsgs) |
| `expected_iterations` | √(πn/(2·class)) for rho, 2√w for kangaroo (theory, for comparison) |
| `dp_count`, `dp_bytes`, `table_entries`, `table_bytes` | distinguished-point / baby-step table size |
| `fruitless_cycles`, `fruitless_by_length`, `lookahead_rejections`, `doubling_fallbacks` | negation/automorphism-class bookkeeping |
| `restarts`, `abandoned_walks`, `useless_collisions` (`herd_collisions` for kangaroo) | walk bookkeeping |
| `threads`, `wall_s`, `cpu_s` (sum of per-thread `CLOCK_THREAD_CPUTIME_ID` timers), `process_cpu_s` | time |
| `peak_rss_bytes` | `getrusage(RUSAGE_SELF).ru_maxrss` |
| `params` | every effective parameter plus the instance, for provenance |

## Field and group arithmetic (`src/field.rs`, `src/curve.rs`)

* Montgomery representation with R = 2^64, u128 products, one conditional subtraction (valid because p < 2^62).
  Inversion by the extended Euclidean algorithm on i64, converted back with R³ mod p.
* Montgomery's simultaneous inversion (`Field::batch_inv`, 3(k−1) multiplications + 1 inversion) is used by
  every batched phase: the W walks of a thread (rho), the W kangaroos of a thread, and the S independent
  chains of the baby-step and giant-step phases of BSGS.
* Scalar bookkeeping modulo the prime n uses u128 products and `%` (`Modn`).
* Random walk starts u·G + v·Q use two fixed-base comb tables (16 nibble positions × 16 entries each), so a
  restart costs ≤ 31 additions; these additions are included in `ops`.

## Algorithms

### `bsgs` — baby-step giant-step (Shanks 1971)

m = ⌈√n⌉ baby steps (`--memory m` overrides: time/memory trade-off, giant steps become ⌈n/m⌉+1), x-coordinate
keyed `hashbrown` table x(jG) → j for 0 < j < m; giant points R_i = Q − i·(mG); a hit means R_i = ±jG, so both
d = i·m + j and d = i·m − j are verified. Reported: `table_entries`, `table_bytes` (capacity × 17 bytes),
`baby_steps`, `giant_steps_planned`, `build_s`. The giant phase is split across `--threads`.

### `rho` — Pollard rho (Pollard 1978) with Teske's r-adding walk (Teske 2001)

* **Multipliers.** M_j = u_j·G + v_j·Q, j ∈ [0, r), with u_j, v_j uniform in [1, n) from a ChaCha20 RNG seeded
  by `--seed` (r = 20 by default, Teske's recommendation).
* **Partition.** j = h(x) with h(x) = ⌊(mix64(x_M) ≫ 32) · r / 2^32⌋ where x_M is the Montgomery residue of
  the x-coordinate and mix64 the splitmix64 finaliser; the distinguished-point predicate uses the *low* bits of
  the same mix (`mix64(x_M) & (2^d − 1) == 0`), so the two decisions are independent.
* **Iteration function.** f(P) = ‖P + M_j‖ (adding partition) or f(P) = ‖2P‖ (doubling partition), with the
  scalars (u, v) updated accordingly (u + u_j, v + v_j) or (2u, 2v). ‖·‖ is the canonical representative
  defined below (identity without `--neg/--aut3`).
* **`--mixed k`** (Teske's mixed walk): every k-th partition (j ≡ k−1 mod k) is a doubling partition; the
  default k = 0 is the pure r-adding walk.
* **Cycle detection, single walk**: `--cycle floyd` (x_i vs x_{2i}, 3 steps per iteration) or `--cycle brent`
  (teleporting tortoise at powers of two, 1 step per iteration). A collision with different scalars gives
  d = (u₁ − u₂)/(v₂ − v₁) mod n; identical scalars mean a fruitless cycle (handled below); the degenerate
  v₁ = v₂ case restarts from a new random point.
* **`--cycle dp` (default): van Oorschot–Wiener parallel collision search (1999).** Each of `--threads` threads
  runs `--walks` (default 128) independent walks, each started at a random ‖u·G + v·Q‖ and advanced together
  with one simultaneous inversion per step. A point whose mix has `--dp` low zero bits (default
  ⌊log₂n/4⌋ − 2, ≥ 1) is distinguished: (x, y, u, v) is sent to a shared table (`Mutex<HashMap>`) and the walk
  restarts at a fresh random point. Two entries with the same x and different scalars solve the log
  (d = (u₁ − u₂)/(v₂ − v₁) if y₁ = y₂, d = −(u₁ + u₂)/(v₁ + v₂) if y₁ = −y₂). Walks exceeding
  `--max-walk-len` (default 64·2^dp) steps without a distinguished point are abandoned. With one thread the
  run is fully deterministic (the per-thread RNG is derived from `--seed` and the thread index).

#### Equivalence classes

* **`--neg` (negation map; Wiener–Zuccherato 1999, Gallant–Lambert–Vanstone 2000).** Canonical
  representative of {P, −P}: the point whose standard-form y satisfies 2y < p, i.e. y = min(y, p − y);
  choosing −P flips the scalars (u, v) ↦ (−u, −v). Expected iterations drop from √(πn/2) to √(πn/4).
* **`--aut3` (order-3 automorphism ζ: (x, y) ↦ (βx, y) = λ·(x, y) on a = 0 curves with p ≡ 1 mod 3;
  Duursma–Gaudry–Morain 1999, GLV 2000).** Requires `--beta` and `--lambda` from the caller; at start-up the
  engine checks β³ ≡ 1 (mod p), λ³ ≡ 1 (mod n) and (β·gx, gy) = λ·G, and aborts otherwise. Canonical
  representative of {P, ζP, ζ²P}: the one with the smallest standard-form x among {x, βx, β²x}; choosing
  ζ^i P multiplies the scalars by λ^i. `--neg --aut3` composes both (orbit of size 6): the x rule is applied
  first, then the y rule. Expected iterations √(πn/6) and √(πn/12) respectively.
* **Fruitless cycles (Bos–Kleinjung–Lenstra 2010, Bernstein–Lange–Schwabe 2011).**
  1. *2-cycles, look-ahead.* With `--neg`, after computing R = ‖P + M_j‖ the engine checks h(R) ≠ j; if
     h(R) = j (the configuration that allows ‖R + M_j‖ = ‖P‖), the step is discarded (`lookahead_rejections`,
     one wasted addition) and the next partition j+1 is tried, and so on; after r rejections f(P) = ‖2P‖
     (`doubling_fallbacks`). f remains a function of P alone, so colliding walks stay merged. This is the
     BKL "next partition" rule; it leaves residual 2-cycles with probability ≈ 1/(2r³) per step (when the
     partition sequence j, j+1 repeats from R), which the periodic check below catches — the measured
     `fruitless_by_length` histograms confirm the ≈ r⁻³ rate (e.g. 96 two-cycles in 26 649 steps at r = 4,
     1 in 6 569 steps at r = 20).
  2. *Longer cycles (4, 6, … with `--neg`; 3, 6, … with `--aut3`), periodic check.* Every walk remembers its
     point every `--cycle-check` K steps (default 32) and compares every subsequent point with it (one
     comparison per step), so any fruitless cycle of length ≤ K is detected within ≤ K + length steps of
     entering it. Detection also happens in Floyd/Brent mode when the collision has identical scalars.
  3. *Escape.* The cycle is traversed once to find its minimum point P_min (smallest Montgomery x, ties by y)
     and the walk continues from ‖2·P_min‖ with doubled scalars — a function of the cycle only, so two walks
     trapped in the same cycle leave it to the same point (BLS 2011). If the same P_min is met twice in a row
     the walk restarts from a fresh random point. Counts: `fruitless_cycles`, `fruitless_by_length`.
  Because the 4-cycle rate is ≈ 1/(4r²) per step, use a larger r (`--r 128`, `--r 512`) with `--neg`, as
  BLS recommend; r = 20 is kept as the default for comparability with Teske's walk.

### `kangaroo` — Pollard's lambda method (Pollard 1978, 2000) in the van Oorschot–Wiener parallel form

For d ∈ [lo, hi] (`--lo --hi`, default [0, n−1]), width w = hi − lo + 1. N = threads × `--walks` kangaroos
(default `--walks` = clamp(2^(⌊log₂w/4⌋−2), 2, 64), even), half tame, half wild. Tame kangaroo c starts at
position t_c = lo + ⌊w/2⌋ + c·s (point t_c·G), wild kangaroo c at offset o_c = c·s (point Q + o_c·G), with
spacing s = ⌈m/(N/2)⌉. Jump set J = {2^0·G, …, 2^{k−1}·G} (Pollard 2000), j = h(x) ∈ [0, k), k chosen so that
the mean jump m = (2^k − 1)/k is closest to N·√w/4 (= √w/2 for the classical single tame/wild pair). Every
kangaroo keeps its position modulo n and reports distinguished points (same predicate and default `--dp` as
rho, computed from w) to the shared table; a tame/wild collision with positions (t, o) gives d = t − o (same
y) or d = −t − o (opposite y), verified before being accepted. A same-herd collision (merged trails) or a
kangaroo that has travelled more than 3w + 4·m·2^dp restarts at a fresh random position of its herd
(`herd_collisions`, `abandoned_walks`, `restarts`). Expected cost ≈ 2√w group operations plus the
distinguished-point overshoot N·2^dp.

## Tests

* `cargo test --release`: Montgomery arithmetic round-trips and batch inversion; group law against repeated
  addition; **small curves** (9 primes 101…32771, two prime-order curves each, orders enumerated by Legendre
  symbols, every log brute-forced for n ≤ 300 and 30 spread values otherwise; 1 052 (curve, d) pairs × 14
  algorithm/option combinations); **fixtures** `tests/fixtures/ecdlp_instances.json` (60 instances: 10 generic
  curves for each of 20/24/28/32 bits and 10 j = 0 curves for 24 and 32 bits with β, λ and random d,
  generated by `scripts/gen_fixtures.py` from `src/wp34/ec.py` + PARI/GP) with 15–19 combinations each;
  1-thread determinism; rejection of wrong (β, λ).
* `tests/test_rho_engine.py` (repository `pytest`): the release binary on every fixture with bsgs, rho
  floyd / brent / dp (1 and 4 threads) / neg / mixed, aut3 and neg+aut3 (j = 0 only), kangaroo on [0, n);
  the answer is re-verified in pure Python (`Curve.mul`), determinism, batch mode, memory/interval overrides.

## Measured throughput (Apple M5 Max laptop, macOS 27, rustc 1.95, see `research_log/2026-11-01-rho-engine.md`)

Single thread, group operations per CPU-second (one run each; raw JSON with host provenance in
`bench/results-laptop-2026-11-01.json`): rho dp (r = 20, 128 walks) **45.8 M/s** at 48 bits and **48.5 M/s**
at 56 bits; rho `--neg --r 128` ≈ 30.6 M/s; rho `--neg --aut3 --r 128` ≈ 18–19 M/s (the literal
min{x, βx, β²x} / min{y, p−y} rules cost 2 multiplications + 4 Montgomery conversions per step); kangaroo
≈ 48.5 M/s; BSGS ≈ 41 M/s (m = 2^24, 288 MB); single-walk Brent (one inversion per step) ≈ 9 M/s.
16 threads: ≈ 610 M group ops/s wall-clock (12.6× over one thread; the M5 Max mixes performance and
efficiency cores), a 62-bit instance is solved in ≈ 3 s (≈ 1.8 G group operations).

## References

* V. Shanks, *Class number, a theory of factorization, and genera*, Proc. Symp. Pure Math. 20 (1971) — BSGS.
* J. M. Pollard, *Monte Carlo methods for index computation (mod p)*, Math. Comp. 32 (1978) — rho and lambda.
* E. Teske, *On random walks for Pollard's rho method*, Math. Comp. 70 (2001) 809–825 — r-adding and mixed walks.
* P. C. van Oorschot, M. J. Wiener, *Parallel collision search with cryptanalytic applications*, J. Cryptology
  12 (1999) 1–28 — distinguished points, parallel rho and kangaroo.
* J. M. Pollard, *Kangaroos, Monopoly and discrete logarithms*, J. Cryptology 13 (2000) 437–447 — power-of-two jumps.
* M. J. Wiener, R. J. Zuccherato, *Faster attacks on elliptic curve cryptosystems*, SAC 1998, LNCS 1556 (1999) — negation map.
* R. Gallant, R. Lambert, S. Vanstone, *Improving the parallelized Pollard lambda search on anomalous binary
  curves*, Math. Comp. 69 (2000) 1699–1705 — automorphism classes.
* I. Duursma, P. Gaudry, F. Morain, *Speeding up the discrete log computation on curves with automorphisms*,
  ASIACRYPT 1999, LNCS 1716 — order-3/6 automorphisms, fruitless cycles.
* J. W. Bos, T. Kleinjung, A. K. Lenstra, *On the use of the negation map in the Pollard rho method*,
  ANTS-IX 2010, LNCS 6197 — look-ahead, cycle reduction.
* D. J. Bernstein, T. Lange, P. Schwabe, *On the correct use of the negation map in the Pollard rho method*,
  PKC 2011, LNCS 6571 — fruitless-cycle detection and escape by doubling the minimum point.