# 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):

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