rusqsieve 0.3.0

#![cfg(any(unix, windows))]
use rusqsieve::{
    FactorConfig, FactorError, Natural, Parallelism, ProgressAction, ProgressPhase, factor,
    factor_with_progress,
};
use std::str::FromStr;

#[test]
fn factors_sorted_with_repetitions() {
    let n: Natural = Natural::from_u64(360);
    let factors = factor(n.clone()).unwrap();
    assert_eq!(
        factors
            .iter()
            .map(|(p, e)| (p.to_string(), e.get()))
            .collect::<Vec<_>>(),
        [("2".into(), 3), ("3".into(), 2), ("5".into(), 1)]
    );
    assert!(factors.verify_product(&n));
    assert_eq!(factors.distinct_len(), 3);
    assert_eq!(factors.total_len(), 6);
    assert_eq!(
        factors
            .expanded()
            .map(ToString::to_string)
            .collect::<Vec<_>>(),
        ["2", "2", "2", "3", "3", "5"]
    );
}

#[test]
fn zero_and_one() {
    let zero: Natural = Natural::ZERO;
    let one: Natural = Natural::ONE;
    assert!(matches!(
        factor(zero),
        Err(FactorError::ZeroHasNoPrimeFactorization)
    ));
    assert!(factor(one).unwrap().is_empty());
    for prime in [2u64, 3] {
        let input: Natural = Natural::from_u64(prime);
        let factors = factor(input.clone()).unwrap();
        assert_eq!(factors.total_len(), 1);
        assert!(factors.verify_product(&input));
    }
}

#[test]
fn widths_above_the_engine_capacity_use_the_real_siqs_path() {
    let input =
        Natural::<17>::from_decimal("18446744400127067027").expect("65-bit value fits 17 limbs");
    let factors = factor(input.clone()).unwrap();
    assert!(factors.verify_product(&input));
    assert_eq!(factors.distinct_len(), 2);
}

#[test]
fn perfect_power_and_recursive_multifactor_inputs() {
    let prime = Natural::<16>::from_decimal("170141183460469231731687303715884105727").unwrap();
    let square = prime.checked_mul(&prime).unwrap();
    let factors = factor(square.clone()).unwrap();
    assert!(factors.verify_product(&square));
    assert_eq!(factors.multiplicity(&prime).unwrap().get(), 2);

    let three_prime = Natural::<16>::from_decimal("10007000160112000630441").unwrap();
    // 10007 × 1000000007 × 1000000009
    let factors = factor(three_prime.clone()).unwrap();
    assert!(factors.verify_product(&three_prime));
    assert_eq!(factors.total_len(), 3);

    let odd = Natural::<16>::from_u64(1_000_003);
    let power_of_two_input = odd.clone() << 180;
    let factors = factor(power_of_two_input.clone()).unwrap();
    assert!(factors.verify_product(&power_of_two_input));
    assert_eq!(
        factors.multiplicity(&Natural::from_u64(2)).unwrap().get(),
        180
    );
    assert_eq!(factors.multiplicity(&odd).unwrap().get(), 1);
}

#[test]
fn configuration_is_validated_and_encapsulated() {
    assert_eq!(Parallelism::threads(0), None);
    let threads = Parallelism::threads(2).unwrap();
    let config = FactorConfig::default().with_parallelism(threads);
    assert_eq!(config.parallelism(), threads);
}

#[test]
fn progress_can_cancel_before_work_starts() {
    let input: Natural = Natural::from_u64(360);
    let result = factor_with_progress(input, FactorConfig::default(), |snapshot| {
        assert_eq!(snapshot.phase(), ProgressPhase::Preprocessing);
        ProgressAction::Cancel
    });
    assert!(matches!(result, Err(FactorError::Cancelled)));
}

#[test]
fn progress_finishes_with_a_complete_snapshot() {
    let mut phases = Vec::new();
    let input: Natural = Natural::from_u64(360);
    let factors = factor_with_progress(input, FactorConfig::default(), |snapshot| {
        phases.push(snapshot.phase());
        ProgressAction::Continue
    })
    .unwrap();
    assert_eq!(factors.total_len(), 6);
    assert_eq!(phases.first(), Some(&ProgressPhase::Preprocessing));
    assert_eq!(phases.last(), Some(&ProgressPhase::Complete));
}

#[test]
fn progress_cancellation_stops_parallel_sieving() {
    let p: Natural = Natural::from_u64(18_446_744_073_709_551_557);
    let q: Natural = Natural::from_u64(18_446_744_073_709_551_533);
    let input = p.checked_mul(&q).unwrap();
    let mut reached_sieving = false;
    let result = factor_with_progress(input, FactorConfig::default(), |snapshot| {
        if snapshot.phase() == ProgressPhase::Sieving {
            reached_sieving = true;
            ProgressAction::Cancel
        } else {
            ProgressAction::Continue
        }
    });
    assert!(reached_sieving);
    assert!(matches!(result, Err(FactorError::Cancelled)));
}

fn assert_factorization(input: &str, expected: &[&str]) {
    let n = Natural::<16>::from_str(input).unwrap();
    let factors = factor(n.clone()).unwrap_or_else(|error| panic!("failed to factor {n}: {error}"));
    assert!(
        factors.verify_product(&n),
        "factor product mismatch for {n}"
    );
    let actual = factors
        .expanded()
        .map(ToString::to_string)
        .collect::<Vec<_>>();
    assert_eq!(actual, expected, "prime factorization mismatch for {n}");

    // Each listed factor must itself terminate as one prime factor. This exercises
    // the library's final primality decision rather than merely trusting the product.
    for expected_prime in expected {
        let prime = Natural::<16>::from_str(expected_prime).unwrap();
        let prime_factors = factor(prime.clone()).unwrap();
        assert_eq!(
            prime_factors.total_len(),
            1,
            "{prime} was not accepted as prime"
        );
        assert!(prime_factors.verify_product(&prime));
    }
}

#[test]
fn balanced_semiprimes_across_the_choose_a_dead_zone() {
    let cases: &[(&str, &[&str])] = &[
        // Required minimum reproducer (65 bits).
        ("18446744400127067027", &["4294967311", "4294967357"]),
        ("27072011721716628587", &["4273765633", "6334463339"]),
        ("635904368119925963561", &["19860882047", "32017931863"]),
        ("20988451891514649258347", &["91807517561", "228613652227"]),
        (
            "703713894016303629914563",
            &["815250411389", "863187413567"],
        ),
        (
            "22921914745054882120472087",
            &["2921865453193", "7844959020959"],
        ),
        (
            "648536833001811612107041493",
            &["24295067057461", "26694177524513"],
        ),
    ];
    for &(n, expected) in cases {
        assert_factorization(n, expected);
    }
}

/// Every entry of the supplied corpus, parsed. The arity varies from 1 to 10, so the whole line is
/// read and no entry may be assumed to be a semiprime.
fn corpus_entries() -> Vec<(&'static str, Vec<&'static str>)> {
    let corpus = include_str!("data/rusqsieve-factorization-corpus.txt");
    let mut entries = Vec::new();
    for (line_index, line) in corpus.lines().enumerate() {
        let line = line.trim();
        if line.is_empty() || line.starts_with('#') {
            continue;
        }
        let fields = line.split_ascii_whitespace().collect::<Vec<_>>();
        assert!(
            fields.len() >= 2,
            "corpus line {} has no factorization",
            line_index + 1
        );
        entries.push((fields[0], fields[1..].to_vec()));
    }
    assert_eq!(entries.len(), 309, "unexpected corpus entry count");
    entries
}

#[test]
fn browser_tuning_corpus_has_exact_balanced_products() {
    let corpus = include_str!("data/browser-balanced-corpus.txt");
    let mut counts = [0usize; 6];
    for (line_index, line) in corpus.lines().enumerate() {
        let line = line.trim();
        if line.is_empty() || line.starts_with('#') {
            continue;
        }
        let fields = line.split_ascii_whitespace().collect::<Vec<_>>();
        assert_eq!(
            fields.len(),
            4,
            "bad browser corpus line {}",
            line_index + 1
        );
        let bits: usize = fields[0].parse().unwrap();
        let n = Natural::<16>::from_str(fields[1]).unwrap();
        let p = Natural::<16>::from_str(fields[2]).unwrap();
        let q = Natural::<16>::from_str(fields[3]).unwrap();
        assert_eq!(n.bit_len(), bits, "wrong width on line {}", line_index + 1);
        assert_eq!(p.bit_len(), bits / 2);
        assert_eq!(q.bit_len(), bits / 2);
        assert_eq!(p.checked_mul(&q).unwrap(), n);
        counts[match bits {
            216 => 0,
            224 => 1,
            232 => 2,
            240 => 3,
            256 => 4,
            272 => 5,
            _ => panic!("unexpected browser tier {bits}"),
        }] += 1;
    }
    assert_eq!(counts, [5, 5, 5, 5, 5, 5]);
}

/// Where the default corpus test stops and the `#[ignore]`d one picks up. Every one of the 117
/// entries in the 65-85-bit `choose_a` dead zone — the regression this corpus exists for — is below
/// it, with margin. Above it the entries are genuine SIQS work: a 256-bit factorization is tens of
/// seconds in a release build and minutes in the default unoptimized test profile, which would make
/// `cargo test` too slow to be run.
const DEFAULT_TIER_BITS: usize = 128;

/// The corpus through [`DEFAULT_TIER_BITS`]. Note this exercises the ladder's cheap stages, not the
/// sieve: since the Pollard-Brent stage was added, everything in this band splits before SIQS is
/// reached. The dead zone is pinned against the sieve itself by `engine`'s
/// `siqs_builds_polynomials_across_the_dead_zone` and `siqs_alone_factors_the_dead_zone`.
#[test]
fn supplied_factorization_corpus_through_128_bits() {
    let mut tested = 0usize;
    let mut in_dead_zone = 0usize;
    for (n, factors) in corpus_entries() {
        let bits = Natural::<16>::from_str(n).unwrap().bit_len();
        if bits > DEFAULT_TIER_BITS {
            continue;
        }
        assert_factorization(n, &factors);
        tested += 1;
        if (65..=85).contains(&bits) {
            in_dead_zone += 1;
        }
    }
    assert_eq!(
        in_dead_zone, 117,
        "the 65-85-bit regression band is not fully covered"
    );
    assert!(tested >= 270, "only {tested} entries ran");
}

/// The remaining corpus entries, up to 256 bits. Run with
/// `cargo test --profile release-test --test factorization -- --ignored`.
#[test]
#[ignore = "minutes of sieving; run in CI on a schedule"]
fn supplied_factorization_corpus_above_128_bits() {
    let mut tested = 0usize;
    for (n, factors) in corpus_entries() {
        if Natural::<16>::from_str(n).unwrap().bit_len() <= DEFAULT_TIER_BITS {
            continue;
        }
        assert_factorization(n, &factors);
        tested += 1;
    }
    assert_eq!(tested, 29, "unexpected large corpus entry count");
}

#[test]
#[ignore = "manual interleaved performance measurement"]
fn profile_single_input() {
    // `--ignored` runs this alongside the slow corpus tier, so an absent input is "nothing to
    // measure" rather than a failure.
    let Ok(input) = std::env::var("RUSQSIEVE_BENCH_INPUT") else {
        eprintln!("BENCH skipped: set RUSQSIEVE_BENCH_INPUT to a decimal integer");
        return;
    };
    let n = Natural::<16>::from_str(&input).unwrap();
    let repeats = std::env::var("RUSQSIEVE_BENCH_REPEATS")
        .ok()
        .and_then(|value| value.parse().ok())
        .unwrap_or(1);
    let started = std::time::Instant::now();
    for _ in 0..repeats {
        let factors = rusqsieve::factor_with(
            n.clone(),
            FactorConfig::default().with_parallelism(Parallelism::threads(4).unwrap()),
        )
        .unwrap();
        assert!(factors.verify_product(&n));
    }
    eprintln!(
        "BENCH input_bits={} repeats={} elapsed={:.6}s",
        n.bit_len(),
        repeats,
        started.elapsed().as_secs_f64()
    );
}