qfall_math/integer_mod_q/mat_zq/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 the uniform distributions.
10
11use crate::{
12    integer::Z,
13    integer_mod_q::MatZq,
14    macros::seeded::seedable_function,
15    traits::{MatrixDimensions, MatrixSetEntry},
16    utils::sample::uniform::UniformIntegerSampler,
17};
18use std::fmt::Display;
19
20impl MatZq {
21    seedable_function!(
22        /// Outputs a [`MatZq`] instance with entries chosen uniform at random
23        /// in `[0, modulus)`.
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        /// - `modulus`: specifies the modulus of the matrix and defines the interval
40        ///   over which is sampled
41        #[seeded]
42        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
43        #[optionally_seeded]
44        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
45        #[optionally_seeded]
46        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
47        ///
48        /// Returns a new [`MatZq`] instance with entries chosen
49        /// uniformly at random in `[0, modulus)`.
50        ///
51        /// # Examples
52        /// ```
53        /// use qfall_math::integer_mod_q::MatZq;
54        ///
55        #[unseeded]
56        /// let matrix = MatZq::sample_uniform(3, 3, 17);
57        #[seeded]
58        /// let matrix = MatZq::sample_uniform_seeded(3, 3, 17, [42; 32]);
59        /// ```
60        ///
61        /// # Panics ...
62        /// - if the provided number of rows and columns or the modulus are not suited to create a matrix.
63        ///   For further information see [`MatZq::new`].
64        pub(crate) fn sample_uniform(
65            num_rows: impl TryInto<i64> + Display,
66            num_cols: impl TryInto<i64> + Display,
67            modulus: impl Into<Z>,
68            seed: Option<[u8; 32]>,
69        ) -> Self {
70            let modulus: Z = modulus.into();
71            let mut uis = UniformIntegerSampler::init(&modulus, seed).unwrap();
72            let mut matrix = MatZq::new(num_rows, num_cols, modulus);
73
74            for row in 0..matrix.get_num_rows() {
75                for col in 0..matrix.get_num_columns() {
76                    let sample = uis.sample();
77                    unsafe { matrix.set_entry_unchecked(row, col, sample) };
78                }
79            }
80
81            matrix
82        }
83    );
84}
85
86#[cfg(test)]
87mod test_sample_uniform {
88    use crate::traits::{MatrixDimensions, MatrixGetEntry};
89    use crate::utils::sample::test_seed;
90    use crate::{
91        integer::Z,
92        integer_mod_q::{MatZq, Modulus},
93    };
94
95    /// Checks whether the boundaries of the interval are kept for small moduli.
96    #[test]
97    fn boundaries_kept_small() {
98        for seeded in [false, true] {
99            for _ in 0..32 {
100                let matrix =
101                    MatZq::sample_uniform_optionally_seeded(1, 1, 17, seeded.then(test_seed));
102                let sample: Z = matrix.get_entry(0, 0).unwrap();
103                assert!(Z::ZERO <= sample);
104                assert!(sample < 17);
105            }
106        }
107    }
108
109    /// Checks whether the boundaries of the interval are kept for large moduli.
110    #[test]
111    fn boundaries_kept_large() {
112        for seeded in [false, true] {
113            let modulus = Z::from(u64::MAX);
114            for _ in 0..256 {
115                let matrix =
116                    MatZq::sample_uniform_optionally_seeded(1, 1, &modulus, seeded.then(test_seed));
117                let sample: Z = matrix.get_entry(0, 0).unwrap();
118                assert!(Z::ZERO <= sample);
119                assert!(sample < modulus);
120            }
121        }
122    }
123
124    /// Checks whether matrices with at least one dimension chosen smaller than `1`
125    /// or too large for an [`i64`] results in a panic.
126    #[test]
127    fn false_size() {
128        for seeded in [false, true] {
129            let result = std::panic::catch_unwind(|| {
130                let modulus = Z::from(15);
131
132                let _ =
133                    MatZq::sample_uniform_optionally_seeded(0, 3, &modulus, seeded.then(test_seed));
134            });
135            assert!(result.is_err());
136        }
137    }
138
139    /// Checks whether providing an invalid interval/ modulus results in a panic.
140    #[test]
141    fn invalid_modulus() {
142        for seeded in [false, true] {
143            let result = std::panic::catch_unwind(|| {
144                let _ = MatZq::sample_uniform_optionally_seeded(4, 1, 1, seeded.then(test_seed));
145            });
146            assert!(result.is_err());
147        }
148    }
149
150    /// Checks whether `sample_uniform` is available for all types
151    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
152    #[test]
153    fn availability() {
154        for seeded in [false, true] {
155            let modulus = Modulus::from(7);
156            let z = Z::from(7);
157
158            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7u8, seeded.then(test_seed));
159            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7u16, seeded.then(test_seed));
160            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7u32, seeded.then(test_seed));
161            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7u64, seeded.then(test_seed));
162            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7i8, seeded.then(test_seed));
163            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7i16, seeded.then(test_seed));
164            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7i32, seeded.then(test_seed));
165            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, 7i64, seeded.then(test_seed));
166            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, &modulus, seeded.then(test_seed));
167            let _ = MatZq::sample_uniform_optionally_seeded(1, 1, &z, seeded.then(test_seed));
168
169            // explicitly checks the existence of the unseeded and the seeded function
170            if seeded {
171                let _ = MatZq::sample_uniform_seeded(1, 1, 7u8, test_seed());
172            } else {
173                let _ = MatZq::sample_uniform(1, 1, 7u8);
174            }
175        }
176    }
177
178    /// Checks whether the size of uniformly random sampled matrices
179    /// fits the specified dimensions.
180    #[test]
181    fn matrix_size() {
182        for seeded in [false, true] {
183            let modulus = Z::from(15);
184
185            let mat_0 =
186                MatZq::sample_uniform_optionally_seeded(3, 3, &modulus, seeded.then(test_seed));
187            let mat_1 =
188                MatZq::sample_uniform_optionally_seeded(4, 1, &modulus, seeded.then(test_seed));
189            let mat_2 =
190                MatZq::sample_uniform_optionally_seeded(1, 5, &modulus, seeded.then(test_seed));
191            let mat_3 =
192                MatZq::sample_uniform_optionally_seeded(15, 20, &modulus, seeded.then(test_seed));
193
194            assert_eq!(3, mat_0.get_num_rows());
195            assert_eq!(3, mat_0.get_num_columns());
196            assert_eq!(4, mat_1.get_num_rows());
197            assert_eq!(1, mat_1.get_num_columns());
198            assert_eq!(1, mat_2.get_num_rows());
199            assert_eq!(5, mat_2.get_num_columns());
200            assert_eq!(15, mat_3.get_num_rows());
201            assert_eq!(20, mat_3.get_num_columns());
202        }
203    }
204
205    /// Checks whether the same seed results in the same sample.
206    #[test]
207    fn same_seed_same_sample() {
208        use crate::integer_mod_q::MatZq;
209        let sample_0 = MatZq::sample_uniform_seeded(3, 3, 17, [42; 32]);
210        let sample_1 = MatZq::sample_uniform_seeded(3, 3, 17, [42; 32]);
211
212        assert_eq!(sample_0, sample_1);
213    }
214
215    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
216    #[test]
217    fn known_answer() {
218        use crate::integer_mod_q::MatZq;
219        let sample = MatZq::sample_uniform_seeded(3, 3, 17, [42; 32]);
220
221        assert_eq!(
222            "[[2, 16, 3],[7, 7, 16],[4, 13, 0]] mod 17",
223            sample.to_string()
224        );
225    }
226}
qfall_math/integer_mod_q/mat_zq/sample/uniform.rs

qfall_math/integer_mod_q/mat_zq/sample/
uniform.rs
