qfall_math/integer/poly_over_z/sample/
discrete_gauss.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
10//! to the discrete Gaussian distribution.
11
12use crate::{
13    error::MathError,
14    integer::PolyOverZ,
15    rational::Q,
16    traits::SetCoefficient,
17    utils::{
18        index::evaluate_index,
19        sample::discrete_gauss::{DiscreteGaussianIntegerSampler, LookupTableSetting, TAILCUT},
20    },
21};
22use std::fmt::Display;
23
24impl PolyOverZ {
25    /// Initializes a new [`PolyOverZ`] with maximum degree `max_degree`
26    /// and with each entry sampled independently according to the
27    /// discrete Gaussian distribution, using [`Z::sample_discrete_gauss`](crate::integer::Z::sample_discrete_gauss).
28    ///
29    /// Parameters:
30    /// - `max_degree`: specifies the included maximal degree the created [`PolyOverZ`] should have
31    /// - `center`: specifies the positions of the center with peak probability
32    /// - `s`: specifies the Gaussian parameter, which is proportional
33    ///   to the standard deviation `sigma * sqrt(2 * pi) = s`
34    ///
35    /// Returns a fresh [`PolyOverZ`] instance of maximum degree `max_degree`
36    /// with coefficients chosen independently according the discrete Gaussian distribution or
37    /// a [`MathError`] if `s < 0`.
38    ///
39    /// # Examples
40    /// ```
41    /// use qfall_math::integer::PolyOverZ;
42    ///
43    /// let sample = PolyOverZ::sample_discrete_gauss(2, 0, 1).unwrap();
44    /// ```
45    ///
46    /// # Errors and Failures
47    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
48    ///   if `s < 0`.
49    ///
50    /// # Panics ...
51    /// - if `max_degree` is negative, or does not fit into an [`i64`].
52    pub fn sample_discrete_gauss(
53        max_degree: impl TryInto<i64> + Display,
54        center: impl Into<Q>,
55        s: impl Into<Q>,
56    ) -> Result<Self, MathError> {
57        let max_degree = evaluate_index(max_degree).unwrap();
58
59        let center = center.into();
60        let s = s.into();
61        let mut poly = PolyOverZ::default();
62
63        let mut dgis = DiscreteGaussianIntegerSampler::init(
64            &center,
65            &s,
66            unsafe { TAILCUT },
67            LookupTableSetting::FillOnTheFly,
68        )?;
69
70        for index in 0..=max_degree {
71            let sample = dgis.sample_z();
72            unsafe { poly.set_coeff_unchecked(index, &sample) };
73        }
74        Ok(poly)
75    }
76}
77
78#[cfg(test)]
79mod test_sample_discrete_gauss {
80    use crate::{integer::PolyOverZ, rational::Q};
81
82    /// Checks whether `sample_discrete_gauss` is available for all types
83    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
84    /// or [`Into<Q>`], i.e. u8, i16, f32, Z, Q, ...
85    #[test]
86    fn availability() {
87        let center = Q::ZERO;
88        let s = Q::ONE;
89
90        let _ = PolyOverZ::sample_discrete_gauss(1u8, 0f32, 1u8);
91        let _ = PolyOverZ::sample_discrete_gauss(1u16, 0f64, 1u16);
92        let _ = PolyOverZ::sample_discrete_gauss(1u32, 0f32, 1u32);
93        let _ = PolyOverZ::sample_discrete_gauss(1u64, 0f64, 1u64);
94        let _ = PolyOverZ::sample_discrete_gauss(1i8, 0f32, 1i8);
95        let _ = PolyOverZ::sample_discrete_gauss(1i8, 0f32, 1i16);
96        let _ = PolyOverZ::sample_discrete_gauss(1i16, 0f32, 1i32);
97        let _ = PolyOverZ::sample_discrete_gauss(1i32, 0f64, 1i64);
98        let _ = PolyOverZ::sample_discrete_gauss(1i64, center, s);
99        let _ = PolyOverZ::sample_discrete_gauss(1u8, 0f32, 1f64);
100    }
101
102    /// Checks whether the number of coefficients is correct.
103    #[test]
104    fn nr_coeffs() {
105        let degrees = [1, 3, 7, 15, 32, 120];
106        for degree in degrees {
107            let res = PolyOverZ::sample_discrete_gauss(degree, i64::MAX, 1).unwrap();
108
109            assert_eq!(
110                res.get_degree(),
111                degree,
112                "Could fail with negligible probability."
113            );
114        }
115    }
116
117    /// Checks whether the maximum degree needs to be at least 0.
118    #[test]
119    #[should_panic]
120    fn invalid_max_degree() {
121        let _ = PolyOverZ::sample_discrete_gauss(-1, 0, 1).unwrap();
122    }
123}
qfall_math/integer/poly_over_z/sample/discrete_gauss.rs

qfall_math/integer/poly_over_z/sample/
discrete_gauss.rs
