adele_ring/
bounds.rs

1//! A-priori height bounds (in bits) used to provision an adaptive [`crate::basis::Basis`].
2//!
3//! These turn "might overflow" into "provision exactly enough channels, then prove
4//! it fit." Every bound here is an *upper* bound on the bit-height of the result, so
5//! `Basis::with_bits(bound + slack)` is guaranteed large enough for reconstruction.
6
7use num_bigint::BigInt;
8use num_traits::Zero;
9
10/// Bit-length of an integer (0 has length 0).
11pub fn integer_bits(n: &BigInt) -> u64 {
12    n.bits()
13}
14
15/// Exact bound for a product of integers: the sum of their bit-lengths (+1 slack
16/// for the leading carry).
17pub fn product_bits(values: &[BigInt]) -> u64 {
18    values.iter().map(|v| v.bits()).sum::<u64>() + 1
19}
20
21/// `floor` infinity-norm in bits: the largest coefficient bit-length.
22fn inf_norm_bits(coeffs: &[BigInt]) -> u64 {
23    coeffs.iter().map(|c| c.bits()).max().unwrap_or(0)
24}
25
26/// Upper bound on `log2 ‖f‖₂`, using `‖f‖₂ ≤ sqrt(n+1)·‖f‖∞`.
27fn two_norm_log2_upper(coeffs: &[BigInt]) -> f64 {
28    let n = coeffs.iter().filter(|c| !c.is_zero()).count().max(1);
29    let inf = inf_norm_bits(coeffs) as f64;
30    0.5 * (n as f64 + 1.0).log2() + inf
31}
32
33/// Hadamard/Mahler bound on `Res(f, g)` in bits:
34/// `‖f‖₂^deg g · ‖g‖₂^deg f` (with slack for the sign bit and rounding).
35pub fn resultant_bits(f: &[BigInt], g: &[BigInt]) -> u64 {
36    let deg_f = f.len().saturating_sub(1) as f64;
37    let deg_g = g.len().saturating_sub(1) as f64;
38    let log_f = two_norm_log2_upper(f);
39    let log_g = two_norm_log2_upper(g);
40    let bits = deg_g * log_f + deg_f * log_g;
41    bits.ceil() as u64 + 4
42}
43
44/// Hadamard bound on an `n×n` integer determinant in bits: `∏ row-2-norms`.
45pub fn determinant_bits(rows: &[Vec<BigInt>]) -> u64 {
46    let mut total = 0.0f64;
47    for row in rows {
48        total += two_norm_log2_upper(row);
49    }
50    total.ceil() as u64 + 2
51}
52
53/// Mignotte bound on the coefficients of any integer factor `g | f` in bits:
54/// `‖g‖∞ ≤ 2^deg g · ‖f‖₂` (we use `deg f` as the worst-case factor degree).
55pub fn mignotte_bits(f: &[BigInt]) -> u64 {
56    let deg = f.len().saturating_sub(1) as u64;
57    let log_f2 = two_norm_log2_upper(f).ceil() as u64;
58    deg + log_f2 + 2
59}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn product_is_sum_of_bits() {
67        let vals = vec![BigInt::from(255), BigInt::from(255)];
68        // 255*255 = 65025 needs 16 bits; bound is 8+8+1 = 17 ≥ 16
69        assert!(product_bits(&vals) >= 16);
70    }
71
72    #[test]
73    fn resultant_bound_is_positive() {
74        let f = vec![BigInt::from(1), BigInt::from(0), BigInt::from(-2)]; // x^2 - 2
75        let g = vec![BigInt::from(1), BigInt::from(0), BigInt::from(-3)]; // x^2 - 3
76        assert!(resultant_bits(&f, &g) > 0);
77    }
78}
adele_ring/bounds.rs

adele_ring/
bounds.rs
