dashu-int 0.6.0-rc.4

Arbitrary-precision integer math library for Rust, balancing ergonomics and efficiency. Provides UBig and IBig (unsigned and signed), with small values inlined on the stack. Efficient arithmetic, modular arithmetic, and number theory (pow, ilog, gcd, gcd_ext); two's-complement bit operations; parsing and formatting in base 2-36; optional serde, rand, num-traits, rkyv, and zeroize.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

//! NTT primes and constants for 32-bit Word targets.
//!
//! Uses Proth primes of the form `K * 2^N + 1`.
//! All constants computed by `integer/src/mul/ntt/compute_constants.py`.

use num_modular::FixedProth32;

// Proth reducer instances — each with a different (N, K) pair.
pub type Rp0 = FixedProth32<26, 7>;
pub type Rp1 = FixedProth32<27, 15>;
pub type Rp2 = FixedProth32<27, 17>;

pub const P0: Rp0 = FixedProth32::<26, 7>;
pub const P1: Rp1 = FixedProth32::<27, 15>;
pub const P2: Rp2 = FixedProth32::<27, 17>;

pub const K: usize = 3;
pub const MAX_LOG_N: u32 = 26;
pub const B_PACK_MIN: u32 = 8;
pub const B_PACK_CANDIDATES: &[u32] = &[32, 16, 8];

pub type Lane = u32;

/// Primitive `MAX_LOG_N`-th roots of unity for each prime.
pub const OMEGA_MAX: [Lane; K] = [
    0x0000088b, // P0
    0x3a26eef8, // P1
    0x1aa0ab5e, // P2
];

pub const CRT_INV_IJ: [[Lane; K]; K] = [[0, 0x4e42c85b, 0x5fb425ef], [0, 0, 0x44000009], [0, 0, 0]];

/// Prime moduli indexed by PI.
pub const MODULI: [Lane; K] = [Rp0::MODULUS, Rp1::MODULUS, Rp2::MODULUS];

#[cfg(test)]
mod tests {
    use super::*;
    use num_modular::Reducer;

    type ReducerFns = (fn(Lane) -> Lane, fn(Lane) -> Lane, fn(Lane) -> Lane);

    #[test]
    fn test_primes_proth_form() {
        assert_eq!(MODULI[0], 7u32 * (1u32 << 26) + 1);
        assert_eq!(MODULI[1], 15u32 * (1u32 << 27) + 1);
        assert_eq!(MODULI[2], 17u32 * (1u32 << 27) + 1);
    }

    #[test]
    fn test_primes_v2() {
        for &p in &MODULI {
            let v2 = (p - 1).trailing_zeros();
            assert!(v2 >= MAX_LOG_N, "v2(p-1) = {v2} < MAX_LOG_N");
        }
    }

    #[test]
    fn test_omega_order() {
        for (pi, &omega_max) in OMEGA_MAX.iter().enumerate() {
            let p = MODULI[pi];
            let (sqr, to_m, from_m): ReducerFns = match pi {
                0 => {
                    (|w| P0.reduce((w as u64) * (w as u64)), |v| P0.transform(v), |v| P0.residue(v))
                }
                1 => {
                    (|w| P1.reduce((w as u64) * (w as u64)), |v| P1.transform(v), |v| P1.residue(v))
                }
                2 => {
                    (|w| P2.reduce((w as u64) * (w as u64)), |v| P2.transform(v), |v| P2.residue(v))
                }
                _ => unreachable!(),
            };

            let mut w = to_m(omega_max);
            for _ in 0..MAX_LOG_N - 1 {
                w = sqr(w);
            }
            assert_eq!(from_m(w), p - 1, "omega^(2^(MAX_LOG_N-1)) != -1 mod p for prime {pi}");
            w = sqr(w);
            assert_eq!(from_m(w), 1, "omega^(2^MAX_LOG_N) != 1 mod p for prime {pi}");
        }
    }
}