qfall_math/integer_mod_q/mat_polynomial_ring_zq/sample/
binomial.rs

1// Copyright © 2023 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::{MatPolyOverZ, Z},
15    integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq},
16    rational::Q,
17};
18use std::fmt::Display;
19
20impl MatPolynomialRingZq {
21    /// Outputs a [`MatPolynomialRingZq`] instance with entries chosen according to the binomial
22    /// distribution parameterized by `n` and `p`.
23    ///
24    /// Parameters:
25    /// - `num_rows`: specifies the number of rows the new matrix should have
26    /// - `num_cols`: specifies the number of columns the new matrix should have
27    /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
28    ///   ring of polynomials modulo `modulus.get_q()` is defined
29    /// - `n`: specifies the number of trials
30    /// - `p`: specifies the probability of success
31    ///
32    /// Returns a new [`MatPolynomialRingZq`] instance with entries chosen
33    /// according to the binomial distribution or a [`MathError`]
34    /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
35    /// or the dimensions of the matrix were chosen too small.
36    ///
37    /// # Examples
38    /// ```
39    /// use qfall_math::integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq};
40    /// use std::str::FromStr;
41    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
42    ///
43    /// let sample = MatPolynomialRingZq::sample_binomial(2, 2, &modulus, 2, 0.5).unwrap();
44    /// ```
45    ///
46    /// # Errors and Failures
47    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
48    ///   if `n < 0` or `p ∉ (0,1)`.
49    /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
50    ///   if `n` does not fit into an [`i64`].
51    ///
52    /// # Panics ...
53    /// - if the provided number of rows and columns are not suited to create a matrix.
54    ///   For further information see [`MatPolynomialRingZq::new`].
55    /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
56    pub fn sample_binomial(
57        num_rows: impl TryInto<i64> + Display,
58        num_cols: impl TryInto<i64> + Display,
59        modulus: impl Into<ModulusPolynomialRingZq>,
60        n: impl Into<Z>,
61        p: impl Into<Q>,
62    ) -> Result<Self, MathError> {
63        Self::sample_binomial_with_offset(num_rows, num_cols, modulus, 0, n, p)
64    }
65
66    /// Outputs a [`MatPolynomialRingZq`] instance with entries chosen according to the binomial
67    /// distribution parameterized by `n` and `p` with given `offset`.
68    ///
69    /// Parameters:
70    /// - `num_rows`: specifies the number of rows the new matrix should have
71    /// - `num_cols`: specifies the number of columns the new matrix should have
72    /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
73    ///   ring of polynomials modulo `modulus.get_q()` is defined
74    /// - `offset`: specifies an offset applied to each sample
75    ///   collected from the binomial distribution
76    /// - `n`: specifies the number of trials
77    /// - `p`: specifies the probability of success
78    ///
79    /// Returns a new [`MatPolynomialRingZq`] instance with entries chosen
80    /// according to the binomial distribution or a [`MathError`]
81    /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
82    /// or the dimensions of the matrix were chosen too small.
83    ///
84    /// # Examples
85    /// ```
86    /// use qfall_math::integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq};
87    /// use std::str::FromStr;
88    /// let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
89    ///
90    /// let sample = MatPolynomialRingZq::sample_binomial_with_offset(2, 2, &modulus, -1, 2, 0.5).unwrap();
91    /// ```
92    ///
93    /// # Errors and Failures
94    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
95    ///   if `n < 0` or `p ∉ (0,1)`.
96    /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
97    ///   if `n` does not fit into an [`i64`].
98    ///
99    /// # Panics ...
100    /// - if the provided number of rows and columns are not suited to create a matrix.
101    ///   For further information see [`MatPolynomialRingZq::new`].
102    /// - if the provided [`ModulusPolynomialRingZq`] has degree `0`.
103    pub fn sample_binomial_with_offset(
104        num_rows: impl TryInto<i64> + Display,
105        num_cols: impl TryInto<i64> + Display,
106        modulus: impl Into<ModulusPolynomialRingZq>,
107        offset: impl Into<Z>,
108        n: impl Into<Z>,
109        p: impl Into<Q>,
110    ) -> Result<Self, MathError> {
111        let modulus = modulus.into();
112        assert!(
113            modulus.get_degree() > 0,
114            "ModulusPolynomial of degree 0 is insufficient to sample over."
115        );
116
117        let matrix = MatPolyOverZ::sample_binomial_with_offset(
118            num_rows,
119            num_cols,
120            modulus.get_degree() - 1,
121            offset,
122            n,
123            p,
124        )?;
125        Ok(MatPolynomialRingZq::from((matrix, modulus)))
126    }
127}
128
129#[cfg(test)]
130mod test_sample_binomial {
131    use super::{MatPolynomialRingZq, ModulusPolynomialRingZq, Q, Z};
132    use crate::{
133        integer::PolyOverZ,
134        integer_mod_q::PolyOverZq,
135        traits::{GetCoefficient, MatrixDimensions, MatrixGetEntry, SetCoefficient},
136    };
137    use std::str::FromStr;
138
139    // As all major tests regarding an appropriate binomial distribution,
140    // whether the correct interval is kept, and if the errors are thrown correctly,
141    // are performed in the `utils` module, we omit these tests here.
142
143    /// Checks whether the boundaries of the interval are kept.
144    #[test]
145    fn boundaries_kept() {
146        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
147
148        for _ in 0..8 {
149            let matrix = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 2, 0.5).unwrap();
150            let entry: PolyOverZ = matrix.get_entry(0, 0).unwrap();
151            let poly = entry.get_coeff(0).unwrap();
152
153            assert!(Z::ZERO <= poly);
154            assert!(poly <= 2);
155        }
156    }
157
158    /// Checks whether the number of coefficients is correct.
159    #[test]
160    fn nr_coeffs() {
161        let degrees = [1, 3, 7, 15, 32, 120];
162        for degree in degrees {
163            let mut modulus = PolyOverZq::from((1, u64::MAX));
164            modulus.set_coeff(degree, 1).unwrap();
165            let modulus = ModulusPolynomialRingZq::from(&modulus);
166
167            let matrix = MatPolynomialRingZq::sample_binomial(1, 1, modulus, 256, 0.99999).unwrap();
168            let poly: PolyOverZ = matrix.get_entry(0, 0).unwrap();
169
170            assert_eq!(
171                degree,
172                poly.get_degree() + 1,
173                "This test can fail with probability close to 0."
174            );
175        }
176    }
177
178    /// Checks whether matrices with at least one dimension chosen smaller than `1`
179    /// or too big for an [`i64`] results in an error.
180    #[should_panic]
181    #[test]
182    fn false_size() {
183        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
184
185        let _ = MatPolynomialRingZq::sample_binomial(0, 3, modulus, 1, 0.5);
186    }
187
188    /// Checks whether 0 modulus polynomial is insufficient.
189    #[test]
190    #[should_panic]
191    fn invalid_modulus() {
192        let modulus = ModulusPolynomialRingZq::from_str("1  1 mod 17").unwrap();
193
194        let _ = MatPolynomialRingZq::sample_binomial(1, 1, modulus, 1, 0.5);
195    }
196
197    /// Checks whether `sample_binomial` is available for all types
198    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
199    /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
200    #[test]
201    fn availability() {
202        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
203
204        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1u16, 7u8);
205        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1u32, 7u16);
206        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1u64, 7u32);
207        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1i8, 7u64);
208        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1i16, 7i8);
209        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1i32, 7i16);
210        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1i64, 7i32);
211        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, Z::ONE, 7i64);
212        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1u8, 0.5f32);
213        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1u8, 0.5f64);
214        let _ = MatPolynomialRingZq::sample_binomial(1, 1, &modulus, 1, Q::from((1, 2)));
215    }
216
217    /// Checks whether the size of uniformly random sampled matrices
218    /// fits the specified dimensions.
219    #[test]
220    fn matrix_size() {
221        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
222
223        let mat_0 = MatPolynomialRingZq::sample_binomial(3, 3, &modulus, 1, 0.5).unwrap();
224        let mat_1 = MatPolynomialRingZq::sample_binomial(4, 1, &modulus, 1, 0.5).unwrap();
225        let mat_2 = MatPolynomialRingZq::sample_binomial(1, 5, &modulus, 1, 0.5).unwrap();
226        let mat_3 = MatPolynomialRingZq::sample_binomial(15, 20, &modulus, 1, 0.5).unwrap();
227
228        assert_eq!(3, mat_0.get_num_rows());
229        assert_eq!(3, mat_0.get_num_columns());
230        assert_eq!(4, mat_1.get_num_rows());
231        assert_eq!(1, mat_1.get_num_columns());
232        assert_eq!(1, mat_2.get_num_rows());
233        assert_eq!(5, mat_2.get_num_columns());
234        assert_eq!(15, mat_3.get_num_rows());
235        assert_eq!(20, mat_3.get_num_columns());
236    }
237}
238
239#[cfg(test)]
240mod test_sample_binomial_with_offset {
241    use super::{MatPolynomialRingZq, ModulusPolynomialRingZq, Q, Z};
242    use crate::{
243        integer::PolyOverZ,
244        integer_mod_q::PolyOverZq,
245        traits::{GetCoefficient, MatrixDimensions, MatrixGetEntry, SetCoefficient},
246    };
247    use std::str::FromStr;
248
249    // As all major tests regarding an appropriate binomial distribution,
250    // whether the correct interval is kept, and if the errors are thrown correctly,
251    // are performed in the `utils` module, we omit these tests here.
252
253    /// Checks whether the boundaries of the interval are kept.
254    #[test]
255    fn boundaries_kept() {
256        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
257
258        for _ in 0..8 {
259            let matrix =
260                MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 2, 0.5)
261                    .unwrap();
262            let poly: PolyOverZ = matrix.get_entry(0, 0).unwrap();
263            let value = poly.get_coeff(0).unwrap();
264
265            assert!(16 <= value || value <= Z::ONE);
266        }
267    }
268
269    /// Checks whether the number of coefficients is correct.
270    #[test]
271    fn nr_coeffs() {
272        let degrees = [1, 3, 7, 15, 32, 120];
273        for degree in degrees {
274            let mut modulus = PolyOverZq::from((1, u64::MAX));
275            modulus.set_coeff(degree, 1).unwrap();
276            let modulus = ModulusPolynomialRingZq::from(&modulus);
277
278            let matrix =
279                MatPolynomialRingZq::sample_binomial_with_offset(1, 1, modulus, 1, 256, 0.99999)
280                    .unwrap();
281            let poly: PolyOverZ = matrix.get_entry(0, 0).unwrap();
282
283            assert_eq!(degree, poly.get_degree() + 1,);
284        }
285    }
286
287    /// Checks whether matrices with at least one dimension chosen smaller than `1`
288    /// or too big for an [`i64`] results in an error.
289    #[should_panic]
290    #[test]
291    fn false_size() {
292        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
293
294        let _ = MatPolynomialRingZq::sample_binomial_with_offset(0, 3, modulus, -1, 1, 0.5);
295    }
296
297    /// Checks whether 0 modulus polynomial is insufficient.
298    #[test]
299    #[should_panic]
300    fn invalid_modulus() {
301        let modulus = ModulusPolynomialRingZq::from_str("1  1 mod 17").unwrap();
302
303        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, modulus, -1, 1, 0.5);
304    }
305
306    /// Checks whether `sample_binomial_with_offset` is available for all types
307    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
308    /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
309    #[test]
310    fn availability() {
311        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
312
313        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 1u16, 7u8);
314        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, 0, 1u32, 7u16);
315        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 1u64, 7u32);
316        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 1i8, 7u64);
317        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 1i16, 7i8);
318        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 1i32, 7i16);
319        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 1i64, 7i32);
320        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, Z::ONE, 7i64);
321        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, -1, 1u8, 0.5f32);
322        let _ = MatPolynomialRingZq::sample_binomial_with_offset(1, 1, &modulus, 1, 1u8, 0.5f64);
323        let _ = MatPolynomialRingZq::sample_binomial_with_offset(
324            1,
325            1,
326            &modulus,
327            Z::ONE,
328            1,
329            Q::from((1, 2)),
330        );
331    }
332
333    /// Checks whether the size of uniformly random sampled matrices
334    /// fits the specified dimensions.
335    #[test]
336    fn matrix_size() {
337        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
338
339        let mat_0 =
340            MatPolynomialRingZq::sample_binomial_with_offset(3, 3, &modulus, -1, 1, 0.5).unwrap();
341        let mat_1 =
342            MatPolynomialRingZq::sample_binomial_with_offset(4, 1, &modulus, -1, 1, 0.5).unwrap();
343        let mat_2 =
344            MatPolynomialRingZq::sample_binomial_with_offset(1, 5, &modulus, -1, 1, 0.5).unwrap();
345        let mat_3 =
346            MatPolynomialRingZq::sample_binomial_with_offset(15, 20, &modulus, -1, 1, 0.5).unwrap();
347
348        assert_eq!(3, mat_0.get_num_rows());
349        assert_eq!(3, mat_0.get_num_columns());
350        assert_eq!(4, mat_1.get_num_rows());
351        assert_eq!(1, mat_1.get_num_columns());
352        assert_eq!(1, mat_2.get_num_rows());
353        assert_eq!(5, mat_2.get_num_columns());
354        assert_eq!(15, mat_3.get_num_rows());
355        assert_eq!(20, mat_3.get_num_columns());
356    }
357}
qfall_math/integer_mod_q/mat_polynomial_ring_zq/sample/binomial.rs

qfall_math/integer_mod_q/mat_polynomial_ring_zq/sample/
binomial.rs
