1//! Pollard's kangaroo (lambda) method for d ∈ [lo, hi], in the van Oorschot–Wiener parallel form2//! with tame/wild herds and distinguished points (Pollard 2000 for the power-of-two jump set).3//!4//! Tame kangaroo c starts at position t_c = lo + ⌊w/2⌋ + c·s (point t_c·G); wild kangaroo c starts5//! at offset o_c = c·s (point Q + o_c·G); s = ⌈mean jump / (N/2)⌉ with N kangaroos in total.6//! Jump set J = {2^0 G, …, 2^{k−1} G}, j = h(x) ∈ [0, k), k chosen so that (2^k − 1)/k ≈ N·√w/47//! (which is √w/2 for the classical single tame/wild pair). Every kangaroo keeps its position mod n;8//! a tame/wild distinguished-point collision with positions (t, o) gives d = t − o (same y) or9//! d = −t − o (opposite y). Same-herd collisions reposition the newcomer by a random jump.1011use crate::curve::{CombTable, Counters, Pt};12use crate::instance::{is_distinguished, isqrt, partition, Instance};13use crate::rho::{RhoConfig, WalkStats};14use crate::stats::FxBuild;15use hashbrown::HashMap;16use rand::{Rng, SeedableRng};17use rand_chacha::ChaCha20Rng;18use serde::{Deserialize, Serialize};19use std::sync::atomic::{AtomicBool, Ordering};20use std::sync::Mutex;21use std::time::Instant;2223#[derive(Clone, Debug, Serialize, Deserialize)]24pub struct KangarooConfig {25 pub lo: u64,26 pub hi: u64,27 pub threads: usize,28 /// kangaroos per thread (0 = automatic, even number, half tame / half wild)29 pub walks: usize,30 /// 0 = automatic31 pub dp_bits: u32,32 pub seed: u64,33}3435#[derive(Clone, Debug, Serialize, Deserialize)]36pub struct KangarooResult {37 pub d: Option<u64>,38 pub stats: WalkStats,39 pub dp_count: u64,40 pub dp_bytes: u64,41 pub table_entries: u64,42 pub threads: usize,43 pub kangaroos_per_thread: usize,44 pub dp_bits: u32,45 pub jump_count: u32,46 pub mean_jump: u64,47 pub interval_width: u64,48 pub wall_s: f64,49}5051#[derive(Clone, Copy)]52struct Roo {53 p: Pt,54 dist: u64,55 tame: bool,56 /// total distance jumped since the last (re)start; a kangaroo that travels much further than57 /// the interval width has lost its herd and is restarted at a fresh random position58 travel: u128,59}6061#[derive(Clone, Copy)]62struct DpEntry {63 y: u64,64 dist: u64,65 tame: bool,66}6768pub fn auto_kangaroos(w: u64) -> usize {69 let bits = 64 - w.leading_zeros();70 let k = 1usize << (bits / 4).saturating_sub(2).min(6);71 k.clamp(2, 64).next_multiple_of(2)72}7374/// Pick k with (2^k − 1)/k closest to `target`.75pub fn choose_jump_count(target: u64) -> u32 {76 let mut best = 1u32;77 let mut best_err = u128::MAX;78 for k in 1..=62u32 {79 let mean = (((1u128 << k) - 1) / k as u128) as u128;80 let err = mean.abs_diff(target as u128);81 if err < best_err {82 best_err = err;83 best = k;84 }85 }86 best87}8889pub fn solve_kangaroo(inst: &Instance, cfg: &KangarooConfig) -> KangarooResult {90 let t0 = Instant::now();91 let n = inst.n.n;92 assert!(cfg.lo <= cfg.hi, "lo must be ≤ hi");93 let w = cfg.hi - cfg.lo + 1;94 let wbits = 64 - w.leading_zeros();95 let threads = cfg.threads.max(1);96 let per_thread = if cfg.walks == 0 { auto_kangaroos(w) } else { cfg.walks.max(2).next_multiple_of(2) };97 let total_roos = (threads * per_thread) as u64;98 let dp_bits = if cfg.dp_bits == 0 { RhoConfig::default_dp_bits(wbits) } else { cfg.dp_bits };99 let dp_mask = (1u64 << dp_bits.min(63)) - 1;100 let sqrt_w = isqrt(w as u128) as u64;101 let target_mean = (total_roos * sqrt_w / 4).max(1);102 let k = choose_jump_count(target_mean);103 let mean_jump = (((1u128 << k) - 1) / k as u128) as u64;104 let spacing = (mean_jump / (total_roos / 2)).max(1);105106 let mut setup = Counters::default();107 let comb_g = CombTable::new(&inst.curve, &inst.g, &mut setup);108 let jumps: Vec<Pt> = (0..k).map(|i| comb_g.mul(&inst.curve, (1u64 << i) % n, &mut setup)).collect();109 let mut total = WalkStats { fruitless_by_length: vec![], ..Default::default() };110 total.ops.merge(&setup);111112 if inst.q.inf {113 return KangarooResult { d: Some(0), stats: total, dp_count: 0, dp_bytes: 0, table_entries: 0, threads, kangaroos_per_thread: per_thread, dp_bits, jump_count: k, mean_jump, interval_width: w, wall_s: t0.elapsed().as_secs_f64() };114 }115116 let expected_dps = 2.0 * (w as f64).sqrt() / (1u64 << dp_bits.min(63)) as f64;117 let table: Mutex<HashMap<u64, DpEntry, FxBuild>> = Mutex::new(HashMap::with_capacity_and_hasher((expected_dps * 3.0) as usize + 1024, Default::default()));118 let found: Mutex<Option<u64>> = Mutex::new(None);119 let stop = AtomicBool::new(false);120 let stats: Mutex<Vec<WalkStats>> = Mutex::new(Vec::new());121 let mid = cfg.lo + w / 2;122 let jumps = &jumps;123 let comb_g = &comb_g;124125 std::thread::scope(|s| {126 for t in 0..threads {127 let table = &table;128 let found = &found;129 let stop = &stop;130 let stats = &stats;131 s.spawn(move || {132 let cpu0 = crate::stats::thread_cpu_s();133 let mut seed = [0u8; 32];134 seed[..8].copy_from_slice(&cfg.seed.to_le_bytes());135 seed[8..16].copy_from_slice(&(t as u64).to_le_bytes());136 seed[16..24].copy_from_slice(b"kangaroo");137 let mut rng = ChaCha20Rng::from_seed(seed);138 let mut st = WalkStats { fruitless_by_length: vec![], ..Default::default() };139 let f = &inst.curve.f;140 let curve = &inst.curve;141 let half = per_thread / 2;142 let mut roos: Vec<Roo> = Vec::with_capacity(per_thread);143 let mut solved: Option<u64> = None;144 let start = |st: &mut WalkStats, tame: bool, dist: u64| -> Roo {145 let base = comb_g.mul(curve, dist % n, &mut st.ops);146 let p = if tame { base } else { curve.add(&inst.q, &base, &mut st.ops) };147 Roo { p, dist: dist % n, tame, travel: 0 }148 };149 // random fresh start for a lost / merged kangaroo150 let fresh = |st: &mut WalkStats, rng: &mut ChaCha20Rng, tame: bool| -> Roo {151 let off = rng.random_range(0..w);152 let dist = if tame { (cfg.lo as u128 + off as u128) % n as u128 } else { off as u128 % n as u128 } as u64;153 st.restarts += 1;154 start(st, tame, dist)155 };156 let max_travel: u128 = 3 * w as u128 + 4 * (mean_jump as u128) * (1u128 << dp_bits.min(40));157 for c in 0..per_thread {158 let gc = (t * half + c % half) as u64;159 let tame = c < half;160 let dist = if tame { (mid as u128 + gc as u128 * spacing as u128) % n as u128 } else { (gc as u128 * spacing as u128) % n as u128 } as u64;161 let r = start(&mut st, tame, dist);162 if r.p.inf {163 // wild: Q = −dist·G ⇒ d = −dist ; tame: dist ≡ 0 — harmless, re-seed164 if !tame {165 let d = inst.n.neg(r.dist);166 if inst.verify(d, &mut st.ops) {167 solved = Some(d);168 }169 }170 let fr = fresh(&mut st, &mut rng, tame);171 roos.push(fr);172 } else {173 roos.push(r);174 }175 }176 let mut dens = vec![0u64; per_thread];177 let mut scratch = vec![0u64; per_thread];178 let mut js = vec![0u32; per_thread];179 let mut special = vec![false; per_thread];180 let mut dps: Vec<(u64, DpEntry)> = Vec::new();181 'main: while solved.is_none() && !stop.load(Ordering::Relaxed) {182 for i in 0..per_thread {183 let j = partition(roos[i].p.x, k as u64);184 js[i] = j;185 let jp = &jumps[j as usize];186 let sp = roos[i].p.inf || roos[i].p.x == jp.x;187 special[i] = sp;188 dens[i] = if sp { f.one } else { f.sub(jp.x, roos[i].p.x) };189 }190 let (m, inv) = f.batch_inv(&mut dens[..per_thread], &mut scratch[..per_thread]);191 st.ops.mul += m;192 st.ops.inv += inv;193 for i in 0..per_thread {194 let j = js[i] as usize;195 let jp = jumps[j];196 let jd = (1u64 << j) % n;197 let r = &mut roos[i];198 if special[i] {199 // P = ±2^j G200 if !r.tame {201 // Q + o·G = ±2^j·G ⇒ d = ±2^j − o202 for d in [inst.n.sub(jd, r.dist), inst.n.sub(inst.n.neg(jd), r.dist)] {203 if inst.verify(d, &mut st.ops) {204 solved = Some(d);205 break 'main;206 }207 }208 }209 let np = curve.add(&r.p, &jp, &mut st.ops);210 st.iterations += 1;211 if np.inf {212 *r = fresh(&mut st, &mut rng, r.tame);213 } else {214 r.p = np;215 r.dist = inst.n.add(r.dist, jd);216 r.travel += 1u128 << j;217 }218 } else {219 let lam = f.mul(f.sub(jp.y, r.p.y), dens[i]);220 r.p = curve.finish_add(&r.p, jp.x, lam);221 r.dist = inst.n.add(r.dist, jd);222 r.travel += 1u128 << j;223 st.ops.add += 1;224 st.ops.mul += 3;225 st.iterations += 1;226 }227 if r.travel > max_travel {228 st.abandoned_walks += 1;229 *r = fresh(&mut st, &mut rng, r.tame);230 continue;231 }232 if is_distinguished(r.p.x, dp_mask) {233 st.dp_found += 1;234 dps.push((r.p.x, DpEntry { y: r.p.y, dist: r.dist, tame: r.tame }));235 }236 }237 if !dps.is_empty() {238 let mut tab = table.lock().unwrap();239 for (x, e) in dps.drain(..) {240 match tab.get(&x) {241 None => {242 tab.insert(x, e);243 }244 Some(old) => {245 let old = *old;246 if old.tame == e.tame {247 if old.dist != e.dist {248 // merged trails inside one herd: reposition the newcomer249 st.useless_collisions += 1;250 if let Some(r) = roos.iter_mut().find(|r| r.p.x == x && r.tame == e.tame) {251 *r = fresh(&mut st, &mut rng, r.tame);252 }253 }254 continue;255 }256 let (tame_d, wild_d) = if old.tame { (old.dist, e.dist) } else { (e.dist, old.dist) };257 let cand = if old.y == e.y { inst.n.sub(tame_d, wild_d) } else { inst.n.sub(inst.n.neg(tame_d), wild_d) };258 if inst.verify(cand, &mut st.ops) {259 solved = Some(cand);260 break;261 }262 st.useless_collisions += 1;263 }264 }265 }266 }267 }268 if let Some(d) = solved {269 let mut fd = found.lock().unwrap();270 if fd.is_none() {271 *fd = Some(d);272 }273 stop.store(true, Ordering::Relaxed);274 }275 st.cpu_s = crate::stats::thread_cpu_s() - cpu0;276 stats.lock().unwrap().push(st);277 });278 }279 });280 for st in stats.lock().unwrap().iter() {281 total.merge(st);282 }283 let tab = table.lock().unwrap();284 let entries = tab.len() as u64;285 let bytes = tab.capacity() as u64 * (std::mem::size_of::<(u64, DpEntry)>() as u64 + 1);286 let d = *found.lock().unwrap();287 KangarooResult { d, stats: total, dp_count: entries, dp_bytes: bytes, table_entries: entries, threads, kangaroos_per_thread: per_thread, dp_bits, jump_count: k, mean_jump, interval_width: w, wall_s: t0.elapsed().as_secs_f64() }288}289