1# rho_engine — native ECDLP experimentation engine (WP34-UQO, Research Axis A)23Rust crate (library + binary) solving synthetic elliptic-curve discrete logarithms Q = d·G on prime-order4short Weierstrass curves y² = x³ + ax + b over F_p with **p < 2^62**, by the established generic methods, with5exact operation counts, memory and time measurements. Synthetic instances only (see `docs/MANDATE.md` §2):6the engine takes the curve and the two points from the command line; it never touches real keys.78Conventions match the Python reference `src/wp34/ec.py`: affine points, the point at infinity is a separate9flag, one group addition = one field inversion + 3 multiplications (λ, λ², λ·(x₁−x₃)), one doubling = one10inversion + 4 multiplications (x², λ, λ², λ·(x₁−x₃)); the `mul` counter also includes the multiplications of11Montgomery's simultaneous inversion (3 per element) and the Montgomery-form conversions used by the canonical12representatives (documented below), so `mul` is an upper bound of "pure" multiplication counts.1314```15cargo build --release # → target/release/rho_engine (arm64 Mach-O, links only libSystem/libiconv)16cargo test --release # unit tests + small-curve brute force + 60 fixture instances17```1819## CLI2021```22rho_engine solve --p P --a A --b B --n N --gx GX --gy GY --qx QX --qy QY --alg {bsgs,rho,kangaroo}23 [--seed S] [--threads T] [--json] [--label L] [--expected-d D]24 rho: [--cycle floyd|brent|dp] [--r 20] [--dp BITS] [--walks 128] [--mixed K] [--neg]25 [--aut3 --beta B --lambda L] [--cycle-check 32] [--max-walk-len N]26 kangaroo: [--lo LO] [--hi HI] [--dp BITS] [--walks W]27 bsgs: [--memory M] [--chains 64]28rho_engine batch --file jobs.json --out results.json [--verbose]29```3031All integers are decimal strings (also in JSON). `solve` prints one JSON object and exits 0 on success32(2 if the log was not found / not verified, with an `"error"` field for invalid inputs). `batch` reads a JSON33array of job objects with the same keys as the flags (`p, a, b, n, gx, gy, qx, qy, alg, seed, threads, r,34cycle, dp, walks, mixed, neg, aut3, beta, lambda, lo, hi, memory, label, expected_d`), runs them sequentially35(parallelism is inside each job) and writes a JSON array of result objects.3637Result object (common keys):3839| key | meaning |40|---|---|41| `d` | the discrete logarithm (decimal string) |42| `ok` | `d·G == Q` re-verified inside Rust after the search |43| `match` | `d == expected_d` when `--expected-d` was given |44| `ops` | `{add, dbl, inv, mul}` summed over all threads (setup, walks, verification) |45| `group_ops`, `group_ops_per_cpu_s`, `group_ops_per_wall_s` | `add + dbl` and throughput |46| `iterations` | steps of the iteration function (rho/kangaroo) or giant steps computed (bsgs) |47| `expected_iterations` | √(πn/(2·class)) for rho, 2√w for kangaroo (theory, for comparison) |48| `dp_count`, `dp_bytes`, `table_entries`, `table_bytes` | distinguished-point / baby-step table size |49| `fruitless_cycles`, `fruitless_by_length`, `lookahead_rejections`, `doubling_fallbacks` | negation/automorphism-class bookkeeping |50| `restarts`, `abandoned_walks`, `useless_collisions` (`herd_collisions` for kangaroo) | walk bookkeeping |51| `threads`, `wall_s`, `cpu_s` (sum of per-thread `CLOCK_THREAD_CPUTIME_ID` timers), `process_cpu_s` | time |52| `peak_rss_bytes` | `getrusage(RUSAGE_SELF).ru_maxrss` |53| `params` | every effective parameter plus the instance, for provenance |5455## Field and group arithmetic (`src/field.rs`, `src/curve.rs`)5657* Montgomery representation with R = 2^64, u128 products, one conditional subtraction (valid because p < 2^62).58 Inversion by the extended Euclidean algorithm on i64, converted back with R³ mod p.59* Montgomery's simultaneous inversion (`Field::batch_inv`, 3(k−1) multiplications + 1 inversion) is used by60 every batched phase: the W walks of a thread (rho), the W kangaroos of a thread, and the S independent61 chains of the baby-step and giant-step phases of BSGS.62* Scalar bookkeeping modulo the prime n uses u128 products and `%` (`Modn`).63* Random walk starts u·G + v·Q use two fixed-base comb tables (16 nibble positions × 16 entries each), so a64 restart costs ≤ 31 additions; these additions are included in `ops`.6566## Algorithms6768### `bsgs` — baby-step giant-step (Shanks 1971)6970m = ⌈√n⌉ baby steps (`--memory m` overrides: time/memory trade-off, giant steps become ⌈n/m⌉+1), x-coordinate71keyed `hashbrown` table x(jG) → j for 0 < j < m; giant points R_i = Q − i·(mG); a hit means R_i = ±jG, so both72d = i·m + j and d = i·m − j are verified. Reported: `table_entries`, `table_bytes` (capacity × 17 bytes),73`baby_steps`, `giant_steps_planned`, `build_s`. The giant phase is split across `--threads`.7475### `rho` — Pollard rho (Pollard 1978) with Teske's r-adding walk (Teske 2001)7677* **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 seeded78 by `--seed` (r = 20 by default, Teske's recommendation).79* **Partition.** j = h(x) with h(x) = ⌊(mix64(x_M) ≫ 32) · r / 2^32⌋ where x_M is the Montgomery residue of80 the x-coordinate and mix64 the splitmix64 finaliser; the distinguished-point predicate uses the *low* bits of81 the same mix (`mix64(x_M) & (2^d − 1) == 0`), so the two decisions are independent.82* **Iteration function.** f(P) = ‖P + M_j‖ (adding partition) or f(P) = ‖2P‖ (doubling partition), with the83 scalars (u, v) updated accordingly (u + u_j, v + v_j) or (2u, 2v). ‖·‖ is the canonical representative84 defined below (identity without `--neg/--aut3`).85* **`--mixed k`** (Teske's mixed walk): every k-th partition (j ≡ k−1 mod k) is a doubling partition; the86 default k = 0 is the pure r-adding walk.87* **Cycle detection, single walk**: `--cycle floyd` (x_i vs x_{2i}, 3 steps per iteration) or `--cycle brent`88 (teleporting tortoise at powers of two, 1 step per iteration). A collision with different scalars gives89 d = (u₁ − u₂)/(v₂ − v₁) mod n; identical scalars mean a fruitless cycle (handled below); the degenerate90 v₁ = v₂ case restarts from a new random point.91* **`--cycle dp` (default): van Oorschot–Wiener parallel collision search (1999).** Each of `--threads` threads92 runs `--walks` (default 128) independent walks, each started at a random ‖u·G + v·Q‖ and advanced together93 with one simultaneous inversion per step. A point whose mix has `--dp` low zero bits (default94 ⌊log₂n/4⌋ − 2, ≥ 1) is distinguished: (x, y, u, v) is sent to a shared table (`Mutex<HashMap>`) and the walk95 restarts at a fresh random point. Two entries with the same x and different scalars solve the log96 (d = (u₁ − u₂)/(v₂ − v₁) if y₁ = y₂, d = −(u₁ + u₂)/(v₁ + v₂) if y₁ = −y₂). Walks exceeding97 `--max-walk-len` (default 64·2^dp) steps without a distinguished point are abandoned. With one thread the98 run is fully deterministic (the per-thread RNG is derived from `--seed` and the thread index).99100#### Equivalence classes101102* **`--neg` (negation map; Wiener–Zuccherato 1999, Gallant–Lambert–Vanstone 2000).** Canonical103 representative of {P, −P}: the point whose standard-form y satisfies 2y < p, i.e. y = min(y, p − y);104 choosing −P flips the scalars (u, v) ↦ (−u, −v). Expected iterations drop from √(πn/2) to √(πn/4).105* **`--aut3` (order-3 automorphism ζ: (x, y) ↦ (βx, y) = λ·(x, y) on a = 0 curves with p ≡ 1 mod 3;106 Duursma–Gaudry–Morain 1999, GLV 2000).** Requires `--beta` and `--lambda` from the caller; at start-up the107 engine checks β³ ≡ 1 (mod p), λ³ ≡ 1 (mod n) and (β·gx, gy) = λ·G, and aborts otherwise. Canonical108 representative of {P, ζP, ζ²P}: the one with the smallest standard-form x among {x, βx, β²x}; choosing109 ζ^i P multiplies the scalars by λ^i. `--neg --aut3` composes both (orbit of size 6): the x rule is applied110 first, then the y rule. Expected iterations √(πn/6) and √(πn/12) respectively.111* **Fruitless cycles (Bos–Kleinjung–Lenstra 2010, Bernstein–Lange–Schwabe 2011).**112 1. *2-cycles, look-ahead.* With `--neg`, after computing R = ‖P + M_j‖ the engine checks h(R) ≠ j; if113 h(R) = j (the configuration that allows ‖R + M_j‖ = ‖P‖), the step is discarded (`lookahead_rejections`,114 one wasted addition) and the next partition j+1 is tried, and so on; after r rejections f(P) = ‖2P‖115 (`doubling_fallbacks`). f remains a function of P alone, so colliding walks stay merged. This is the116 BKL "next partition" rule; it leaves residual 2-cycles with probability ≈ 1/(2r³) per step (when the117 partition sequence j, j+1 repeats from R), which the periodic check below catches — the measured118 `fruitless_by_length` histograms confirm the ≈ r⁻³ rate (e.g. 96 two-cycles in 26 649 steps at r = 4,119 1 in 6 569 steps at r = 20).120 2. *Longer cycles (4, 6, … with `--neg`; 3, 6, … with `--aut3`), periodic check.* Every walk remembers its121 point every `--cycle-check` K steps (default 32) and compares every subsequent point with it (one122 comparison per step), so any fruitless cycle of length ≤ K is detected within ≤ K + length steps of123 entering it. Detection also happens in Floyd/Brent mode when the collision has identical scalars.124 3. *Escape.* The cycle is traversed once to find its minimum point P_min (smallest Montgomery x, ties by y)125 and the walk continues from ‖2·P_min‖ with doubled scalars — a function of the cycle only, so two walks126 trapped in the same cycle leave it to the same point (BLS 2011). If the same P_min is met twice in a row127 the walk restarts from a fresh random point. Counts: `fruitless_cycles`, `fruitless_by_length`.128 Because the 4-cycle rate is ≈ 1/(4r²) per step, use a larger r (`--r 128`, `--r 512`) with `--neg`, as129 BLS recommend; r = 20 is kept as the default for comparability with Teske's walk.130131### `kangaroo` — Pollard's lambda method (Pollard 1978, 2000) in the van Oorschot–Wiener parallel form132133For d ∈ [lo, hi] (`--lo --hi`, default [0, n−1]), width w = hi − lo + 1. N = threads × `--walks` kangaroos134(default `--walks` = clamp(2^(⌊log₂w/4⌋−2), 2, 64), even), half tame, half wild. Tame kangaroo c starts at135position 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), with136spacing s = ⌈m/(N/2)⌉. Jump set J = {2^0·G, …, 2^{k−1}·G} (Pollard 2000), j = h(x) ∈ [0, k), k chosen so that137the mean jump m = (2^k − 1)/k is closest to N·√w/4 (= √w/2 for the classical single tame/wild pair). Every138kangaroo keeps its position modulo n and reports distinguished points (same predicate and default `--dp` as139rho, computed from w) to the shared table; a tame/wild collision with positions (t, o) gives d = t − o (same140y) or d = −t − o (opposite y), verified before being accepted. A same-herd collision (merged trails) or a141kangaroo that has travelled more than 3w + 4·m·2^dp restarts at a fresh random position of its herd142(`herd_collisions`, `abandoned_walks`, `restarts`). Expected cost ≈ 2√w group operations plus the143distinguished-point overshoot N·2^dp.144145## Tests146147* `cargo test --release`: Montgomery arithmetic round-trips and batch inversion; group law against repeated148 addition; **small curves** (9 primes 101…32771, two prime-order curves each, orders enumerated by Legendre149 symbols, every log brute-forced for n ≤ 300 and 30 spread values otherwise; 1 052 (curve, d) pairs × 14150 algorithm/option combinations); **fixtures** `tests/fixtures/ecdlp_instances.json` (60 instances: 10 generic151 curves for each of 20/24/28/32 bits and 10 j = 0 curves for 24 and 32 bits with β, λ and random d,152 generated by `scripts/gen_fixtures.py` from `src/wp34/ec.py` + PARI/GP) with 15–19 combinations each;153 1-thread determinism; rejection of wrong (β, λ).154* `tests/test_rho_engine.py` (repository `pytest`): the release binary on every fixture with bsgs, rho155 floyd / brent / dp (1 and 4 threads) / neg / mixed, aut3 and neg+aut3 (j = 0 only), kangaroo on [0, n);156 the answer is re-verified in pure Python (`Curve.mul`), determinism, batch mode, memory/interval overrides.157158## Measured throughput (Apple M5 Max laptop, macOS 27, rustc 1.95, see `research_log/2026-11-01-rho-engine.md`)159160Single thread, group operations per CPU-second (one run each; raw JSON with host provenance in161`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**162at 56 bits; rho `--neg --r 128` ≈ 30.6 M/s; rho `--neg --aut3 --r 128` ≈ 18–19 M/s (the literal163min{x, βx, β²x} / min{y, p−y} rules cost 2 multiplications + 4 Montgomery conversions per step); kangaroo164≈ 48.5 M/s; BSGS ≈ 41 M/s (m = 2^24, 288 MB); single-walk Brent (one inversion per step) ≈ 9 M/s.16516 threads: ≈ 610 M group ops/s wall-clock (12.6× over one thread; the M5 Max mixes performance and166efficiency cores), a 62-bit instance is solved in ≈ 3 s (≈ 1.8 G group operations).167168## References169170* V. Shanks, *Class number, a theory of factorization, and genera*, Proc. Symp. Pure Math. 20 (1971) — BSGS.171* J. M. Pollard, *Monte Carlo methods for index computation (mod p)*, Math. Comp. 32 (1978) — rho and lambda.172* E. Teske, *On random walks for Pollard's rho method*, Math. Comp. 70 (2001) 809–825 — r-adding and mixed walks.173* P. C. van Oorschot, M. J. Wiener, *Parallel collision search with cryptanalytic applications*, J. Cryptology174 12 (1999) 1–28 — distinguished points, parallel rho and kangaroo.175* J. M. Pollard, *Kangaroos, Monopoly and discrete logarithms*, J. Cryptology 13 (2000) 437–447 — power-of-two jumps.176* M. J. Wiener, R. J. Zuccherato, *Faster attacks on elliptic curve cryptosystems*, SAC 1998, LNCS 1556 (1999) — negation map.177* R. Gallant, R. Lambert, S. Vanstone, *Improving the parallelized Pollard lambda search on anomalous binary178 curves*, Math. Comp. 69 (2000) 1699–1705 — automorphism classes.179* I. Duursma, P. Gaudry, F. Morain, *Speeding up the discrete log computation on curves with automorphisms*,180 ASIACRYPT 1999, LNCS 1716 — order-3/6 automorphisms, fruitless cycles.181* J. W. Bos, T. Kleinjung, A. K. Lenstra, *On the use of the negation map in the Pollard rho method*,182 ANTS-IX 2010, LNCS 6197 — look-ahead, cycle reduction.183* D. J. Bernstein, T. Lange, P. Schwabe, *On the correct use of the negation map in the Pollard rho method*,184 PKC 2011, LNCS 6571 — fruitless-cycle detection and escape by doubling the minimum point.185