qfall_math/integer/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 algorithms for sampling according to the uniform distribution.
10
11use crate::{
12    error::MathError, integer::Z, macros::seeded::seedable_function,
13    utils::sample::uniform::UniformIntegerSampler,
14};
15
16impl Z {
17    seedable_function!(
18        /// Chooses a [`Z`] instance uniformly at random
19        /// in `[lower_bound, upper_bound)`.
20        ///
21        /// The internally used uniform at random chosen bytes are generated
22        #[unseeded]
23        /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and is
24        #[seeded]
25        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed`, which uses ChaCha12 and is
26        #[optionally_seeded]
27        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed` or by [`ThreadRng`](rand::rngs::ThreadRng)
28        #[optionally_seeded]
29        /// if `seed` is `None`. Both use ChaCha12 and are
30        /// considered cryptographically secure.
31        ///
32        /// Parameters:
33        /// - `lower_bound`: specifies the included lower bound of the
34        ///   interval over which is sampled
35        /// - `upper_bound`: specifies the excluded upper bound of the
36        ///   interval over which is sampled
37        #[seeded]
38        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
39        #[optionally_seeded]
40        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
41        #[optionally_seeded]
42        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
43        ///
44        /// Returns a fresh [`Z`] instance with a
45        /// uniform random value in `[lower_bound, upper_bound)` or a [`MathError`]
46        /// if the provided interval was chosen too small.
47        ///
48        /// # Examples
49        /// ```
50        /// use qfall_math::integer::Z;
51        ///
52        #[unseeded]
53        /// let sample = Z::sample_uniform(17, 26).unwrap();
54        #[seeded]
55        /// let sample = Z::sample_uniform_seeded(17, 26, [42; 32]).unwrap();
56        /// ```
57        ///
58        /// # Errors and Failures
59        /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
60        ///   if the given `upper_bound` isn't at least larger than `lower_bound`.
61        pub(crate) fn sample_uniform(
62            lower_bound: impl Into<Z>,
63            upper_bound: impl Into<Z>,
64            seed: Option<[u8; 32]>,
65        ) -> Result<Self, MathError> {
66            let lower_bound: Z = lower_bound.into();
67            let upper_bound: Z = upper_bound.into();
68
69            let interval_size = &upper_bound - &lower_bound;
70            let mut uis = UniformIntegerSampler::init(&interval_size, seed)?;
71
72            let sample = uis.sample();
73            Ok(&lower_bound + sample)
74        }
75    );
76
77    seedable_function!(
78        /// Chooses a prime [`Z`] instance uniformly at random
79        /// in `[lower_bound, upper_bound)`. If after 2 * `n` steps, where `n` denotes the size of
80        /// the interval, no suitable prime was found, the algorithm aborts.
81        ///
82        /// The internally used uniform at random chosen bytes are generated
83        #[unseeded]
84        /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and is
85        #[seeded]
86        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed`, which uses ChaCha12 and is
87        #[optionally_seeded]
88        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed` or by [`ThreadRng`](rand::rngs::ThreadRng)
89        #[optionally_seeded]
90        /// if `seed` is `None`. Both use ChaCha12 and are
91        /// considered cryptographically secure.
92        ///
93        /// Parameters:
94        /// - `lower_bound`: specifies the included lower bound of the
95        ///   interval over which is sampled
96        /// - `upper_bound`: specifies the excluded upper bound of the
97        ///   interval over which is sampled
98        #[seeded]
99        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
100        #[optionally_seeded]
101        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
102        #[optionally_seeded]
103        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
104        ///
105        /// Returns a fresh [`Z`] instance with a
106        /// uniform random value in `[lower_bound, upper_bound)`. Otherwise, a [`MathError`]
107        /// if the provided interval was chosen too small, no prime could be found in the interval,
108        /// or the provided `lower_bound` was negative.
109        ///
110        /// # Examples
111        /// ```
112        /// use qfall_math::integer::Z;
113        ///
114        #[unseeded]
115        /// let prime = Z::sample_prime_uniform(1, 100).unwrap();
116        #[seeded]
117        /// let prime = Z::sample_prime_uniform_seeded(1, 100, [42; 32]).unwrap();
118        /// ```
119        ///
120        /// # Errors and Failures
121        /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
122        ///   if the given `upper_bound` isn't at least larger than `lower_bound`
123        ///   , or if no prime could be found in the specified interval.
124        /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
125        ///   if `lower_bound` is negative as primes are always positive.
126        pub(crate) fn sample_prime_uniform(
127            lower_bound: impl Into<Z>,
128            upper_bound: impl Into<Z>,
129            seed: Option<[u8; 32]>,
130        ) -> Result<Self, MathError> {
131            let lower_bound: Z = lower_bound.into();
132            let upper_bound: Z = upper_bound.into();
133
134            if lower_bound < Z::ZERO {
135                return Err(MathError::InvalidIntegerInput(format!(
136                    "Primes are always positive. Hence, sample_prime_uniform expects a positive lower_bound.
137                    The provided one is {lower_bound}.")));
138            }
139
140            let interval_size = &upper_bound - &lower_bound;
141            let mut uis = UniformIntegerSampler::init(&interval_size, seed)?;
142            let mut sample = &lower_bound + uis.sample();
143
144            // after 2 * size of interval many uniform random samples, a suitable prime should have been
145            // found with high probability, if there is one prime in the interval
146            let mut steps = 2 * &interval_size;
147            while !sample.is_prime() {
148                if steps == Z::ZERO {
149                    return Err(MathError::InvalidInterval(format!(
150                        "After sampling O({interval_size}) times uniform at random in the interval [{lower_bound}, {upper_bound}[
151                            no prime was found. It is very likely, that no prime exists in this interval.
152                            Please choose the interval larger.")));
153                }
154                sample = &lower_bound + uis.sample();
155                steps -= 1;
156            }
157
158            Ok(sample)
159        }
160    );
161}
162
163#[cfg(test)]
164mod test_sample_uniform {
165    use crate::utils::sample::test_seed;
166    use crate::{integer::Z, integer_mod_q::Modulus};
167
168    /// Checks whether the boundaries of the interval are kept for small intervals.
169    #[test]
170    fn boundaries_kept_small() {
171        for seeded in [false, true] {
172            let lower_bound = Z::from(17);
173            let upper_bound = Z::from(32);
174            for _ in 0..32 {
175                let sample = Z::sample_uniform_optionally_seeded(
176                    &lower_bound,
177                    &upper_bound,
178                    seeded.then(test_seed),
179                )
180                .unwrap();
181                assert!(lower_bound <= sample);
182                assert!(sample < upper_bound);
183            }
184        }
185    }
186
187    /// Checks whether the boundaries of the interval are kept for large intervals.
188    #[test]
189    fn boundaries_kept_large() {
190        for seeded in [false, true] {
191            let lower_bound = Z::from(i64::MIN) - Z::from(u64::MAX);
192            let upper_bound = Z::from(i64::MIN);
193            for _ in 0..256 {
194                let sample = Z::sample_uniform_optionally_seeded(
195                    &lower_bound,
196                    &upper_bound,
197                    seeded.then(test_seed),
198                )
199                .unwrap();
200                assert!(lower_bound <= sample);
201                assert!(sample < upper_bound);
202            }
203        }
204    }
205
206    /// Checks whether providing an invalid interval results in an error.
207    #[test]
208    fn invalid_interval() {
209        for seeded in [false, true] {
210            let lb_0 = Z::from(i64::MIN);
211            let lb_1 = Z::from(i64::MIN);
212            let lb_2 = Z::ZERO;
213            let upper_bound = Z::from(i64::MIN);
214
215            let res_0 =
216                Z::sample_uniform_optionally_seeded(&lb_0, &upper_bound, seeded.then(test_seed));
217            let res_1 =
218                Z::sample_uniform_optionally_seeded(&lb_1, &upper_bound, seeded.then(test_seed));
219            let res_2 =
220                Z::sample_uniform_optionally_seeded(&lb_2, &upper_bound, seeded.then(test_seed));
221
222            assert!(res_0.is_err());
223            assert!(res_1.is_err());
224            assert!(res_2.is_err());
225        }
226    }
227
228    /// Checks whether `sample_uniform` is available for all types
229    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
230    #[test]
231    fn availability() {
232        for seeded in [false, true] {
233            let modulus = Modulus::from(7);
234            let z = Z::from(7);
235
236            let _ = Z::sample_uniform_optionally_seeded(0u16, 7u8, seeded.then(test_seed));
237            let _ = Z::sample_uniform_optionally_seeded(0u32, 7u16, seeded.then(test_seed));
238            let _ = Z::sample_uniform_optionally_seeded(0u64, 7u32, seeded.then(test_seed));
239            let _ = Z::sample_uniform_optionally_seeded(0i8, 7u64, seeded.then(test_seed));
240            let _ = Z::sample_uniform_optionally_seeded(0i16, 7i8, seeded.then(test_seed));
241            let _ = Z::sample_uniform_optionally_seeded(0i32, 7i16, seeded.then(test_seed));
242            let _ = Z::sample_uniform_optionally_seeded(0i64, 7i32, seeded.then(test_seed));
243            let _ = Z::sample_uniform_optionally_seeded(&Z::ZERO, 7i64, seeded.then(test_seed));
244            let _ = Z::sample_uniform_optionally_seeded(0u8, &modulus, seeded.then(test_seed));
245            let _ = Z::sample_uniform_optionally_seeded(0, &z, seeded.then(test_seed));
246
247            // explicitly checks the existence of the unseeded and the seeded function
248            if seeded {
249                let _ = Z::sample_uniform_seeded(0u16, 7u8, test_seed());
250            } else {
251                let _ = Z::sample_uniform(0u16, 7u8);
252            }
253        }
254    }
255
256    /// Roughly checks the uniformity of the distribution.
257    /// This test could possibly fail for a truly uniform distribution
258    /// with probability smaller than 1/1000.
259    #[test]
260    fn uniformity() {
261        for seeded in [false, true] {
262            let lower_bound = Z::ZERO;
263            let upper_bound = Z::from(5);
264            let mut counts = [0; 5];
265            // count sampled instances
266            for _ in 0..1000 {
267                let sample_z = Z::sample_uniform_optionally_seeded(
268                    &lower_bound,
269                    &upper_bound,
270                    seeded.then(test_seed),
271                )
272                .unwrap();
273                let sample_int = i64::try_from(&sample_z).unwrap() as usize;
274                counts[sample_int] += 1;
275            }
276
277            // Check that every sampled integer was sampled roughly the same time
278            // this could possibly fail for true uniform randomness with probability
279            for count in counts {
280                assert!(count > 150, "This test can fail with probability close to 0. 
281            It fails if the sampled occurrences do not look like a typical uniform random distribution. 
282            If this happens, rerun the tests several times and check whether this issue comes up again.");
283            }
284        }
285    }
286
287    /// Checks whether the same seed results in the same sample.
288    #[test]
289    fn same_seed_same_sample() {
290        use crate::integer::Z;
291        let sample_0 = Z::sample_uniform_seeded(17, 26, [42; 32]).unwrap();
292        let sample_1 = Z::sample_uniform_seeded(17, 26, [42; 32]).unwrap();
293
294        assert_eq!(sample_0, sample_1);
295    }
296
297    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
298    #[test]
299    fn known_answer() {
300        use crate::integer::Z;
301        let sample = Z::sample_uniform_seeded(17, 26, [42; 32]).unwrap();
302
303        assert_eq!("19", sample.to_string());
304    }
305}
306
307#[cfg(test)]
308mod test_sample_prime_uniform {
309    use crate::utils::sample::test_seed;
310    use crate::{integer::Z, integer_mod_q::Modulus};
311
312    /// Checks whether `sample_prime_uniform` outputs a prime sample every time.
313    #[test]
314    fn is_prime() {
315        for seeded in [false, true] {
316            for _ in 0..8 {
317                let sample =
318                    Z::sample_prime_uniform_optionally_seeded(20, i64::MAX, seeded.then(test_seed))
319                        .unwrap();
320                assert!(sample.is_prime(), "Can fail with probability ~2^-60.");
321            }
322        }
323    }
324
325    /// Checks whether `sample_prime_uniform` returns an error if
326    /// no prime exists in the specified interval.
327    #[test]
328    fn no_prime_exists() {
329        for seeded in [false, true] {
330            let res_0 = Z::sample_prime_uniform_optionally_seeded(14, 17, seeded.then(test_seed));
331            // there is no prime between u64::MAX - 57 and u64::MAX
332            let res_1 = Z::sample_prime_uniform_optionally_seeded(
333                u64::MAX - 57,
334                u64::MAX,
335                seeded.then(test_seed),
336            );
337
338            assert!(res_0.is_err());
339            assert!(res_1.is_err());
340        }
341    }
342
343    /// Checks whether a negative lower bound result in an error.
344    #[test]
345    fn negative_lower_bound() {
346        for seeded in [false, true] {
347            let res_0 = Z::sample_prime_uniform_optionally_seeded(-1, 10, seeded.then(test_seed));
348            let res_1 = Z::sample_prime_uniform_optionally_seeded(-200, 1, seeded.then(test_seed));
349
350            assert!(res_0.is_err());
351            assert!(res_1.is_err());
352        }
353    }
354
355    /// Checks whether the boundaries of the interval are kept for small intervals.
356    #[test]
357    fn boundaries_kept_small() {
358        for seeded in [false, true] {
359            let lower_bound = Z::from(17);
360            let upper_bound = Z::from(32);
361            for _ in 0..32 {
362                let sample = Z::sample_prime_uniform_optionally_seeded(
363                    &lower_bound,
364                    &upper_bound,
365                    seeded.then(test_seed),
366                )
367                .unwrap();
368                assert!(lower_bound <= sample);
369                assert!(sample < upper_bound);
370            }
371        }
372    }
373
374    /// Checks whether the boundaries of the interval are kept for large intervals.
375    #[test]
376    fn boundaries_kept_large() {
377        for seeded in [false, true] {
378            let lower_bound = Z::ZERO;
379            let upper_bound = Z::from(i64::MAX);
380            for _ in 0..256 {
381                let sample = Z::sample_prime_uniform_optionally_seeded(
382                    &lower_bound,
383                    &upper_bound,
384                    seeded.then(test_seed),
385                )
386                .unwrap();
387                assert!(lower_bound <= sample);
388                assert!(sample < upper_bound);
389            }
390        }
391    }
392
393    /// Checks whether providing an invalid interval results in an error.
394    #[test]
395    fn invalid_interval() {
396        for seeded in [false, true] {
397            let lb_0 = Z::from(i64::MIN) - Z::ONE;
398            let lb_1 = Z::from(i64::MIN);
399            let lb_2 = Z::ZERO;
400            let upper_bound = Z::from(i64::MIN);
401
402            let res_0 = Z::sample_prime_uniform_optionally_seeded(
403                &lb_0,
404                &upper_bound,
405                seeded.then(test_seed),
406            );
407            let res_1 = Z::sample_prime_uniform_optionally_seeded(
408                &lb_1,
409                &upper_bound,
410                seeded.then(test_seed),
411            );
412            let res_2 = Z::sample_prime_uniform_optionally_seeded(
413                &lb_2,
414                &upper_bound,
415                seeded.then(test_seed),
416            );
417
418            assert!(res_0.is_err());
419            assert!(res_1.is_err());
420            assert!(res_2.is_err());
421        }
422    }
423
424    /// Checks whether `sample_prime_uniform` is available for types
425    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
426    #[test]
427    fn availability() {
428        for seeded in [false, true] {
429            let modulus = Modulus::from(7);
430            let z = Z::from(7);
431
432            let _ = Z::sample_prime_uniform_optionally_seeded(0u16, 7u8, seeded.then(test_seed));
433            let _ = Z::sample_prime_uniform_optionally_seeded(0u32, 7u16, seeded.then(test_seed));
434            let _ = Z::sample_prime_uniform_optionally_seeded(0u64, 7u32, seeded.then(test_seed));
435            let _ = Z::sample_prime_uniform_optionally_seeded(0i8, 7u64, seeded.then(test_seed));
436            let _ = Z::sample_prime_uniform_optionally_seeded(0i16, 7i8, seeded.then(test_seed));
437            let _ = Z::sample_prime_uniform_optionally_seeded(0i32, 7i16, seeded.then(test_seed));
438            let _ = Z::sample_prime_uniform_optionally_seeded(0i64, 7i32, seeded.then(test_seed));
439            let _ =
440                Z::sample_prime_uniform_optionally_seeded(&Z::ZERO, 7i64, seeded.then(test_seed));
441            let _ =
442                Z::sample_prime_uniform_optionally_seeded(0u8, &modulus, seeded.then(test_seed));
443            let _ = Z::sample_prime_uniform_optionally_seeded(0, &z, seeded.then(test_seed));
444
445            // explicitly checks the existence of the unseeded and the seeded function
446            if seeded {
447                let _ = Z::sample_prime_uniform_seeded(0u16, 7u8, test_seed());
448            } else {
449                let _ = Z::sample_prime_uniform(0u16, 7u8);
450            }
451        }
452    }
453
454    /// Checks whether the same seed results in the same sample.
455    #[test]
456    fn same_seed_same_sample() {
457        use crate::integer::Z;
458        let sample_0 = Z::sample_prime_uniform_seeded(1, 100, [42; 32]).unwrap();
459        let sample_1 = Z::sample_prime_uniform_seeded(1, 100, [42; 32]).unwrap();
460
461        assert_eq!(sample_0, sample_1);
462    }
463
464    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
465    #[test]
466    fn known_answer() {
467        use crate::integer::Z;
468        let sample = Z::sample_prime_uniform_seeded(1, 100, [42; 32]).unwrap();
469
470        assert_eq!("17", sample.to_string());
471    }
472}
qfall_math/integer/z/sample/uniform.rs

qfall_math/integer/z/sample/
uniform.rs
