qfall_math/integer/mat_poly_over_z/sample/
uniform.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 sampling algorithms for uniform distributions.
10
11use crate::{
12    error::MathError,
13    integer::{MatPolyOverZ, PolyOverZ, Z},
14    traits::{MatrixDimensions, MatrixSetEntry},
15    utils::index::evaluate_index,
16};
17use std::fmt::Display;
18
19impl MatPolyOverZ {
20    /// Outputs a [`MatPolyOverZ`] instance with polynomials as entries,
21    /// whose coefficients were chosen uniform at random in `[lower_bound, upper_bound)`.
22    ///
23    /// The internally used uniform at random chosen bytes are generated
24    /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and
25    /// is considered cryptographically secure.
26    ///
27    /// Parameters:
28    /// - `num_rows`: specifies the number of rows the new matrix should have
29    /// - `num_cols`: specifies the number of columns the new matrix should have
30    /// - `max_degree`: specifies the maximum length of all polynomials in the matrix,
31    ///   i.e. the maximum number of coefficients any polynomial in the matrix can have
32    /// - `lower_bound`: specifies the included lower bound of the
33    ///   interval over which is sampled
34    /// - `upper_bound`: specifies the excluded upper bound of the
35    ///   interval over which is sampled
36    ///
37    /// Returns a new [`MatPolyOverZ`] instance with polynomials as entries,
38    /// whose coefficients were chosen uniformly at random in
39    /// `[lower_bound, upper_bound)` or a [`MathError`]
40    /// if the interval was chosen too small or the `max_degree` of the polynomials
41    /// is negative or too large to fit into [`i64`].
42    ///
43    /// # Examples
44    /// ```
45    /// use qfall_math::integer::MatPolyOverZ;
46    ///
47    /// let matrix = MatPolyOverZ::sample_uniform(3, 3, 5, 17, 26).unwrap();
48    /// ```
49    ///
50    /// # Errors and Failures
51    /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
52    ///   if the given `upper_bound` isn't at least larger than `lower_bound`.
53    /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
54    ///   the `max_degree` is negative or it does not fit into an [`i64`].
55    ///
56    /// # Panics ...
57    /// - if the provided number of rows and columns are not suited to create a matrix.
58    ///   For further information see [`MatPolyOverZ::new`].
59    pub fn sample_uniform(
60        num_rows: impl TryInto<i64> + Display,
61        num_cols: impl TryInto<i64> + Display,
62        max_degree: impl TryInto<i64> + Display,
63        lower_bound: impl Into<Z>,
64        upper_bound: impl Into<Z>,
65    ) -> Result<Self, MathError> {
66        let lower_bound: Z = lower_bound.into();
67        let upper_bound: Z = upper_bound.into();
68        let max_degree = evaluate_index(max_degree)?;
69        let mut matrix = MatPolyOverZ::new(num_rows, num_cols);
70
71        for row in 0..matrix.get_num_rows() {
72            for col in 0..matrix.get_num_columns() {
73                let sample = PolyOverZ::sample_uniform(max_degree, &lower_bound, &upper_bound)?;
74                unsafe { matrix.set_entry_unchecked(row, col, sample) };
75            }
76        }
77
78        Ok(matrix)
79    }
80}
81
82#[cfg(test)]
83mod test_sample_uniform {
84    use crate::traits::{GetCoefficient, MatrixDimensions, MatrixGetEntry};
85    use crate::{
86        integer::{MatPolyOverZ, Z},
87        integer_mod_q::Modulus,
88    };
89
90    /// Checks whether the boundaries of the interval are kept for small intervals.
91    #[test]
92    fn boundaries_kept_small() {
93        let lower_bound = Z::from(17);
94        let upper_bound = Z::from(32);
95        for _ in 0..32 {
96            let matrix = MatPolyOverZ::sample_uniform(1, 1, 0, &lower_bound, &upper_bound).unwrap();
97            let sample = matrix.get_entry(0, 0).unwrap();
98            let coeff = sample.get_coeff(0).unwrap();
99
100            assert!(lower_bound <= coeff);
101            assert!(coeff < upper_bound);
102        }
103    }
104
105    /// Checks whether the boundaries of the interval are kept for large intervals.
106    #[test]
107    fn boundaries_kept_large() {
108        let lower_bound = Z::from(i64::MIN) - Z::from(u64::MAX);
109        let upper_bound = Z::from(i64::MIN);
110        for _ in 0..256 {
111            let matrix = MatPolyOverZ::sample_uniform(1, 1, 0, &lower_bound, &upper_bound).unwrap();
112            let sample = matrix.get_entry(0, 0).unwrap();
113            let coeff = sample.get_coeff(0).unwrap();
114
115            assert!(lower_bound <= coeff);
116            assert!(coeff < upper_bound);
117        }
118    }
119
120    /// Checks whether the number of coefficients is correct.
121    #[test]
122    fn nr_coeffs() {
123        let degrees = [1, 3, 7, 15, 32, 120];
124        for degree in degrees {
125            let matrix = MatPolyOverZ::sample_uniform(1, 1, degree, 1, 15).unwrap();
126            let poly = matrix.get_entry(0, 0).unwrap();
127
128            assert_eq!(degree, poly.get_degree());
129        }
130    }
131
132    /// Checks whether matrices with at least one dimension chosen smaller than `1`
133    /// or too large for an [`i64`] results in an error.
134    #[should_panic]
135    #[test]
136    fn false_size() {
137        let lower_bound = Z::from(-15);
138        let upper_bound = Z::from(15);
139
140        let _ = MatPolyOverZ::sample_uniform(0, 3, 1, &lower_bound, &upper_bound);
141    }
142
143    /// Checks whether providing an invalid interval results in an error.
144    #[test]
145    fn invalid_interval() {
146        let lb_0 = Z::from(i64::MIN);
147        let lb_1 = Z::from(i64::MIN);
148        let lb_2 = Z::ZERO;
149        let upper_bound = Z::from(i64::MIN);
150
151        let mat_0 = MatPolyOverZ::sample_uniform(3, 3, 0, &lb_0, &upper_bound);
152        let mat_1 = MatPolyOverZ::sample_uniform(4, 1, 0, &lb_1, &upper_bound);
153        let mat_2 = MatPolyOverZ::sample_uniform(1, 5, 0, &lb_2, &upper_bound);
154
155        assert!(mat_0.is_err());
156        assert!(mat_1.is_err());
157        assert!(mat_2.is_err());
158    }
159
160    /// Checks whether providing a length smaller than `0` results in an error.
161    #[test]
162    fn invalid_max_degree() {
163        let lower_bound = Z::from(0);
164        let upper_bound = Z::from(15);
165
166        let res_0 = MatPolyOverZ::sample_uniform(1, 1, -1, &lower_bound, &upper_bound);
167        let res_1 = MatPolyOverZ::sample_uniform(1, 1, i64::MIN, &lower_bound, &upper_bound);
168
169        assert!(res_0.is_err());
170        assert!(res_1.is_err());
171    }
172
173    /// Checks whether `sample_uniform` is available for all types
174    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
175    #[test]
176    fn availability() {
177        let modulus = Modulus::from(7);
178        let z = Z::from(7);
179
180        let _ = MatPolyOverZ::sample_uniform(1, 1, 0u8, 0u16, 7u8);
181        let _ = MatPolyOverZ::sample_uniform(1, 1, 0u16, 0u32, 7u16);
182        let _ = MatPolyOverZ::sample_uniform(1, 1, 0u32, 0u64, 7u32);
183        let _ = MatPolyOverZ::sample_uniform(1, 1, 0u64, 0i8, 7u64);
184        let _ = MatPolyOverZ::sample_uniform(1, 1, 0i8, 0i16, 7i8);
185        let _ = MatPolyOverZ::sample_uniform(1, 1, 0i16, 0i32, 7i16);
186        let _ = MatPolyOverZ::sample_uniform(1, 1, 0i32, 0i64, 7i32);
187        let _ = MatPolyOverZ::sample_uniform(1, 1, 0i64, &Z::ZERO, 7i64);
188        let _ = MatPolyOverZ::sample_uniform(1, 1, 0, 0u8, &modulus);
189        let _ = MatPolyOverZ::sample_uniform(1, 1, Z::ZERO, 0, &z);
190    }
191
192    /// Checks whether the size of uniformly random sampled matrices
193    /// fits the specified dimensions.
194    #[test]
195    fn matrix_size() {
196        let lower_bound = Z::from(-15);
197        let upper_bound = Z::from(15);
198
199        let mat_0 = MatPolyOverZ::sample_uniform(3, 3, 0, &lower_bound, &upper_bound).unwrap();
200        let mat_1 = MatPolyOverZ::sample_uniform(4, 1, 0, &lower_bound, &upper_bound).unwrap();
201        let mat_2 = MatPolyOverZ::sample_uniform(1, 5, 0, &lower_bound, &upper_bound).unwrap();
202        let mat_3 = MatPolyOverZ::sample_uniform(15, 20, 0, &lower_bound, &upper_bound).unwrap();
203
204        assert_eq!(3, mat_0.get_num_rows());
205        assert_eq!(3, mat_0.get_num_columns());
206        assert_eq!(4, mat_1.get_num_rows());
207        assert_eq!(1, mat_1.get_num_columns());
208        assert_eq!(1, mat_2.get_num_rows());
209        assert_eq!(5, mat_2.get_num_columns());
210        assert_eq!(15, mat_3.get_num_rows());
211        assert_eq!(20, mat_3.get_num_columns());
212    }
213}
qfall_math/integer/mat_poly_over_z/sample/uniform.rs

qfall_math/integer/mat_poly_over_z/sample/
uniform.rs
