qfall_math/integer/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 algorithms for sampling according to the uniform distribution.
10
11use crate::{
12    error::MathError,
13    integer::{PolyOverZ, Z},
14    traits::SetCoefficient,
15    utils::{index::evaluate_index, sample::uniform::UniformIntegerSampler},
16};
17use std::fmt::Display;
18
19impl PolyOverZ {
20    /// Generates a [`PolyOverZ`] instance of maximum degree `max_degree` and coefficients
21    /// 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    /// - `max_degree`: specifies the length of the polynomial,
29    ///   i.e. the number of coefficients
30    /// - `lower_bound`: specifies the included lower bound of the
31    ///   interval over which is sampled
32    /// - `upper_bound`: specifies the excluded upper bound of the
33    ///   interval over which is sampled
34    ///
35    /// Returns a fresh [`PolyOverZ`] instance of length `max_degree` with coefficients
36    /// chosen uniform at random in `[lower_bound, upper_bound)` or a [`MathError`]
37    /// if the `max_degree` was smaller than `0` or the provided interval was chosen too small.
38    ///
39    /// # Examples
40    /// ```
41    /// use qfall_math::integer::{PolyOverZ, Z};
42    ///
43    /// let sample = PolyOverZ::sample_uniform(3, 17, 26).unwrap();
44    /// ```
45    ///
46    /// # Errors and Failures
47    /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
48    ///   if the given `upper_bound` isn't at least larger than `lower_bound`.
49    /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
50    ///   the `max_degree` is negative or it does not fit into an [`i64`].
51    pub fn sample_uniform(
52        max_degree: impl TryInto<i64> + Display,
53        lower_bound: impl Into<Z>,
54        upper_bound: impl Into<Z>,
55    ) -> Result<Self, MathError> {
56        let max_degree = evaluate_index(max_degree)?;
57        let lower_bound: Z = lower_bound.into();
58        let upper_bound: Z = upper_bound.into();
59
60        let interval_size = &upper_bound - &lower_bound;
61        let mut uis = UniformIntegerSampler::init(&interval_size)?;
62
63        let mut poly_z = PolyOverZ::default();
64        for index in 0..=max_degree {
65            let sample = uis.sample();
66            unsafe { poly_z.set_coeff_unchecked(index, &lower_bound + sample) };
67        }
68        Ok(poly_z)
69    }
70}
71
72#[cfg(test)]
73mod test_sample_uniform {
74    use crate::{
75        integer::{PolyOverZ, Z},
76        integer_mod_q::Modulus,
77        traits::GetCoefficient,
78    };
79
80    /// Checks whether the boundaries of the interval are kept for small intervals.
81    #[test]
82    fn boundaries_kept_small() {
83        let lower_bound = Z::from(17);
84        let upper_bound = Z::from(32);
85        let poly_z = PolyOverZ::sample_uniform(32, &lower_bound, &upper_bound).unwrap();
86
87        for i in 0..32 {
88            let sample = poly_z.get_coeff(i).unwrap();
89            assert!(lower_bound <= sample);
90            assert!(sample < upper_bound);
91        }
92    }
93
94    /// Checks whether the boundaries of the interval are kept for large intervals.
95    #[test]
96    fn boundaries_kept_large() {
97        let lower_bound = Z::from(i64::MIN) - Z::from(u64::MAX);
98        let upper_bound = Z::from(i64::MIN);
99
100        let poly_z = PolyOverZ::sample_uniform(256, &lower_bound, &upper_bound).unwrap();
101
102        for i in 0..256 {
103            let sample = poly_z.get_coeff(i).unwrap();
104            assert!(lower_bound <= sample);
105            assert!(sample < upper_bound);
106        }
107    }
108
109    /// Checks whether the number of coefficients is correct.
110    #[test]
111    fn nr_coeffs() {
112        let degrees = [1, 3, 7, 15, 32, 120];
113        for degree in degrees {
114            let res = PolyOverZ::sample_uniform(degree, 1, 15).unwrap();
115
116            assert_eq!(degree, res.get_degree());
117        }
118    }
119
120    /// Checks whether providing an invalid interval results in an error.
121    #[test]
122    fn invalid_interval() {
123        let lb_0 = Z::from(i64::MIN);
124        let lb_1 = Z::from(i64::MIN);
125        let lb_2 = Z::ZERO;
126        let upper_bound = Z::from(i64::MIN);
127
128        let res_0 = PolyOverZ::sample_uniform(1, &lb_0, &upper_bound);
129        let res_1 = PolyOverZ::sample_uniform(1, &lb_1, &upper_bound);
130        let res_2 = PolyOverZ::sample_uniform(1, &lb_2, &upper_bound);
131
132        assert!(res_0.is_err());
133        assert!(res_1.is_err());
134        assert!(res_2.is_err());
135    }
136
137    /// Checks whether providing a length smaller than `0` results in an error.
138    #[test]
139    fn invalid_max_degree() {
140        let lower_bound = Z::from(0);
141        let upper_bound = Z::from(15);
142
143        let res_0 = PolyOverZ::sample_uniform(-1, &lower_bound, &upper_bound);
144        let res_1 = PolyOverZ::sample_uniform(i64::MIN, &lower_bound, &upper_bound);
145
146        assert!(res_0.is_err());
147        assert!(res_1.is_err());
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        let modulus = Modulus::from(7);
155        let z = Z::from(7);
156
157        let _ = PolyOverZ::sample_uniform(1u64, 0u16, 7u8);
158        let _ = PolyOverZ::sample_uniform(1i64, 0u32, 7u16);
159        let _ = PolyOverZ::sample_uniform(1u8, 0u64, 7u32);
160        let _ = PolyOverZ::sample_uniform(1u16, 0i8, 7u64);
161        let _ = PolyOverZ::sample_uniform(1u32, 0i16, 7i8);
162        let _ = PolyOverZ::sample_uniform(1i32, 0i32, 7i16);
163        let _ = PolyOverZ::sample_uniform(1i16, 0i64, 7i32);
164        let _ = PolyOverZ::sample_uniform(1i8, &Z::ZERO, 7i64);
165        let _ = PolyOverZ::sample_uniform(1, 0u8, &modulus);
166        let _ = PolyOverZ::sample_uniform(1, 0, &z);
167    }
168}
qfall_math/integer/poly_over_z/sample/uniform.rs

qfall_math/integer/poly_over_z/sample/
uniform.rs
