1//! (a) Tiny curves: enumerate the group by naive point counting, brute-force every discrete log,2//! and check that every algorithm/option combination returns it.34use rho_engine::bsgs::{solve_bsgs, BsgsConfig};5use rho_engine::curve::{Counters, Curve, Pt};6use rho_engine::field::Field;7use rho_engine::instance::Instance;8use rho_engine::kangaroo::{solve_kangaroo, KangarooConfig};9use rho_engine::rho::{solve_rho, RhoConfig, RhoMode};1011fn is_prime(n: u64) -> bool {12 if n < 2 {13 return false;14 }15 let mut d = 2;16 while d * d <= n {17 if n % d == 0 {18 return false;19 }20 d += 1;21 }22 true23}2425/// #E(F_p) by Legendre symbols (p tiny).26fn count_points(p: u64, a: u64, b: u64) -> u64 {27 let f = Field::new(p);28 let mut total = 1;29 for x in 0..p {30 let rhs = (((x * x % p) * x % p) + a * x % p + b) % p;31 if rhs == 0 {32 total += 1;33 } else if f.legendre(rhs) == 1 {34 total += 2;35 }36 }37 total38}3940/// Deterministic list of small prime-order curves: (p, a, b, n, G).41fn small_prime_order_curves() -> Vec<(u64, u64, u64, u64, (u64, u64))> {42 let mut out = Vec::new();43 let mut seed = 12345u64;44 let mut next = || {45 seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);46 seed >> 3347 };48 for &p in &[101u64, 211, 503, 1009, 2003, 4099, 8191, 16411, 32771] {49 let mut found = 0;50 let mut tries = 0;51 while found < 2 && tries < 5000 {52 tries += 1;53 let a = next() % p;54 let b = next() % p;55 if (4 * a * a % p * a + 27 * b * b) % p == 0 {56 continue;57 }58 let n = count_points(p, a, b);59 if !is_prime(n) || n == p {60 continue;61 }62 let curve = Curve::new(p, a, b);63 let f = &curve.f;64 // find a point65 let mut g = None;66 for x in 0..p {67 let rhs = (((x * x % p) * x % p) + a * x % p + b) % p;68 if let Some(y) = f.sqrt_plain(rhs) {69 g = Some((x, y));70 break;71 }72 }73 let g = g.unwrap();74 out.push((p, a, b, n, g));75 found += 1;76 }77 }78 assert!(out.len() >= 12, "expected enough small curves, got {}", out.len());79 out80}8182#[test]83fn small_curves_all_algorithms_brute_force() {84 let curves = small_prime_order_curves();85 let mut checked = 0usize;86 for (p, a, b, n, (gx, gy)) in curves {87 let curve = Curve::new(p, a, b);88 let g = curve.point_from_std(gx, gy);89 let mut c = Counters::default();90 // brute-force table of all multiples91 let mut mults: Vec<Pt> = Vec::with_capacity(n as usize);92 let mut r = Pt::INF;93 for _ in 0..n {94 mults.push(r);95 r = curve.add(&r, &g, &mut c);96 }97 assert!(r.inf, "n·G must be O");98 // sample of d values: all for n ≤ 300, otherwise 25 spread values + extremes99 let ds: Vec<u64> = if n <= 300 { (1..n).collect() } else { (0..25).map(|i| 1 + i * (n - 2) / 24).chain([1, 2, n - 1, n - 2, (n + 1) / 2]).collect() };100 for d in ds {101 let q = mults[d as usize];102 let (qx, qy) = curve.point_to_std(&q).unwrap();103 let inst = Instance::new(p, a, b, n, gx, gy, qx, qy).unwrap();104 // BSGS, default and reduced memory, 1 and 2 threads105 let verbose = std::env::var("RHO_TEST_VERBOSE").is_ok();106 for (mem, th) in [(None, 1), (Some(3), 2), (Some(1), 1)] {107 if verbose { eprintln!("bsgs p={p} n={n} d={d} mem={mem:?} th={th}"); }108 let res = solve_bsgs(&inst, &BsgsConfig { memory: mem, threads: th, chains: 4 });109 assert_eq!(res.d, Some(d), "bsgs p={p} n={n} d={d} mem={mem:?} threads={th}");110 }111 // rho: floyd, brent, dp (1 and 2 threads), with neg, mixed112 let base = RhoConfig { r: 8, mixed: 0, neg: false, aut3: false, cycle_check: 8, dp_bits: 1, walks: 4, threads: 1, mode: RhoMode::Floyd, seed: d ^ p, max_walk_len: 1 << 12 };113 let variants = vec![114 RhoConfig { ..base.clone() },115 RhoConfig { mode: RhoMode::Brent, ..base.clone() },116 RhoConfig { mode: RhoMode::Dp, ..base.clone() },117 RhoConfig { mode: RhoMode::Dp, threads: 2, ..base.clone() },118 RhoConfig { mode: RhoMode::Dp, neg: true, ..base.clone() },119 RhoConfig { mode: RhoMode::Brent, neg: true, r: 3, ..base.clone() },120 RhoConfig { mode: RhoMode::Floyd, neg: true, mixed: 2, ..base.clone() },121 RhoConfig { mode: RhoMode::Dp, mixed: 3, ..base.clone() },122 ];123 for cfg in variants {124 if verbose { eprintln!("rho p={p} n={n} d={d} {:?} neg={} mixed={} th={}", cfg.mode, cfg.neg, cfg.mixed, cfg.threads); }125 let res = solve_rho(&inst, &cfg);126 assert_eq!(res.d, Some(d), "rho p={p} n={n} d={d} cfg={cfg:?}");127 }128 // kangaroo: full interval, and a tight interval around d129 let lo = d.saturating_sub(7);130 let hi = (d + 9).min(n - 1);131 for (lo, hi, th) in [(0, n - 1, 1), (lo, hi, 1), (0, n - 1, 2)] {132 if verbose { eprintln!("kangaroo p={p} n={n} d={d} [{lo},{hi}] th={th}"); }133 let res = solve_kangaroo(&inst, &KangarooConfig { lo, hi, threads: th, walks: 0, dp_bits: 1, seed: d });134 assert_eq!(res.d, Some(d), "kangaroo p={p} n={n} d={d} [{lo},{hi}] threads={th}");135 }136 checked += 1;137 }138 }139 eprintln!("small curves: {checked} (curve, d) pairs checked");140 assert!(checked > 200);141}142143#[test]144fn group_law_matches_naive_scalar_multiplication() {145 // cross-check batch-free add/dbl against repeated addition on a mid-size curve146 let (p, a, b) = (1_000_003u64, 5u64, 7u64);147 let curve = Curve::new(p, a, b);148 let f = &curve.f;149 let mut g = None;150 for x in 1..p {151 let rhs = (((x * x % p) * x % p) + a * x % p + b) % p;152 if let Some(y) = f.sqrt_plain(rhs) {153 g = Some(curve.point_from_std(x, y));154 break;155 }156 }157 let g = g.unwrap();158 assert!(curve.is_on_curve(&g));159 let mut c = Counters::default();160 let mut r = Pt::INF;161 for k in 0..500u64 {162 assert!(curve.eq(&r, &curve.mul(k, &g, &mut c)), "k={k}");163 assert!(curve.is_on_curve(&r));164 r = curve.add(&r, &g, &mut c);165 }166 let d2 = curve.dbl(&g, &mut c);167 assert!(curve.eq(&d2, &curve.add(&g, &g, &mut c)));168 assert!(curve.add(&g, &curve.neg(&g), &mut c).inf);169}170