qfall_math/integer_mod_q/polynomial_ring_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::{PolyOverZ, Z},
15 integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
16 rational::Q,
17};
18
19impl PolynomialRingZq {
20 /// Generates a [`PolynomialRingZq`] instance of maximum degree `modulus.get_degree() - 1` and
21 /// coefficients chosen according to the binomial distribution
22 /// parameterized by `n` and `p`.
23 ///
24 /// Parameters:
25 /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
26 /// ring of polynomials modulo `modulus.get_q()` is defined
27 /// - `n`: specifies the number of trials
28 /// - `p`: specifies the probability of success
29 ///
30 /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
31 /// with coefficients chosen according to the binomial distribution or a [`MathError`]
32 /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`].
33 ///
34 /// # Examples
35 /// ```
36 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
37 /// use std::str::FromStr;
38 /// let modulus = ModulusPolynomialRingZq::from_str("3 1 2 3 mod 17").unwrap();
39 ///
40 /// let sample = PolynomialRingZq::sample_binomial(&modulus, 2, 0.5).unwrap();
41 /// ```
42 ///
43 /// # Errors and Failures
44 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
45 /// if `n < 0`.
46 /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
47 /// if `p ∉ (0,1)`.
48 /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
49 /// if `n` does not fit into an [`i64`].
50 ///
51 /// # Panics ...
52 /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
53 pub fn sample_binomial(
54 modulus: &ModulusPolynomialRingZq,
55 n: impl Into<Z>,
56 p: impl Into<Q>,
57 ) -> Result<Self, MathError> {
58 Self::sample_binomial_with_offset(modulus, 0, n, p)
59 }
60
61 /// Generates a [`PolynomialRingZq`] instance of maximum degree `modulus.get_degree() - 1` and
62 /// coefficients chosen according to the binomial distribution
63 /// parameterized by `n` and `p` with given `offset`.
64 ///
65 /// Parameters:
66 /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
67 /// ring of polynomials modulo `modulus.get_q()` is defined
68 /// - `offset`: specifies an offset applied to each sample
69 /// collected from the binomial distribution
70 /// - `n`: specifies the number of trials
71 /// - `p`: specifies the probability of success
72 ///
73 /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
74 /// with coefficients chosen according to the binomial distribution or a [`MathError`]
75 /// if `n < 0`, `p ∉ (0,1)`, `n` does not fit into an [`i64`].
76 ///
77 /// # Examples
78 /// ```
79 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
80 /// use std::str::FromStr;
81 /// let modulus = ModulusPolynomialRingZq::from_str("3 1 2 3 mod 17").unwrap();
82 ///
83 /// let sample = PolynomialRingZq::sample_binomial_with_offset(&modulus, -1, 2, 0.5).unwrap();
84 /// ```
85 ///
86 /// # Errors and Failures
87 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
88 /// if `n < 0`.
89 /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
90 /// if `p ∉ (0,1)`.
91 /// - Returns a [`MathError`] of type [`ConversionError`](MathError::ConversionError)
92 /// if `n` does not fit into an [`i64`].
93 ///
94 /// # Panics ...
95 /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
96 pub fn sample_binomial_with_offset(
97 modulus: &ModulusPolynomialRingZq,
98 offset: impl Into<Z>,
99 n: impl Into<Z>,
100 p: impl Into<Q>,
101 ) -> Result<Self, MathError> {
102 assert!(
103 modulus.get_degree() > 0,
104 "ModulusPolynomial of degree 0 is insufficient to sample over."
105 );
106
107 let poly_z =
108 PolyOverZ::sample_binomial_with_offset(modulus.get_degree() - 1, offset, n, p)?;
109
110 Ok(PolynomialRingZq {
111 poly: poly_z,
112 modulus: modulus.clone(),
113 })
114 }
115}
116
117#[cfg(test)]
118mod test_sample_binomial {
119 use super::{PolynomialRingZq, Z};
120 use crate::{
121 integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq},
122 traits::{GetCoefficient, SetCoefficient},
123 };
124 use std::str::FromStr;
125
126 // As all major tests regarding an appropriate binomial distribution,
127 // whether the correct interval is kept, and if the errors are thrown correctly,
128 // are performed in the `utils` module, we omit these tests here.
129
130 /// Checks whether the boundaries of the interval are kept.
131 #[test]
132 fn boundaries_kept() {
133 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
134
135 for _ in 0..8 {
136 let poly = PolynomialRingZq::sample_binomial(&modulus, 2, 0.5).unwrap();
137 let sample: Z = poly.get_coeff(0).unwrap();
138 assert!(Z::ZERO <= sample || sample <= 2);
139 }
140 }
141
142 /// Checks whether the number of coefficients is correct.
143 #[test]
144 fn nr_coeffs() {
145 let degrees = [1, 3, 7, 15, 32, 120];
146 for degree in degrees {
147 let mut modulus = PolyOverZq::from((1, u64::MAX));
148 modulus.set_coeff(degree, 1).unwrap();
149 let modulus = ModulusPolynomialRingZq::from(&modulus);
150
151 let res = PolynomialRingZq::sample_binomial(&modulus, 256, 0.99999).unwrap();
152
153 assert_eq!(
154 modulus.get_degree(),
155 res.get_degree() + 1,
156 "This test can fail with probability close to 0."
157 );
158 }
159 }
160
161 /// Checks whether 0 modulus polynomial is insufficient.
162 #[test]
163 #[should_panic]
164 fn invalid_modulus() {
165 let modulus = ModulusPolynomialRingZq::from_str("1 1 mod 17").unwrap();
166
167 let _ = PolynomialRingZq::sample_binomial(&modulus, 2, 0.5);
168 }
169}
170
171#[cfg(test)]
172mod test_sample_binomial_with_offset {
173 use super::{PolynomialRingZq, Z};
174 use crate::{
175 integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq},
176 traits::{GetCoefficient, SetCoefficient},
177 };
178 use std::str::FromStr;
179
180 // As all major tests regarding an appropriate binomial distribution,
181 // whether the correct interval is kept, and if the errors are thrown correctly,
182 // are performed in the `utils` module, we omit these tests here.
183
184 /// Checks whether the boundaries of the interval are kept.
185 #[test]
186 fn boundaries_kept() {
187 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
188
189 for _ in 0..8 {
190 let poly = PolynomialRingZq::sample_binomial_with_offset(&modulus, -1, 2, 0.5).unwrap();
191 let sample: Z = poly.get_coeff(0).unwrap();
192 assert!(Z::MINUS_ONE <= sample || sample <= Z::ONE);
193 }
194 }
195
196 /// Checks whether the number of coefficients is correct.
197 #[test]
198 fn nr_coeffs() {
199 let degrees = [1, 3, 7, 15, 32, 120];
200 for degree in degrees {
201 let mut modulus = PolyOverZq::from((1, u64::MAX));
202 modulus.set_coeff(degree, 1).unwrap();
203 let modulus = ModulusPolynomialRingZq::from(&modulus);
204
205 let res = PolynomialRingZq::sample_binomial_with_offset(&modulus, 1, 2, 0.5).unwrap();
206
207 assert_eq!(modulus.get_degree(), res.get_degree() + 1);
208 }
209 }
210
211 /// Checks whether 0 modulus polynomial is insufficient.
212 #[test]
213 #[should_panic]
214 fn invalid_modulus() {
215 let modulus = ModulusPolynomialRingZq::from_str("1 1 mod 17").unwrap();
216
217 let _ = PolynomialRingZq::sample_binomial_with_offset(&modulus, -1, 2, 0.5);
218 }
219}