qfall_math/integer_mod_q/z_q/sample/
binomial.rs

1// Copyright 2023 Jan Niklas Siemer
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! This module contains algorithms for sampling
10//! according to the binomial distribution.
11
12use crate::{
13    error::MathError,
14    integer::Z,
15    integer_mod_q::{Modulus, Zq},
16    macros::seeded::seedable_function,
17    rational::Q,
18    utils::sample::binomial::BinomialSampler,
19};
20
21impl Zq {
22    seedable_function!(
23        /// Chooses a [`Zq`] instance according to the binomial distribution
24        /// parameterized by `n` and `p`.
25        ///
26        /// Parameters:
27        /// - `modulus`: specifies the [`Modulus`] of the new [`Zq`] instance
28        /// - `n`: specifies the number of trials
29        /// - `p`: specifies the probability of success
30        #[seeded]
31        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
32        #[optionally_seeded]
33        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
34        #[optionally_seeded]
35        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
36        ///
37        /// Returns a fresh [`Zq`] instance with a value sampled
38        /// according to the binomial distribution or a [`MathError`]
39        /// if `n < 0`, `p ∉ (0,1)`, or `n` does not fit into an [`i64`].
40        ///
41        /// # Examples
42        /// ```
43        /// use qfall_math::integer_mod_q::Zq;
44        ///
45        #[unseeded]
46        /// let sample = Zq::sample_binomial(7, 2, 0.5).unwrap();
47        #[seeded]
48        /// let sample = Zq::sample_binomial_seeded(7, 2, 0.5, [42; 32]).unwrap();
49        /// ```
50        ///
51        /// # Errors and Failures
52        /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
53        ///   if `n < 0`.
54        /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
55        ///   if `p ∉ (0,1)`.
56        /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
57        ///   if `n` does not fit into an [`i64`].
58        ///
59        /// # Panics ...
60        /// - if `modulus` is smaller than `2`.
61        pub(crate) fn sample_binomial(
62            modulus: impl Into<Modulus>,
63            n: impl Into<Z>,
64            p: impl Into<Q>,
65            seed: Option<[u8; 32]>,
66        ) -> Result<Self, MathError> {
67            let modulus: Modulus = modulus.into();
68            let mut bin_sampler = BinomialSampler::init(n, p, seed)?;
69
70            let sample = bin_sampler.sample();
71            Ok(Zq::from((sample, modulus)))
72        }
73    );
74}
75
76#[cfg(test)]
77mod test_sample_binomial {
78    use super::{Q, Z, Zq};
79    use crate::utils::sample::test_seed;
80
81    // As all major tests regarding an appropriate binomial distribution,
82    // whether the correct interval is kept, and if the errors are thrown correctly,
83    // are performed in the `utils` module, we omit these tests here.
84
85    /// Checks whether `sample_binomial` is available for all types
86    /// implementing [`Into<Zq>`], i.e. u8, u16, u32, u64, i8, ...
87    /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
88    /// and [`Into<Modulus>`], i.e. u8, u16, u32, u64, i8, ...
89    #[test]
90    fn availability() {
91        for seeded in [false, true] {
92            let _ = Zq::sample_binomial_optionally_seeded(7u8, 1u16, 7u8, seeded.then(test_seed));
93            let _ = Zq::sample_binomial_optionally_seeded(7u16, 1u32, 7u16, seeded.then(test_seed));
94            let _ = Zq::sample_binomial_optionally_seeded(7u32, 1u64, 7u32, seeded.then(test_seed));
95            let _ = Zq::sample_binomial_optionally_seeded(7u64, 1i8, 7u64, seeded.then(test_seed));
96            let _ = Zq::sample_binomial_optionally_seeded(7i8, 1i16, 7i8, seeded.then(test_seed));
97            let _ = Zq::sample_binomial_optionally_seeded(7i16, 1i32, 7i16, seeded.then(test_seed));
98            let _ = Zq::sample_binomial_optionally_seeded(7i32, 1i64, 7i32, seeded.then(test_seed));
99            let _ =
100                Zq::sample_binomial_optionally_seeded(7i64, Z::ONE, 7i64, seeded.then(test_seed));
101            let _ = Zq::sample_binomial_optionally_seeded(7, 1u8, 0.5f32, seeded.then(test_seed));
102            let _ = Zq::sample_binomial_optionally_seeded(7, 1u8, 0.5f64, seeded.then(test_seed));
103            let _ = Zq::sample_binomial_optionally_seeded(
104                7,
105                1,
106                Q::from((1, 2)),
107                seeded.then(test_seed),
108            );
109
110            // explicitly checks the existence of the unseeded and the seeded function
111            if seeded {
112                let _ = Zq::sample_binomial_seeded(7u8, 1u16, 7u8, test_seed());
113            } else {
114                let _ = Zq::sample_binomial(7u8, 1u16, 7u8);
115            }
116        }
117    }
118
119    /// Checks whether the same seed results in the same sample.
120    #[test]
121    fn same_seed_same_sample() {
122        use crate::integer_mod_q::Zq;
123        let sample_0 = Zq::sample_binomial_seeded(7, 2, 0.5, [42; 32]).unwrap();
124        let sample_1 = Zq::sample_binomial_seeded(7, 2, 0.5, [42; 32]).unwrap();
125
126        assert_eq!(sample_0, sample_1);
127    }
128
129    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
130    #[test]
131    fn known_answer() {
132        use crate::integer_mod_q::Zq;
133        let sample = Zq::sample_binomial_seeded(7, 2, 0.5, [42; 32]).unwrap();
134
135        assert_eq!("0 mod 7", sample.to_string());
136    }
137}
qfall_math/integer_mod_q/z_q/sample/binomial.rs

qfall_math/integer_mod_q/z_q/sample/
binomial.rs
