qfall_math/integer_mod_q/polynomial_ring_zq/sample/binomial.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
10//! according to the binomial distribution.
11
12use crate::{
13 error::MathError,
14 integer::{PolyOverZ, Z},
15 integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
16 macros::seeded::seedable_function,
17 rational::Q,
18};
19
20impl PolynomialRingZq {
21 seedable_function!(
22 /// Generates a [`PolynomialRingZq`] instance of maximum degree `modulus.get_degree() - 1` and
23 /// coefficients chosen according to the binomial distribution
24 /// parameterized by `n` and `p`.
25 ///
26 /// Parameters:
27 /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
28 /// ring of polynomials modulo `modulus.get_q()` is defined
29 /// - `n`: specifies the number of trials
30 /// - `p`: specifies the probability of success
31 #[seeded]
32 /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
33 #[optionally_seeded]
34 /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
35 #[optionally_seeded]
36 /// If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
37 ///
38 /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
39 /// with coefficients chosen according to the binomial distribution or a [`MathError`]
40 /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`].
41 ///
42 /// # Examples
43 /// ```
44 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
45 /// use std::str::FromStr;
46 /// let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
47 ///
48 #[unseeded]
49 /// let sample = PolynomialRingZq::sample_binomial(&modulus, 2, 0.5).unwrap();
50 #[seeded]
51 /// let sample = PolynomialRingZq::sample_binomial_seeded(&modulus, 2, 0.5, [42; 32]).unwrap();
52 /// ```
53 ///
54 /// # Errors and Failures
55 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
56 /// if `n < 0`.
57 /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
58 /// if `p ∉ (0,1)`.
59 /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
60 /// if `n` does not fit into an [`i64`].
61 ///
62 /// # Panics ...
63 /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
64 pub(crate) fn sample_binomial(
65 modulus: &ModulusPolynomialRingZq,
66 n: impl Into<Z>,
67 p: impl Into<Q>,
68 seed: Option<[u8; 32]>,
69 ) -> Result<Self, MathError> {
70 Self::sample_binomial_with_offset_optionally_seeded(modulus, 0, n, p, seed)
71 }
72 );
73
74 seedable_function!(
75 /// Generates a [`PolynomialRingZq`] instance of maximum degree `modulus.get_degree() - 1` and
76 /// coefficients chosen according to the binomial distribution
77 /// parameterized by `n` and `p` with given `offset`.
78 ///
79 /// Parameters:
80 /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
81 /// ring of polynomials modulo `modulus.get_q()` is defined
82 /// - `offset`: specifies an offset applied to each sample
83 /// collected from the binomial distribution
84 /// - `n`: specifies the number of trials
85 /// - `p`: specifies the probability of success
86 #[seeded]
87 /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
88 #[optionally_seeded]
89 /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
90 #[optionally_seeded]
91 /// If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
92 ///
93 /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
94 /// with coefficients chosen according to the binomial distribution or a [`MathError`]
95 /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`].
96 ///
97 /// # Examples
98 /// ```
99 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
100 /// use std::str::FromStr;
101 /// let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
102 ///
103 #[unseeded]
104 /// let sample = PolynomialRingZq::sample_binomial_with_offset(&modulus, -1, 2, 0.5).unwrap();
105 #[seeded]
106 /// let sample = PolynomialRingZq::sample_binomial_with_offset_seeded(&modulus, -1, 2, 0.5, [42; 32]).unwrap();
107 /// ```
108 ///
109 /// # Errors and Failures
110 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
111 /// if `n < 0`.
112 /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
113 /// if `p ∉ (0,1)`.
114 /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
115 /// if `n` does not fit into an [`i64`].
116 ///
117 /// # Panics ...
118 /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
119 pub(crate) fn sample_binomial_with_offset(
120 modulus: &ModulusPolynomialRingZq,
121 offset: impl Into<Z>,
122 n: impl Into<Z>,
123 p: impl Into<Q>,
124 seed: Option<[u8; 32]>,
125 ) -> Result<Self, MathError> {
126 assert!(
127 modulus.get_degree() > 0,
128 "ModulusPolynomial of degree 0 is insufficient to sample over."
129 );
130
131 let poly_z = PolyOverZ::sample_binomial_with_offset_optionally_seeded(
132 modulus.get_degree() - 1,
133 offset,
134 n,
135 p,
136 seed,
137 )?;
138
139 Ok(PolynomialRingZq {
140 poly: poly_z,
141 modulus: modulus.clone(),
142 })
143 }
144 );
145}
146
147#[cfg(test)]
148mod test_sample_binomial {
149 use super::{PolynomialRingZq, Z};
150 use crate::utils::sample::test_seed;
151 use crate::{
152 integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq},
153 traits::{GetCoefficient, SetCoefficient},
154 };
155 use std::str::FromStr;
156
157 // As all major tests regarding an appropriate binomial distribution,
158 // whether the correct interval is kept, and if the errors are thrown correctly,
159 // are performed in the `utils` module, we omit these tests here.
160
161 /// Checks whether the boundaries of the interval are kept.
162 #[test]
163 fn boundaries_kept() {
164 for seeded in [false, true] {
165 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
166
167 for _ in 0..8 {
168 let poly = PolynomialRingZq::sample_binomial_optionally_seeded(
169 &modulus,
170 2,
171 0.5,
172 seeded.then(test_seed),
173 )
174 .unwrap();
175 let sample: Z = poly.get_coeff(0).unwrap();
176 assert!(Z::ZERO <= sample || sample <= 2);
177 }
178 }
179 }
180
181 /// Checks whether the number of coefficients is correct.
182 #[test]
183 fn nr_coeffs() {
184 for seeded in [false, true] {
185 let degrees = [1, 3, 7, 15, 32, 120];
186 for degree in degrees {
187 let mut modulus = PolyOverZq::from((1, u64::MAX));
188 modulus.set_coeff(degree, 1).unwrap();
189 let modulus = ModulusPolynomialRingZq::from(&modulus);
190
191 let res = PolynomialRingZq::sample_binomial_optionally_seeded(
192 &modulus,
193 256,
194 0.99999,
195 seeded.then(test_seed),
196 )
197 .unwrap();
198
199 assert_eq!(
200 modulus.get_degree(),
201 res.get_degree() + 1,
202 "This test can fail with probability close to 0."
203 );
204 }
205 }
206 }
207
208 /// Checks whether 0 modulus polynomial is insufficient.
209 #[test]
210 fn invalid_modulus() {
211 for seeded in [false, true] {
212 let result = std::panic::catch_unwind(|| {
213 let modulus = ModulusPolynomialRingZq::from_str("1 1 mod 17").unwrap();
214
215 let _ = PolynomialRingZq::sample_binomial_optionally_seeded(
216 &modulus,
217 2,
218 0.5,
219 seeded.then(test_seed),
220 );
221 });
222 assert!(result.is_err());
223 }
224 }
225
226 /// Checks whether the same seed results in the same sample.
227 #[test]
228 fn same_seed_same_sample() {
229 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
230 use std::str::FromStr;
231 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
232 let sample_0 =
233 PolynomialRingZq::sample_binomial_seeded(&modulus, 2, 0.5, [42; 32]).unwrap();
234 let sample_1 =
235 PolynomialRingZq::sample_binomial_seeded(&modulus, 2, 0.5, [42; 32]).unwrap();
236
237 assert_eq!(sample_0, sample_1);
238 }
239
240 /// Checks whether the seeded variant outputs the known sample for a fixed seed.
241 #[test]
242 fn known_answer() {
243 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
244 use std::str::FromStr;
245 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
246 let sample = PolynomialRingZq::sample_binomial_seeded(&modulus, 2, 0.5, [42; 32]).unwrap();
247
248 assert_eq!("2 0 2 / 3 1 2 1 mod 17", sample.to_string());
249 }
250
251 /// Checks whether the unseeded and the seeded function are available.
252 #[test]
253 fn availability() {
254 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
255 use std::str::FromStr;
256 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
257
258 // explicitly checks the existence of the unseeded and the seeded function
259 let _ = PolynomialRingZq::sample_binomial(&modulus, 2, 0.5);
260 let _ = PolynomialRingZq::sample_binomial_seeded(&modulus, 2, 0.5, test_seed());
261 }
262}
263
264#[cfg(test)]
265mod test_sample_binomial_with_offset {
266 use super::{PolynomialRingZq, Z};
267 use crate::utils::sample::test_seed;
268 use crate::{
269 integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq},
270 traits::{GetCoefficient, SetCoefficient},
271 };
272 use std::str::FromStr;
273
274 // As all major tests regarding an appropriate binomial distribution,
275 // whether the correct interval is kept, and if the errors are thrown correctly,
276 // are performed in the `utils` module, we omit these tests here.
277
278 /// Checks whether the boundaries of the interval are kept.
279 #[test]
280 fn boundaries_kept() {
281 for seeded in [false, true] {
282 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
283
284 for _ in 0..8 {
285 let poly = PolynomialRingZq::sample_binomial_with_offset_optionally_seeded(
286 &modulus,
287 -1,
288 2,
289 0.5,
290 seeded.then(test_seed),
291 )
292 .unwrap();
293 let sample: Z = poly.get_coeff(0).unwrap();
294 assert!(Z::MINUS_ONE <= sample || sample <= Z::ONE);
295 }
296 }
297 }
298
299 /// Checks whether the number of coefficients is correct.
300 #[test]
301 fn nr_coeffs() {
302 for seeded in [false, true] {
303 let degrees = [1, 3, 7, 15, 32, 120];
304 for degree in degrees {
305 let mut modulus = PolyOverZq::from((1, u64::MAX));
306 modulus.set_coeff(degree, 1).unwrap();
307 let modulus = ModulusPolynomialRingZq::from(&modulus);
308
309 let res = PolynomialRingZq::sample_binomial_with_offset_optionally_seeded(
310 &modulus,
311 1,
312 2,
313 0.5,
314 seeded.then(test_seed),
315 )
316 .unwrap();
317
318 assert_eq!(modulus.get_degree(), res.get_degree() + 1);
319 }
320 }
321 }
322
323 /// Checks whether 0 modulus polynomial is insufficient.
324 #[test]
325 fn invalid_modulus() {
326 for seeded in [false, true] {
327 let result = std::panic::catch_unwind(|| {
328 let modulus = ModulusPolynomialRingZq::from_str("1 1 mod 17").unwrap();
329
330 let _ = PolynomialRingZq::sample_binomial_with_offset_optionally_seeded(
331 &modulus,
332 -1,
333 2,
334 0.5,
335 seeded.then(test_seed),
336 );
337 });
338 assert!(result.is_err());
339 }
340 }
341
342 /// Checks whether the same seed results in the same sample.
343 #[test]
344 fn same_seed_same_sample() {
345 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
346 use std::str::FromStr;
347 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
348 let sample_0 =
349 PolynomialRingZq::sample_binomial_with_offset_seeded(&modulus, -1, 2, 0.5, [42; 32])
350 .unwrap();
351 let sample_1 =
352 PolynomialRingZq::sample_binomial_with_offset_seeded(&modulus, -1, 2, 0.5, [42; 32])
353 .unwrap();
354
355 assert_eq!(sample_0, sample_1);
356 }
357
358 /// Checks whether the seeded variant outputs the known sample for a fixed seed.
359 #[test]
360 fn known_answer() {
361 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
362 use std::str::FromStr;
363 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
364 let sample =
365 PolynomialRingZq::sample_binomial_with_offset_seeded(&modulus, -1, 2, 0.5, [42; 32])
366 .unwrap();
367
368 assert_eq!("2 -1 1 / 3 1 2 1 mod 17", sample.to_string());
369 }
370
371 /// Checks whether the unseeded and the seeded function are available.
372 #[test]
373 fn availability() {
374 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
375 use std::str::FromStr;
376 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
377
378 // explicitly checks the existence of the unseeded and the seeded function
379 let _ = PolynomialRingZq::sample_binomial_with_offset(&modulus, -1, 2, 0.5);
380 let _ =
381 PolynomialRingZq::sample_binomial_with_offset_seeded(&modulus, -1, 2, 0.5, test_seed());
382 }
383}