1//! Baby-step giant-step (Shanks 1971) with x-coordinate keys and ± lookup.2//!3//! Baby table: x(jG) → j for 0 < j < m (m = ⌈√n⌉ or --memory). Giant steps R_i = Q − i·(mG),4//! i = 0, 1, …, ⌈n/m⌉; a hit x(R_i) = x(jG) means R_i = ±jG, i.e. d = i·m ± j (both verified).5//! Both phases are chains advanced by a constant point, so m/S independent chains are advanced6//! together with Montgomery's simultaneous inversion (S = `chains`); the giant phase is split7//! across threads.89use crate::curve::{Counters, Pt};10use crate::instance::{isqrt_ceil, Instance};11use crate::stats::FxBuild;12use hashbrown::HashMap;13use serde::{Deserialize, Serialize};14use std::sync::atomic::{AtomicBool, Ordering};15use std::sync::Mutex;16use std::time::Instant;1718#[derive(Clone, Debug, Serialize, Deserialize)]19pub struct BsgsConfig {20 /// number of baby steps m (default ⌈√n⌉)21 pub memory: Option<u64>,22 pub threads: usize,23 /// independent chains per thread for batch inversion24 pub chains: usize,25}2627#[derive(Clone, Debug, Serialize, Deserialize)]28pub struct BsgsResult {29 pub d: Option<u64>,30 pub ops: Counters,31 /// giant steps actually computed (all threads)32 pub iterations: u64,33 pub baby_steps: u64,34 pub giant_steps_planned: u64,35 pub table_entries: u64,36 pub table_bytes: u64,37 pub threads: usize,38 pub wall_s: f64,39 pub cpu_s: f64,40 pub build_s: f64,41}4243/// Advance every chain by the constant point `s` (P_c ← P_c + s) with one batched inversion.44/// Chains at infinity or with x(P_c) = x(s) take the slow path.45fn advance_chains(inst: &Instance, pts: &mut [Pt], s: &Pt, dens: &mut [u64], scratch: &mut [u64], special: &mut [bool], c: &mut Counters) {46 let f = &inst.curve.f;47 let k = pts.len();48 for i in 0..k {49 let p = &pts[i];50 let sp = p.inf || p.x == s.x;51 special[i] = sp;52 dens[i] = if sp { f.one } else { f.sub(s.x, p.x) };53 }54 let (m, inv) = f.batch_inv(&mut dens[..k], &mut scratch[..k]);55 c.mul += m;56 c.inv += inv;57 for i in 0..k {58 if special[i] {59 pts[i] = inst.curve.add(&pts[i], s, c);60 } else {61 let lam = f.mul(f.sub(s.y, pts[i].y), dens[i]);62 pts[i] = inst.curve.finish_add(&pts[i], s.x, lam);63 c.add += 1;64 c.mul += 3;65 }66 }67}6869pub fn solve_bsgs(inst: &Instance, cfg: &BsgsConfig) -> BsgsResult {70 let t0 = Instant::now();71 let cpu0 = crate::stats::thread_cpu_s();72 let n = inst.n.n;73 let mut c = Counters::default();74 let m = cfg.memory.unwrap_or(isqrt_ceil(n as u128) as u64).max(1).min(n);75 let t_total = (n as u128).div_ceil(m as u128) as u64 + 1;76 let threads = cfg.threads.max(1);77 let empty = |d: Option<u64>, c: Counters, t0: Instant, cpu0: f64| BsgsResult {78 d,79 ops: c,80 iterations: 0,81 baby_steps: m,82 giant_steps_planned: t_total,83 table_entries: 0,84 table_bytes: 0,85 threads,86 wall_s: t0.elapsed().as_secs_f64(),87 cpu_s: crate::stats::thread_cpu_s() - cpu0,88 build_s: 0.0,89 };90 if inst.q.inf {91 return empty(Some(0), c, t0, cpu0);92 }9394 // ---- baby steps --------------------------------------------------------------------------95 let s = cfg.chains.max(1).min(m as usize);96 let len = (m as usize).div_ceil(s);97 let mut table: HashMap<u64, u64, FxBuild> = HashMap::with_capacity_and_hasher(m as usize + 1, Default::default());98 let mut pts: Vec<Pt> = (0..s).map(|ci| inst.curve.mul((ci * len) as u64, &inst.g, &mut c)).collect();99 let mut dens = vec![0u64; s];100 let mut scratch = vec![0u64; s];101 let mut special = vec![false; s];102 for step in 0..len {103 let mut active = 0;104 for ci in 0..s {105 let j = (ci * len + step) as u64;106 if j >= m {107 break;108 }109 active = ci + 1;110 if !pts[ci].inf {111 table.entry(pts[ci].x).or_insert(j);112 }113 }114 if active == 0 {115 break;116 }117 if step + 1 < len {118 advance_chains(inst, &mut pts[..active], &inst.g, &mut dens, &mut scratch, &mut special, &mut c);119 }120 }121 let build_s = t0.elapsed().as_secs_f64();122 let table_entries = table.len() as u64;123 let table_bytes = table.capacity() as u64 * (std::mem::size_of::<(u64, u64)>() as u64 + 1);124125 // ---- giant steps (threaded) ---------------------------------------------------------------126 let mg = inst.curve.mul(m, &inst.g, &mut c);127 let neg_mg = inst.curve.neg(&mg);128 let found: Mutex<Option<u64>> = Mutex::new(None);129 let stop = AtomicBool::new(false);130 let per: Mutex<Vec<(Counters, u64, f64)>> = Mutex::new(Vec::new());131 let table = &table;132 let block = (t_total as usize).div_ceil(threads);133 std::thread::scope(|sc| {134 for t in 0..threads {135 let found = &found;136 let stop = &stop;137 let per = &per;138 let i_begin = (t * block) as u64;139 let i_end = (((t + 1) * block) as u64).min(t_total);140 if i_begin >= i_end {141 continue;142 }143 sc.spawn(move || {144 let cpu0 = crate::stats::thread_cpu_s();145 let mut c = Counters::default();146 let count = (i_end - i_begin) as usize;147 let s = cfg.chains.max(1).min(count);148 let len = count.div_ceil(s);149 // chain ci starts at R_{i_begin + ci·len} = Q − (i_begin + ci·len)·mG150 let mut pts: Vec<Pt> = (0..s)151 .map(|ci| {152 let i0 = i_begin + (ci * len) as u64;153 let off = inst.curve.mul(i0 % n, &neg_mg, &mut c);154 inst.curve.add(&inst.q, &off, &mut c)155 })156 .collect();157 let mut dens = vec![0u64; s];158 let mut scratch = vec![0u64; s];159 let mut special = vec![false; s];160 let mut iters = 0u64;161 let mut solved: Option<u64> = None;162 'outer: for step in 0..len {163 if stop.load(Ordering::Relaxed) {164 break;165 }166 let mut active = 0;167 for ci in 0..s {168 let i = i_begin + (ci * len + step) as u64;169 if i >= i_end {170 break;171 }172 active = ci + 1;173 iters += 1;174 let r = pts[ci];175 if r.inf {176 // Q = i·m·G177 let d = inst.n.mul(i % n, m % n);178 if inst.verify(d, &mut c) {179 solved = Some(d);180 break 'outer;181 }182 continue;183 }184 if let Some(&j) = table.get(&r.x) {185 let im = inst.n.mul(i % n, m % n);186 for d in [inst.n.add(im, j % n), inst.n.sub(im, j % n)] {187 if inst.verify(d, &mut c) {188 solved = Some(d);189 break 'outer;190 }191 }192 }193 }194 if active == 0 {195 break;196 }197 if step + 1 < len {198 advance_chains(inst, &mut pts[..active], &neg_mg, &mut dens, &mut scratch, &mut special, &mut c);199 }200 }201 if let Some(d) = solved {202 let mut f = found.lock().unwrap();203 if f.is_none() {204 *f = Some(d);205 }206 stop.store(true, Ordering::Relaxed);207 }208 per.lock().unwrap().push((c, iters, crate::stats::thread_cpu_s() - cpu0));209 });210 }211 });212 let mut iterations = 0u64;213 let mut cpu_s = crate::stats::thread_cpu_s() - cpu0;214 for (pc, it, cpu) in per.lock().unwrap().iter() {215 c.merge(pc);216 iterations += it;217 cpu_s += cpu;218 }219 let d = *found.lock().unwrap();220 BsgsResult {221 d,222 ops: c,223 iterations,224 baby_steps: m,225 giant_steps_planned: t_total,226 table_entries,227 table_bytes,228 threads,229 wall_s: t0.elapsed().as_secs_f64(),230 cpu_s,231 build_s,232 }233}234