qfall_math/integer_mod_q/poly_over_zq/sample/binomial.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
10//! according to the binomial distribution.
11
12use crate::{
13 error::MathError,
14 integer::Z,
15 integer_mod_q::{Modulus, PolyOverZq},
16 rational::Q,
17 traits::SetCoefficient,
18 utils::{index::evaluate_index, sample::binomial::BinomialSampler},
19};
20use std::fmt::Display;
21
22impl PolyOverZq {
23 /// Generates a [`PolyOverZq`] instance of maximum degree `max_degree` and
24 /// coefficients chosen according to the binomial distribution
25 /// parameterized by `n` and `p`.
26 ///
27 /// Parameters:
28 /// - `max_degree`: specifies the length of the polynomial,
29 /// i.e. the number of coefficients
30 /// - `modulus`: specifies the [`Modulus`] of the new [`PolyOverZq`] instance
31 /// - `n`: specifies the number of trials
32 /// - `p`: specifies the probability of success
33 ///
34 /// Returns a fresh [`PolyOverZq`] instance with each value sampled
35 /// according to the binomial distribution or a [`MathError`]
36 /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
37 /// or `max_degree` is negative or does not into an [`i64`].
38 ///
39 /// # Examples
40 /// ```
41 /// use qfall_math::integer_mod_q::PolyOverZq;
42 ///
43 /// let sample = PolyOverZq::sample_binomial(2, 7, 2, 0.5).unwrap();
44 /// ```
45 ///
46 /// # Errors and Failures
47 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
48 /// if `n < 0`.
49 /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
50 /// if `p ∉ (0,1)`.
51 /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
52 /// if `n` does not fit into an [`i64`].
53 /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
54 /// the `max_degree` is negative or it does not fit into an [`i64`].
55 pub fn sample_binomial(
56 max_degree: impl TryInto<i64> + Display,
57 modulus: impl Into<Modulus>,
58 n: impl Into<Z>,
59 p: impl Into<Q>,
60 ) -> Result<Self, MathError> {
61 Self::sample_binomial_with_offset(max_degree, 0, modulus, n, p)
62 }
63
64 /// Generates a [`PolyOverZq`] instance of maximum degree `max_degree` and
65 /// coefficients chosen according to the binomial distribution
66 /// parameterized by `n` and `p` with given `offset`.
67 ///
68 /// Parameters:
69 /// - `max_degree`: specifies the length of the polynomial,
70 /// i.e. the number of coefficients
71 /// - `offset`: specifies an offset applied to each sample
72 /// collected from the binomial distribution
73 /// - `modulus`: specifies the [`Modulus`] of the new [`PolyOverZq`] instance
74 /// - `n`: specifies the number of trials
75 /// - `p`: specifies the probability of success
76 ///
77 /// Returns a fresh [`PolyOverZq`] instance with each value sampled
78 /// according to the binomial distribution or a [`MathError`]
79 /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`],
80 /// or `max_degree` is negative or does not into an [`i64`].
81 ///
82 /// # Examples
83 /// ```
84 /// use qfall_math::integer_mod_q::PolyOverZq;
85 ///
86 /// let sample = PolyOverZq::sample_binomial_with_offset(2, -1, 7, 2, 0.5).unwrap();
87 /// ```
88 ///
89 /// # Errors and Failures
90 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
91 /// if `n < 0`.
92 /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
93 /// if `p ∉ (0,1)`.
94 /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
95 /// if `n` does not fit into an [`i64`].
96 /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
97 /// the `max_degree` is negative or it does not fit into an [`i64`].
98 ///
99 /// # Panics ...
100 /// - if `modulus` is smaller than `2`.
101 pub fn sample_binomial_with_offset(
102 max_degree: impl TryInto<i64> + Display,
103 offset: impl Into<Z>,
104 modulus: impl Into<Modulus>,
105 n: impl Into<Z>,
106 p: impl Into<Q>,
107 ) -> Result<Self, MathError> {
108 let max_degree = evaluate_index(max_degree)?;
109 let offset: Z = offset.into();
110 let modulus: Modulus = modulus.into();
111 let mut bin_sampler = BinomialSampler::init(n, p)?;
112
113 let mut poly_z = PolyOverZq::from(&modulus);
114
115 for index in 0..=max_degree {
116 let mut sample = bin_sampler.sample();
117 sample += &offset;
118 unsafe { poly_z.set_coeff_unchecked(index, sample) };
119 }
120
121 Ok(poly_z)
122 }
123}
124
125#[cfg(test)]
126mod test_sample_binomial {
127 use super::{PolyOverZq, Q, Z};
128 use crate::traits::GetCoefficient;
129
130 // As all major tests regarding an appropriate binomial distribution,
131 // whether the correct interval is kept, and if the errors are thrown correctly,
132 // are performed in the `utils` module, we omit these tests here.
133
134 /// Checks whether the boundaries of the interval are kept.
135 #[test]
136 fn boundaries_kept() {
137 for _ in 0..8 {
138 let poly = PolyOverZq::sample_binomial(0, 7, 2, 0.5).unwrap();
139 let sample: Z = poly.get_coeff(0).unwrap();
140 assert!(Z::ZERO <= sample || sample <= 2);
141 }
142 }
143
144 /// Checks whether the number of coefficients is correct.
145 #[test]
146 fn nr_coeffs() {
147 let degrees = [1, 3, 7, 15, 32, 120];
148 for degree in degrees {
149 let res = PolyOverZq::sample_binomial(degree, u64::MAX, 256, 0.99999).unwrap();
150
151 assert_eq!(
152 degree,
153 res.get_degree(),
154 "This test can fail with probability close to 0."
155 );
156 }
157 }
158
159 /// Checks whether providing a length smaller than `0` results in an error.
160 #[test]
161 fn invalid_max_degree() {
162 let res_0 = PolyOverZq::sample_binomial(-1, 7, 2, 0.5);
163 let res_1 = PolyOverZq::sample_binomial(i64::MIN, 7, 2, 0.5);
164
165 assert!(res_0.is_err());
166 assert!(res_1.is_err());
167 }
168
169 /// Checks whether `sample_binomial` is available for all types
170 /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
171 /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
172 #[test]
173 fn availability() {
174 let _ = PolyOverZq::sample_binomial(1, 7u8, 1u16, 7u8);
175 let _ = PolyOverZq::sample_binomial(1, 7u16, 1u32, 7u16);
176 let _ = PolyOverZq::sample_binomial(1, 7u32, 1u64, 7u32);
177 let _ = PolyOverZq::sample_binomial(1, 7u64, 1i8, 7u64);
178 let _ = PolyOverZq::sample_binomial(1, 7i8, 1i16, 7i8);
179 let _ = PolyOverZq::sample_binomial(1, 7i16, 1i32, 7i16);
180 let _ = PolyOverZq::sample_binomial(1, 7i32, 1i64, 7i32);
181 let _ = PolyOverZq::sample_binomial(1, 7i64, Z::ONE, 7i64);
182 let _ = PolyOverZq::sample_binomial(1, 7, 1u8, 0.5f32);
183 let _ = PolyOverZq::sample_binomial(1, 7, 1u8, 0.5f64);
184 let _ = PolyOverZq::sample_binomial(1, 7, 1, Q::from((1, 2)));
185 }
186}
187
188#[cfg(test)]
189mod test_sample_binomial_with_offset {
190 use super::{PolyOverZq, Q, Z};
191 use crate::traits::GetCoefficient;
192
193 // As all major tests regarding an appropriate binomial distribution,
194 // whether the correct interval is kept, and if the errors are thrown correctly,
195 // are performed in the `utils` module, we omit these tests here.
196
197 /// Checks whether the boundaries of the interval are kept.
198 #[test]
199 fn boundaries_kept() {
200 for _ in 0..8 {
201 let poly = PolyOverZq::sample_binomial_with_offset(0, -1, 7, 2, 0.5).unwrap();
202 let sample: Z = poly.get_coeff(0).unwrap();
203 assert!(Z::MINUS_ONE <= sample || sample <= Z::ONE);
204 }
205 }
206
207 /// Checks whether the number of coefficients is correct.
208 #[test]
209 fn nr_coeffs() {
210 let degrees = [1, 3, 7, 15, 32, 120];
211 for degree in degrees {
212 let res = PolyOverZq::sample_binomial_with_offset(degree, 1, 7, 2, 0.5).unwrap();
213
214 assert_eq!(degree, res.get_degree());
215 }
216 }
217
218 /// Checks whether providing a length smaller than `0` results in an error.
219 #[test]
220 fn invalid_max_degree() {
221 let res_0 = PolyOverZq::sample_binomial_with_offset(-1, -1, 7, 2, 0.5);
222 let res_1 = PolyOverZq::sample_binomial_with_offset(i64::MIN, -1, 7, 2, 0.5);
223
224 assert!(res_0.is_err());
225 assert!(res_1.is_err());
226 }
227
228 /// Checks whether `sample_binomial_with_offset` is available for all types
229 /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
230 /// and [`Into<Q>`], i.e. u8, u16, i8, i16, f32, f64, ...
231 #[test]
232 fn availability() {
233 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7u8, 1u16, 7u8);
234 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7u16, 1u32, 7u16);
235 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7u32, 1u64, 7u32);
236 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7u64, 1i8, 7u64);
237 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7i8, 1i16, 7i8);
238 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7i16, 1i32, 7i16);
239 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7i32, 1i64, 7i32);
240 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7i64, Z::ONE, 7i64);
241 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7, 1u8, 0.5f32);
242 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7, 1u8, 0.5f64);
243 let _ = PolyOverZq::sample_binomial_with_offset(1, 0, 7, 1, Q::from((1, 2)));
244 }
245}