//! (a) Tiny curves: enumerate the group by naive point counting, brute-force every discrete log,
//! and check that every algorithm/option combination returns it.

use rho_engine::bsgs::{solve_bsgs, BsgsConfig};
use rho_engine::curve::{Counters, Curve, Pt};
use rho_engine::field::Field;
use rho_engine::instance::Instance;
use rho_engine::kangaroo::{solve_kangaroo, KangarooConfig};
use rho_engine::rho::{solve_rho, RhoConfig, RhoMode};

fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    let mut d = 2;
    while d * d <= n {
        if n % d == 0 {
            return false;
        }
        d += 1;
    }
    true
}

/// #E(F_p) by Legendre symbols (p tiny).
fn count_points(p: u64, a: u64, b: u64) -> u64 {
    let f = Field::new(p);
    let mut total = 1;
    for x in 0..p {
        let rhs = (((x * x % p) * x % p) + a * x % p + b) % p;
        if rhs == 0 {
            total += 1;
        } else if f.legendre(rhs) == 1 {
            total += 2;
        }
    }
    total
}

/// Deterministic list of small prime-order curves: (p, a, b, n, G).
fn small_prime_order_curves() -> Vec<(u64, u64, u64, u64, (u64, u64))> {
    let mut out = Vec::new();
    let mut seed = 12345u64;
    let mut next = || {
        seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        seed >> 33
    };
    for &p in &[101u64, 211, 503, 1009, 2003, 4099, 8191, 16411, 32771] {
        let mut found = 0;
        let mut tries = 0;
        while found < 2 && tries < 5000 {
            tries += 1;
            let a = next() % p;
            let b = next() % p;
            if (4 * a * a % p * a + 27 * b * b) % p == 0 {
                continue;
            }
            let n = count_points(p, a, b);
            if !is_prime(n) || n == p {
                continue;
            }
            let curve = Curve::new(p, a, b);
            let f = &curve.f;
            // find a point
            let mut g = None;
            for x in 0..p {
                let rhs = (((x * x % p) * x % p) + a * x % p + b) % p;
                if let Some(y) = f.sqrt_plain(rhs) {
                    g = Some((x, y));
                    break;
                }
            }
            let g = g.unwrap();
            out.push((p, a, b, n, g));
            found += 1;
        }
    }
    assert!(out.len() >= 12, "expected enough small curves, got {}", out.len());
    out
}

#[test]
fn small_curves_all_algorithms_brute_force() {
    let curves = small_prime_order_curves();
    let mut checked = 0usize;
    for (p, a, b, n, (gx, gy)) in curves {
        let curve = Curve::new(p, a, b);
        let g = curve.point_from_std(gx, gy);
        let mut c = Counters::default();
        // brute-force table of all multiples
        let mut mults: Vec<Pt> = Vec::with_capacity(n as usize);
        let mut r = Pt::INF;
        for _ in 0..n {
            mults.push(r);
            r = curve.add(&r, &g, &mut c);
        }
        assert!(r.inf, "n·G must be O");
        // sample of d values: all for n ≤ 300, otherwise 25 spread values + extremes
        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() };
        for d in ds {
            let q = mults[d as usize];
            let (qx, qy) = curve.point_to_std(&q).unwrap();
            let inst = Instance::new(p, a, b, n, gx, gy, qx, qy).unwrap();
            // BSGS, default and reduced memory, 1 and 2 threads
            let verbose = std::env::var("RHO_TEST_VERBOSE").is_ok();
            for (mem, th) in [(None, 1), (Some(3), 2), (Some(1), 1)] {
                if verbose { eprintln!("bsgs p={p} n={n} d={d} mem={mem:?} th={th}"); }
                let res = solve_bsgs(&inst, &BsgsConfig { memory: mem, threads: th, chains: 4 });
                assert_eq!(res.d, Some(d), "bsgs p={p} n={n} d={d} mem={mem:?} threads={th}");
            }
            // rho: floyd, brent, dp (1 and 2 threads), with neg, mixed
            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 };
            let variants = vec![
                RhoConfig { ..base.clone() },
                RhoConfig { mode: RhoMode::Brent, ..base.clone() },
                RhoConfig { mode: RhoMode::Dp, ..base.clone() },
                RhoConfig { mode: RhoMode::Dp, threads: 2, ..base.clone() },
                RhoConfig { mode: RhoMode::Dp, neg: true, ..base.clone() },
                RhoConfig { mode: RhoMode::Brent, neg: true, r: 3, ..base.clone() },
                RhoConfig { mode: RhoMode::Floyd, neg: true, mixed: 2, ..base.clone() },
                RhoConfig { mode: RhoMode::Dp, mixed: 3, ..base.clone() },
            ];
            for cfg in variants {
                if verbose { eprintln!("rho p={p} n={n} d={d} {:?} neg={} mixed={} th={}", cfg.mode, cfg.neg, cfg.mixed, cfg.threads); }
                let res = solve_rho(&inst, &cfg);
                assert_eq!(res.d, Some(d), "rho p={p} n={n} d={d} cfg={cfg:?}");
            }
            // kangaroo: full interval, and a tight interval around d
            let lo = d.saturating_sub(7);
            let hi = (d + 9).min(n - 1);
            for (lo, hi, th) in [(0, n - 1, 1), (lo, hi, 1), (0, n - 1, 2)] {
                if verbose { eprintln!("kangaroo p={p} n={n} d={d} [{lo},{hi}] th={th}"); }
                let res = solve_kangaroo(&inst, &KangarooConfig { lo, hi, threads: th, walks: 0, dp_bits: 1, seed: d });
                assert_eq!(res.d, Some(d), "kangaroo p={p} n={n} d={d} [{lo},{hi}] threads={th}");
            }
            checked += 1;
        }
    }
    eprintln!("small curves: {checked} (curve, d) pairs checked");
    assert!(checked > 200);
}

#[test]
fn group_law_matches_naive_scalar_multiplication() {
    // cross-check batch-free add/dbl against repeated addition on a mid-size curve
    let (p, a, b) = (1_000_003u64, 5u64, 7u64);
    let curve = Curve::new(p, a, b);
    let f = &curve.f;
    let mut g = None;
    for x in 1..p {
        let rhs = (((x * x % p) * x % p) + a * x % p + b) % p;
        if let Some(y) = f.sqrt_plain(rhs) {
            g = Some(curve.point_from_std(x, y));
            break;
        }
    }
    let g = g.unwrap();
    assert!(curve.is_on_curve(&g));
    let mut c = Counters::default();
    let mut r = Pt::INF;
    for k in 0..500u64 {
        assert!(curve.eq(&r, &curve.mul(k, &g, &mut c)), "k={k}");
        assert!(curve.is_on_curve(&r));
        r = curve.add(&r, &g, &mut c);
    }
    let d2 = curve.dbl(&g, &mut c);
    assert!(curve.eq(&d2, &curve.add(&g, &g, &mut c)));
    assert!(curve.add(&g, &curve.neg(&g), &mut c).inf);
}