1//! rho_engine — native ECDLP experimentation engine for WP34-UQO (synthetic instances, p < 2^62).2//!3//! Library entry point: [`run`] takes a [`SolveSpec`] (the CLI flags or one element of a batch file)4//! and returns the JSON result object documented in README.md.56pub mod bsgs;7pub mod curve;8pub mod field;9pub mod instance;10pub mod kangaroo;11pub mod rho;12pub mod stats;1314use serde::{Deserialize, Serialize};15use serde_json::{json, Value};16use std::time::Instant;1718/// One ECDLP job. Big integers are decimal strings so that the JSON stays exact.19#[derive(Clone, Debug, Serialize, Deserialize)]20pub struct SolveSpec {21 pub p: String,22 pub a: String,23 pub b: String,24 pub n: String,25 pub gx: String,26 pub gy: String,27 pub qx: String,28 pub qy: String,29 pub alg: String,30 #[serde(default = "default_seed")]31 pub seed: u64,32 #[serde(default)]33 pub label: Option<String>,34 #[serde(default)]35 pub expected_d: Option<String>,36 // rho37 #[serde(default = "default_r")]38 pub r: usize,39 #[serde(default)]40 pub cycle: Option<String>,41 #[serde(default)]42 pub dp: Option<u32>,43 #[serde(default = "default_one")]44 pub threads: usize,45 #[serde(default)]46 pub walks: Option<usize>,47 #[serde(default)]48 pub mixed: usize,49 #[serde(default)]50 pub neg: bool,51 #[serde(default)]52 pub aut3: bool,53 #[serde(default)]54 pub beta: Option<String>,55 #[serde(default)]56 pub lambda: Option<String>,57 #[serde(default = "default_cycle_check")]58 pub cycle_check: u64,59 #[serde(default)]60 pub max_walk_len: Option<u64>,61 // kangaroo62 #[serde(default)]63 pub lo: Option<String>,64 #[serde(default)]65 pub hi: Option<String>,66 // bsgs67 #[serde(default)]68 pub memory: Option<String>,69 #[serde(default = "default_chains")]70 pub chains: usize,71}7273fn default_seed() -> u64 {74 175}76fn default_r() -> usize {77 2078}79fn default_one() -> usize {80 181}82fn default_cycle_check() -> u64 {83 3284}85fn default_chains() -> usize {86 6487}8889fn parse_u64(name: &str, s: &str) -> Result<u64, String> {90 s.trim().parse::<u64>().map_err(|e| format!("{name}: cannot parse '{s}' as u64 ({e})"))91}9293/// Run one job and return the result JSON object (never panics on a bad spec: returns {"error": …}).94pub fn run(spec: &SolveSpec) -> Value {95 match run_inner(spec) {96 Ok(v) => v,97 Err(e) => json!({ "error": e, "ok": false, "label": spec.label, "params": serde_json::to_value(spec).unwrap_or(Value::Null) }),98 }99}100101fn run_inner(spec: &SolveSpec) -> Result<Value, String> {102 let t0 = Instant::now();103 let cpu0 = stats::process_cpu_s();104 let p = parse_u64("p", &spec.p)?;105 let a = parse_u64("a", &spec.a)?;106 let b = parse_u64("b", &spec.b)?;107 let n = parse_u64("n", &spec.n)?;108 let gx = parse_u64("gx", &spec.gx)?;109 let gy = parse_u64("gy", &spec.gy)?;110 let qx = parse_u64("qx", &spec.qx)?;111 let qy = parse_u64("qy", &spec.qy)?;112 if p >= (1u64 << 62) {113 return Err("p must be < 2^62".into());114 }115 if n >= (1u64 << 62) {116 return Err("n must be < 2^62".into());117 }118 let mut inst = instance::Instance::new(p, a, b, n, gx, gy, qx, qy)?;119 if spec.aut3 {120 let beta = parse_u64("beta", spec.beta.as_deref().ok_or("--aut3 requires --beta")?)?;121 let lambda = parse_u64("lambda", spec.lambda.as_deref().ok_or("--aut3 requires --lambda")?)?;122 inst = inst.with_aut3(beta, lambda)?;123 }124 let bits = inst.bits();125 let expected_d = spec.expected_d.as_deref().map(|s| parse_u64("expected_d", s)).transpose()?;126127 let (d, ok, mut out) = match spec.alg.as_str() {128 "bsgs" => {129 let memory = spec.memory.as_deref().map(|s| parse_u64("memory", s)).transpose()?;130 let cfg = bsgs::BsgsConfig { memory, threads: spec.threads.max(1), chains: spec.chains.max(1) };131 let res = bsgs::solve_bsgs(&inst, &cfg);132 let ok = res.d.map(|d| inst.verify(d, &mut curve::Counters::default())).unwrap_or(false);133 let out = json!({134 "ops": res.ops,135 "iterations": res.iterations,136 "dp_count": 0,137 "dp_bytes": 0,138 "fruitless_cycles": 0,139 "threads": res.threads,140 "cpu_s": res.cpu_s,141 "table_entries": res.table_entries,142 "table_bytes": res.table_bytes,143 "baby_steps": res.baby_steps.to_string(),144 "giant_steps_planned": res.giant_steps_planned.to_string(),145 "build_s": res.build_s,146 "params": { "alg": "bsgs", "memory": res.baby_steps.to_string(), "threads": res.threads, "chains": cfg.chains, "seed": spec.seed },147 });148 (res.d, ok, out)149 }150 "rho" => {151 let mode = match spec.cycle.as_deref().unwrap_or("dp") {152 "floyd" => rho::RhoMode::Floyd,153 "brent" => rho::RhoMode::Brent,154 "dp" => rho::RhoMode::Dp,155 other => return Err(format!("unknown --cycle '{other}' (floyd|brent|dp)")),156 };157 let dp_bits = spec.dp.unwrap_or_else(|| rho::RhoConfig::default_dp_bits(bits));158 if spec.r < 2 {159 return Err("--r must be ≥ 2".into());160 }161 if spec.mixed == 1 {162 return Err("--mixed k must be ≥ 2 (every k-th partition doubles)".into());163 }164 let cfg = rho::RhoConfig {165 r: spec.r,166 mixed: spec.mixed,167 neg: spec.neg,168 aut3: spec.aut3,169 cycle_check: spec.cycle_check.max(2),170 dp_bits,171 walks: spec.walks.unwrap_or(128).max(1),172 threads: spec.threads.max(1),173 mode,174 seed: spec.seed,175 max_walk_len: spec.max_walk_len.unwrap_or((64u64 << dp_bits.min(40)).max(1 << 16)),176 };177 let res = rho::solve_rho(&inst, &cfg);178 let ok = res.d.map(|d| inst.verify(d, &mut curve::Counters::default())).unwrap_or(false);179 let class = (if cfg.neg { 2 } else { 1 }) * (if cfg.aut3 { 3 } else { 1 });180 let out = json!({181 "ops": res.stats.ops,182 "iterations": res.stats.iterations,183 "dp_count": res.dp_count,184 "dp_bytes": res.dp_bytes,185 "fruitless_cycles": res.stats.fruitless_cycles,186 "fruitless_by_length": res.stats.fruitless_by_length.iter().enumerate().filter(|(_, c)| **c > 0).map(|(l, c)| json!({"length": l, "count": c})).collect::<Vec<_>>(),187 "lookahead_rejections": res.stats.lookahead_rejections,188 "doubling_fallbacks": res.stats.doubling_fallbacks,189 "abandoned_walks": res.stats.abandoned_walks,190 "restarts": res.stats.restarts,191 "useless_collisions": res.stats.useless_collisions,192 "threads": res.threads,193 "cpu_s": res.stats.cpu_s,194 "table_entries": res.table_entries,195 "expected_iterations": rho::expected_iterations(n, class),196 "class_size": class,197 "params": { "alg": "rho", "mode": cfg.mode, "r": cfg.r, "mixed": cfg.mixed, "neg": cfg.neg, "aut3": cfg.aut3, "dp": cfg.dp_bits, "walks": cfg.walks, "threads": cfg.threads, "cycle_check": cfg.cycle_check, "max_walk_len": cfg.max_walk_len, "seed": cfg.seed, "beta": spec.beta, "lambda": spec.lambda },198 });199 (res.d, ok, out)200 }201 "kangaroo" => {202 let lo = spec.lo.as_deref().map(|s| parse_u64("lo", s)).transpose()?.unwrap_or(0);203 let hi = spec.hi.as_deref().map(|s| parse_u64("hi", s)).transpose()?.unwrap_or(n - 1);204 if hi >= n || lo > hi {205 return Err("need 0 ≤ lo ≤ hi < n".into());206 }207 let cfg = kangaroo::KangarooConfig { lo, hi, threads: spec.threads.max(1), walks: spec.walks.unwrap_or(0), dp_bits: spec.dp.unwrap_or(0), seed: spec.seed };208 let res = kangaroo::solve_kangaroo(&inst, &cfg);209 let ok = res.d.map(|d| inst.verify(d, &mut curve::Counters::default())).unwrap_or(false);210 let out = json!({211 "ops": res.stats.ops,212 "iterations": res.stats.iterations,213 "dp_count": res.dp_count,214 "dp_bytes": res.dp_bytes,215 "fruitless_cycles": 0,216 "herd_collisions": res.stats.useless_collisions,217 "abandoned_walks": res.stats.abandoned_walks,218 "restarts": res.stats.restarts,219 "threads": res.threads,220 "cpu_s": res.stats.cpu_s,221 "table_entries": res.table_entries,222 "expected_iterations": 2.0 * (res.interval_width as f64).sqrt(),223 "params": { "alg": "kangaroo", "lo": lo.to_string(), "hi": hi.to_string(), "interval_width": res.interval_width.to_string(), "threads": res.threads, "kangaroos_per_thread": res.kangaroos_per_thread, "dp": res.dp_bits, "jump_count": res.jump_count, "mean_jump": res.mean_jump.to_string(), "seed": spec.seed },224 });225 (res.d, ok, out)226 }227 other => return Err(format!("unknown algorithm '{other}' (bsgs|rho|kangaroo)")),228 };229230 let obj = out.as_object_mut().unwrap();231 let wall = t0.elapsed().as_secs_f64();232 obj.insert("d".into(), d.map(|v| Value::String(v.to_string())).unwrap_or(Value::Null));233 obj.insert("ok".into(), Value::Bool(ok));234 obj.insert("wall_s".into(), json!(wall));235 obj.insert("process_cpu_s".into(), json!(stats::process_cpu_s() - cpu0));236 obj.insert("peak_rss_bytes".into(), json!(stats::peak_rss_bytes()));237 obj.insert("bits".into(), json!(bits));238 obj.insert("seed".into(), json!(spec.seed));239 obj.insert("label".into(), spec.label.clone().map(Value::String).unwrap_or(Value::Null));240 obj.insert("engine".into(), json!(format!("rho_engine {}", env!("CARGO_PKG_VERSION"))));241 let ops = obj.get("ops").cloned().unwrap_or(Value::Null);242 let group_ops = ops.get("add").and_then(|v| v.as_u64()).unwrap_or(0) + ops.get("dbl").and_then(|v| v.as_u64()).unwrap_or(0);243 let cpu = obj.get("cpu_s").and_then(|v| v.as_f64()).unwrap_or(0.0);244 obj.insert("group_ops".into(), json!(group_ops));245 obj.insert("group_ops_per_cpu_s".into(), json!(if cpu > 0.0 { group_ops as f64 / cpu } else { 0.0 }));246 obj.insert("group_ops_per_wall_s".into(), json!(if wall > 0.0 { group_ops as f64 / wall } else { 0.0 }));247 if let Some(e) = expected_d {248 obj.insert("expected_d".into(), Value::String(e.to_string()));249 obj.insert("match".into(), Value::Bool(d == Some(e % n)));250 }251 let instance = json!({ "p": spec.p, "a": spec.a, "b": spec.b, "n": spec.n, "gx": spec.gx, "gy": spec.gy, "qx": spec.qx, "qy": spec.qy });252 obj.get_mut("params").and_then(|v| v.as_object_mut()).map(|m| m.insert("instance".into(), instance));253 Ok(out)254}255