qfall_math/integer/mat_z/sample/
uniform.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 sampling algorithms for uniform distributions.
10
11use crate::{
12    error::MathError,
13    integer::{MatZ, Z},
14    macros::seeded::seedable_function,
15    traits::{MatrixDimensions, MatrixSetEntry},
16    utils::sample::uniform::UniformIntegerSampler,
17};
18use std::fmt::Display;
19
20impl MatZ {
21    seedable_function!(
22        /// Outputs a [`MatZ`] instance with entries chosen uniform at random
23        /// in `[lower_bound, upper_bound)`.
24        ///
25        /// The internally used uniform at random chosen bytes are generated
26        #[unseeded]
27        /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and is
28        #[seeded]
29        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed`, which uses ChaCha12 and is
30        #[optionally_seeded]
31        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed` or by [`ThreadRng`](rand::rngs::ThreadRng)
32        #[optionally_seeded]
33        /// if `seed` is `None`. Both use ChaCha12 and are
34        /// considered cryptographically secure.
35        ///
36        /// Parameters:
37        /// - `num_rows`: specifies the number of rows the new matrix should have
38        /// - `num_cols`: specifies the number of columns the new matrix should have
39        /// - `lower_bound`: specifies the included lower bound of the
40        ///   interval over which is sampled
41        /// - `upper_bound`: specifies the excluded upper bound of the
42        ///   interval over which is sampled
43        #[seeded]
44        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
45        #[optionally_seeded]
46        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
47        #[optionally_seeded]
48        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
49        ///
50        /// Returns a new [`MatZ`] instance with entries chosen
51        /// uniformly at random in `[lower_bound, upper_bound)` or a [`MathError`]
52        /// if the dimensions of the matrix or the interval were chosen too small.
53        ///
54        /// # Examples
55        /// ```
56        /// use qfall_math::integer::MatZ;
57        ///
58        #[unseeded]
59        /// let matrix = MatZ::sample_uniform(3, 3, 17, 26).unwrap();
60        #[seeded]
61        /// let matrix = MatZ::sample_uniform_seeded(3, 3, 17, 26, [42; 32]).unwrap();
62        /// ```
63        ///
64        /// # Errors and Failures
65        /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
66        ///   if the given `upper_bound` isn't at least larger than `lower_bound`.
67        ///
68        /// # Panics ...
69        /// - if the provided number of rows and columns are not suited to create a matrix.
70        ///   For further information see [`MatZ::new`].
71        pub(crate) fn sample_uniform(
72            num_rows: impl TryInto<i64> + Display,
73            num_cols: impl TryInto<i64> + Display,
74            lower_bound: impl Into<Z>,
75            upper_bound: impl Into<Z>,
76            seed: Option<[u8; 32]>,
77        ) -> Result<Self, MathError> {
78            let lower_bound: Z = lower_bound.into();
79            let upper_bound: Z = upper_bound.into();
80            let mut matrix = MatZ::new(num_rows, num_cols);
81
82            let interval_size = &upper_bound - &lower_bound;
83            let mut uis = UniformIntegerSampler::init(&interval_size, seed)?;
84            for row in 0..matrix.get_num_rows() {
85                for col in 0..matrix.get_num_columns() {
86                    let sample = uis.sample();
87                    unsafe { matrix.set_entry_unchecked(row, col, &lower_bound + sample) };
88                }
89            }
90
91            Ok(matrix)
92        }
93    );
94}
95
96#[cfg(test)]
97mod test_sample_uniform {
98    use crate::traits::{MatrixDimensions, MatrixGetEntry};
99    use crate::utils::sample::test_seed;
100    use crate::{
101        integer::{MatZ, Z},
102        integer_mod_q::Modulus,
103    };
104
105    /// Checks whether the boundaries of the interval are kept for small intervals.
106    #[test]
107    fn boundaries_kept_small() {
108        for seeded in [false, true] {
109            let lower_bound = Z::from(17);
110            let upper_bound = Z::from(32);
111            for _ in 0..32 {
112                let matrix = MatZ::sample_uniform_optionally_seeded(
113                    1,
114                    1,
115                    &lower_bound,
116                    &upper_bound,
117                    seeded.then(test_seed),
118                )
119                .unwrap();
120                let sample = matrix.get_entry(0, 0).unwrap();
121                assert!(lower_bound <= sample);
122                assert!(sample < upper_bound);
123            }
124        }
125    }
126
127    /// Checks whether the boundaries of the interval are kept for large intervals.
128    #[test]
129    fn boundaries_kept_large() {
130        for seeded in [false, true] {
131            let lower_bound = Z::from(i64::MIN) - Z::from(u64::MAX);
132            let upper_bound = Z::from(i64::MIN);
133            for _ in 0..256 {
134                let matrix = MatZ::sample_uniform_optionally_seeded(
135                    1,
136                    1,
137                    &lower_bound,
138                    &upper_bound,
139                    seeded.then(test_seed),
140                )
141                .unwrap();
142                let sample = matrix.get_entry(0, 0).unwrap();
143                assert!(lower_bound <= sample);
144                assert!(sample < upper_bound);
145            }
146        }
147    }
148
149    /// Checks whether matrices with at least one dimension chosen smaller than `1`
150    /// or too large for an [`i64`] results in an error.
151    #[test]
152    fn false_size() {
153        for seeded in [false, true] {
154            let result = std::panic::catch_unwind(|| {
155                let lower_bound = Z::from(-15);
156                let upper_bound = Z::from(15);
157
158                let _ = MatZ::sample_uniform_optionally_seeded(
159                    0,
160                    3,
161                    &lower_bound,
162                    &upper_bound,
163                    seeded.then(test_seed),
164                );
165            });
166            assert!(result.is_err());
167        }
168    }
169
170    /// Checks whether providing an invalid interval results in an error.
171    #[test]
172    fn invalid_interval() {
173        for seeded in [false, true] {
174            let lb_0 = Z::from(i64::MIN);
175            let lb_1 = Z::from(i64::MIN);
176            let lb_2 = Z::ZERO;
177            let upper_bound = Z::from(i64::MIN);
178
179            let mat_0 = MatZ::sample_uniform_optionally_seeded(
180                3,
181                3,
182                &lb_0,
183                &upper_bound,
184                seeded.then(test_seed),
185            );
186            let mat_1 = MatZ::sample_uniform_optionally_seeded(
187                4,
188                1,
189                &lb_1,
190                &upper_bound,
191                seeded.then(test_seed),
192            );
193            let mat_2 = MatZ::sample_uniform_optionally_seeded(
194                1,
195                5,
196                &lb_2,
197                &upper_bound,
198                seeded.then(test_seed),
199            );
200
201            assert!(mat_0.is_err());
202            assert!(mat_1.is_err());
203            assert!(mat_2.is_err());
204        }
205    }
206
207    /// Checks whether `sample_uniform` is available for all types
208    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
209    #[test]
210    fn availability() {
211        for seeded in [false, true] {
212            let modulus = Modulus::from(7);
213            let z = Z::from(7);
214
215            let _ = MatZ::sample_uniform_optionally_seeded(1, 1, 0u16, 7u8, seeded.then(test_seed));
216            let _ =
217                MatZ::sample_uniform_optionally_seeded(1, 1, 0u32, 7u16, seeded.then(test_seed));
218            let _ =
219                MatZ::sample_uniform_optionally_seeded(1, 1, 0u64, 7u32, seeded.then(test_seed));
220            let _ = MatZ::sample_uniform_optionally_seeded(1, 1, 0i8, 7u64, seeded.then(test_seed));
221            let _ = MatZ::sample_uniform_optionally_seeded(1, 1, 0i16, 7i8, seeded.then(test_seed));
222            let _ =
223                MatZ::sample_uniform_optionally_seeded(1, 1, 0i32, 7i16, seeded.then(test_seed));
224            let _ =
225                MatZ::sample_uniform_optionally_seeded(1, 1, 0i64, 7i32, seeded.then(test_seed));
226            let _ = MatZ::sample_uniform_optionally_seeded(
227                1,
228                1,
229                &Z::ZERO,
230                7i64,
231                seeded.then(test_seed),
232            );
233            let _ =
234                MatZ::sample_uniform_optionally_seeded(1, 1, 0u8, &modulus, seeded.then(test_seed));
235            let _ = MatZ::sample_uniform_optionally_seeded(1, 1, 0, &z, seeded.then(test_seed));
236
237            // explicitly checks the existence of the unseeded and the seeded function
238            if seeded {
239                let _ = MatZ::sample_uniform_seeded(1, 1, 0u16, 7u8, test_seed());
240            } else {
241                let _ = MatZ::sample_uniform(1, 1, 0u16, 7u8);
242            }
243        }
244    }
245
246    /// Checks whether the size of uniformly random sampled matrices
247    /// fits the specified dimensions.
248    #[test]
249    fn matrix_size() {
250        for seeded in [false, true] {
251            let lower_bound = Z::from(-15);
252            let upper_bound = Z::from(15);
253
254            let mat_0 = MatZ::sample_uniform_optionally_seeded(
255                3,
256                3,
257                &lower_bound,
258                &upper_bound,
259                seeded.then(test_seed),
260            )
261            .unwrap();
262            let mat_1 = MatZ::sample_uniform_optionally_seeded(
263                4,
264                1,
265                &lower_bound,
266                &upper_bound,
267                seeded.then(test_seed),
268            )
269            .unwrap();
270            let mat_2 = MatZ::sample_uniform_optionally_seeded(
271                1,
272                5,
273                &lower_bound,
274                &upper_bound,
275                seeded.then(test_seed),
276            )
277            .unwrap();
278            let mat_3 = MatZ::sample_uniform_optionally_seeded(
279                15,
280                20,
281                &lower_bound,
282                &upper_bound,
283                seeded.then(test_seed),
284            )
285            .unwrap();
286
287            assert_eq!(3, mat_0.get_num_rows());
288            assert_eq!(3, mat_0.get_num_columns());
289            assert_eq!(4, mat_1.get_num_rows());
290            assert_eq!(1, mat_1.get_num_columns());
291            assert_eq!(1, mat_2.get_num_rows());
292            assert_eq!(5, mat_2.get_num_columns());
293            assert_eq!(15, mat_3.get_num_rows());
294            assert_eq!(20, mat_3.get_num_columns());
295        }
296    }
297
298    /// Checks whether the same seed results in the same sample.
299    #[test]
300    fn same_seed_same_sample() {
301        use crate::integer::MatZ;
302        let sample_0 = MatZ::sample_uniform_seeded(3, 3, 17, 26, [42; 32]).unwrap();
303        let sample_1 = MatZ::sample_uniform_seeded(3, 3, 17, 26, [42; 32]).unwrap();
304
305        assert_eq!(sample_0, sample_1);
306    }
307
308    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
309    #[test]
310    fn known_answer() {
311        use crate::integer::MatZ;
312        let sample = MatZ::sample_uniform_seeded(3, 3, 17, 26, [42; 32]).unwrap();
313
314        assert_eq!(
315            "[[19, 20, 17],[19, 20, 22],[24, 24, 19]]",
316            sample.to_string()
317        );
318    }
319}
qfall_math/integer/mat_z/sample/uniform.rs

qfall_math/integer/mat_z/sample/
uniform.rs
