qfall_math/integer/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 algorithms for sampling according to the uniform distribution.
10
11use crate::{error::MathError, integer::Z, utils::sample::uniform::UniformIntegerSampler};
12
13impl Z {
14    /// Chooses a [`Z`] instance uniformly at random
15    /// in `[lower_bound, upper_bound)`.
16    ///
17    /// The internally used uniform at random chosen bytes are generated
18    /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and
19    /// is considered cryptographically secure.
20    ///
21    /// Parameters:
22    /// - `lower_bound`: specifies the included lower bound of the
23    ///   interval over which is sampled
24    /// - `upper_bound`: specifies the excluded upper bound of the
25    ///   interval over which is sampled
26    ///
27    /// Returns a fresh [`Z`] instance with a
28    /// uniform random value in `[lower_bound, upper_bound)` or a [`MathError`]
29    /// if the provided interval was chosen too small.
30    ///
31    /// # Examples
32    /// ```
33    /// use qfall_math::integer::Z;
34    ///
35    /// let sample = Z::sample_uniform(&17, &26).unwrap();
36    /// ```
37    ///
38    /// # Errors and Failures
39    /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
40    ///   if the given `upper_bound` isn't at least larger than `lower_bound`.
41    pub fn sample_uniform(
42        lower_bound: impl Into<Z>,
43        upper_bound: impl Into<Z>,
44    ) -> Result<Self, MathError> {
45        let lower_bound: Z = lower_bound.into();
46        let upper_bound: Z = upper_bound.into();
47
48        let interval_size = &upper_bound - &lower_bound;
49        let mut uis = UniformIntegerSampler::init(&interval_size)?;
50
51        let sample = uis.sample();
52        Ok(&lower_bound + sample)
53    }
54
55    /// Chooses a prime [`Z`] instance uniformly at random
56    /// in `[lower_bound, upper_bound)`. If after 2 * `n` steps, where `n` denotes the size of
57    /// the interval, no suitable prime was found, the algorithm aborts.
58    ///
59    /// The internally used uniform at random chosen bytes are generated
60    /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and
61    /// is considered cryptographically secure.
62    ///
63    /// Parameters:
64    /// - `lower_bound`: specifies the included lower bound of the
65    ///   interval over which is sampled
66    /// - `upper_bound`: specifies the excluded upper bound of the
67    ///   interval over which is sampled
68    ///
69    /// Returns a fresh [`Z`] instance with a
70    /// uniform random value in `[lower_bound, upper_bound)`. Otherwise, a [`MathError`]
71    /// if the provided interval was chosen too small, no prime could be found in the interval,
72    /// or the provided `lower_bound` was negative.
73    ///
74    /// # Examples
75    /// ```
76    /// use qfall_math::integer::Z;
77    ///
78    /// let prime = Z::sample_prime_uniform(1, 100).unwrap();
79    /// ```
80    ///
81    /// # Errors and Failures
82    /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
83    ///   if the given `upper_bound` isn't at least larger than `lower_bound`
84    ///   , or if no prime could be found in the specified interval.
85    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
86    ///   if `lower_bound` is negative as primes are always positive.
87    pub fn sample_prime_uniform(
88        lower_bound: impl Into<Z>,
89        upper_bound: impl Into<Z>,
90    ) -> Result<Self, MathError> {
91        let lower_bound: Z = lower_bound.into();
92        let upper_bound: Z = upper_bound.into();
93
94        if lower_bound < Z::ZERO {
95            return Err(MathError::InvalidIntegerInput(format!(
96                "Primes are always positive. Hence, sample_prime_uniform expects a positive lower_bound.
97                The provided one is {lower_bound}.")));
98        }
99
100        let interval_size = &upper_bound - &lower_bound;
101        let mut uis = UniformIntegerSampler::init(&interval_size)?;
102        let mut sample = &lower_bound + uis.sample();
103
104        // after 2 * size of interval many uniform random samples, a suitable prime should have been
105        // found with high probability, if there is one prime in the interval
106        let mut steps = 2 * &interval_size;
107        while !sample.is_prime() {
108            if steps == Z::ZERO {
109                return Err(MathError::InvalidInterval(format!(
110                    "After sampling O({interval_size}) times uniform at random in the interval [{lower_bound}, {upper_bound}[
111                        no prime was found. It is very likely, that no prime exists in this interval.
112                        Please choose the interval larger.")));
113            }
114            sample = &lower_bound + uis.sample();
115            steps -= 1;
116        }
117
118        Ok(sample)
119    }
120}
121
122#[cfg(test)]
123mod test_sample_uniform {
124    use crate::{integer::Z, integer_mod_q::Modulus};
125
126    /// Checks whether the boundaries of the interval are kept for small intervals.
127    #[test]
128    fn boundaries_kept_small() {
129        let lower_bound = Z::from(17);
130        let upper_bound = Z::from(32);
131        for _ in 0..32 {
132            let sample = Z::sample_uniform(&lower_bound, &upper_bound).unwrap();
133            assert!(lower_bound <= sample);
134            assert!(sample < upper_bound);
135        }
136    }
137
138    /// Checks whether the boundaries of the interval are kept for large intervals.
139    #[test]
140    fn boundaries_kept_large() {
141        let lower_bound = Z::from(i64::MIN) - Z::from(u64::MAX);
142        let upper_bound = Z::from(i64::MIN);
143        for _ in 0..256 {
144            let sample = Z::sample_uniform(&lower_bound, &upper_bound).unwrap();
145            assert!(lower_bound <= sample);
146            assert!(sample < upper_bound);
147        }
148    }
149
150    /// Checks whether providing an invalid interval results in an error.
151    #[test]
152    fn invalid_interval() {
153        let lb_0 = Z::from(i64::MIN);
154        let lb_1 = Z::from(i64::MIN);
155        let lb_2 = Z::ZERO;
156        let upper_bound = Z::from(i64::MIN);
157
158        let res_0 = Z::sample_uniform(&lb_0, &upper_bound);
159        let res_1 = Z::sample_uniform(&lb_1, &upper_bound);
160        let res_2 = Z::sample_uniform(&lb_2, &upper_bound);
161
162        assert!(res_0.is_err());
163        assert!(res_1.is_err());
164        assert!(res_2.is_err());
165    }
166
167    /// Checks whether `sample_uniform` is available for all types
168    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
169    #[test]
170    fn availability() {
171        let modulus = Modulus::from(7);
172        let z = Z::from(7);
173
174        let _ = Z::sample_uniform(0u16, 7u8);
175        let _ = Z::sample_uniform(0u32, 7u16);
176        let _ = Z::sample_uniform(0u64, 7u32);
177        let _ = Z::sample_uniform(0i8, 7u64);
178        let _ = Z::sample_uniform(0i16, 7i8);
179        let _ = Z::sample_uniform(0i32, 7i16);
180        let _ = Z::sample_uniform(0i64, 7i32);
181        let _ = Z::sample_uniform(&Z::ZERO, 7i64);
182        let _ = Z::sample_uniform(0u8, &modulus);
183        let _ = Z::sample_uniform(0, &z);
184    }
185
186    /// Roughly checks the uniformity of the distribution.
187    /// This test could possibly fail for a truly uniform distribution
188    /// with probability smaller than 1/1000.
189    #[test]
190    fn uniformity() {
191        let lower_bound = Z::ZERO;
192        let upper_bound = Z::from(5);
193        let mut counts = [0; 5];
194        // count sampled instances
195        for _ in 0..1000 {
196            let sample_z = Z::sample_uniform(&lower_bound, &upper_bound).unwrap();
197            let sample_int = i64::try_from(&sample_z).unwrap() as usize;
198            counts[sample_int] += 1;
199        }
200
201        // Check that every sampled integer was sampled roughly the same time
202        // this could possibly fail for true uniform randomness with probability
203        for count in counts {
204            assert!(count > 150, "This test can fail with probability close to 0. 
205            It fails if the sampled occurrences do not look like a typical uniform random distribution. 
206            If this happens, rerun the tests several times and check whether this issue comes up again.");
207        }
208    }
209}
210
211#[cfg(test)]
212mod test_sample_prime_uniform {
213    use crate::{integer::Z, integer_mod_q::Modulus};
214
215    /// Checks whether `sample_prime_uniform` outputs a prime sample every time.
216    #[test]
217    fn is_prime() {
218        for _ in 0..8 {
219            let sample = Z::sample_prime_uniform(20, i64::MAX).unwrap();
220            assert!(sample.is_prime(), "Can fail with probability ~2^-60.");
221        }
222    }
223
224    /// Checks whether `sample_prime_uniform` returns an error if
225    /// no prime exists in the specified interval.
226    #[test]
227    fn no_prime_exists() {
228        let res_0 = Z::sample_prime_uniform(14, 17);
229        // there is no prime between u64::MAX - 57 and u64::MAX
230        let res_1 = Z::sample_prime_uniform(u64::MAX - 57, u64::MAX);
231
232        assert!(res_0.is_err());
233        assert!(res_1.is_err());
234    }
235
236    /// Checks whether a negative lower bound result in an error.
237    #[test]
238    fn negative_lower_bound() {
239        let res_0 = Z::sample_prime_uniform(-1, 10);
240        let res_1 = Z::sample_prime_uniform(-200, 1);
241
242        assert!(res_0.is_err());
243        assert!(res_1.is_err());
244    }
245
246    /// Checks whether the boundaries of the interval are kept for small intervals.
247    #[test]
248    fn boundaries_kept_small() {
249        let lower_bound = Z::from(17);
250        let upper_bound = Z::from(32);
251        for _ in 0..32 {
252            let sample = Z::sample_prime_uniform(&lower_bound, &upper_bound).unwrap();
253            assert!(lower_bound <= sample);
254            assert!(sample < upper_bound);
255        }
256    }
257
258    /// Checks whether the boundaries of the interval are kept for large intervals.
259    #[test]
260    fn boundaries_kept_large() {
261        let lower_bound = Z::ZERO;
262        let upper_bound = Z::from(i64::MAX);
263        for _ in 0..256 {
264            let sample = Z::sample_prime_uniform(&lower_bound, &upper_bound).unwrap();
265            assert!(lower_bound <= sample);
266            assert!(sample < upper_bound);
267        }
268    }
269
270    /// Checks whether providing an invalid interval results in an error.
271    #[test]
272    fn invalid_interval() {
273        let lb_0 = Z::from(i64::MIN) - Z::ONE;
274        let lb_1 = Z::from(i64::MIN);
275        let lb_2 = Z::ZERO;
276        let upper_bound = Z::from(i64::MIN);
277
278        let res_0 = Z::sample_prime_uniform(&lb_0, &upper_bound);
279        let res_1 = Z::sample_prime_uniform(&lb_1, &upper_bound);
280        let res_2 = Z::sample_prime_uniform(&lb_2, &upper_bound);
281
282        assert!(res_0.is_err());
283        assert!(res_1.is_err());
284        assert!(res_2.is_err());
285    }
286
287    /// Checks whether `sample_prime_uniform` is available for types
288    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
289    #[test]
290    fn availability() {
291        let modulus = Modulus::from(7);
292        let z = Z::from(7);
293
294        let _ = Z::sample_prime_uniform(0u16, 7u8);
295        let _ = Z::sample_prime_uniform(0u32, 7u16);
296        let _ = Z::sample_prime_uniform(0u64, 7u32);
297        let _ = Z::sample_prime_uniform(0i8, 7u64);
298        let _ = Z::sample_prime_uniform(0i16, 7i8);
299        let _ = Z::sample_prime_uniform(0i32, 7i16);
300        let _ = Z::sample_prime_uniform(0i64, 7i32);
301        let _ = Z::sample_prime_uniform(&Z::ZERO, 7i64);
302        let _ = Z::sample_prime_uniform(0u8, &modulus);
303        let _ = Z::sample_prime_uniform(0, &z);
304    }
305}
qfall_math/integer/z/sample/uniform.rs

qfall_math/integer/z/sample/
uniform.rs
