qfall_math/rational/poly_over_q/rounding.rs
1// Copyright 2024 Marcel Luca Schmidt
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 includes functionality for rounding instances of [`PolyOverQ`] coefficient-wise.
10
11use super::PolyOverQ;
12use crate::{
13 error::MathError,
14 integer::PolyOverZ,
15 macros::seeded::seedable_function,
16 rational::Q,
17 traits::{GetCoefficient, SetCoefficient},
18 utils::sample::uniform::SamplerRng,
19};
20
21impl PolyOverQ {
22 /// Rounds all coefficients of the given rational polynomial [`PolyOverQ`] down to the next integer
23 /// as a [`PolyOverZ`].
24 ///
25 /// # Examples
26 /// ```
27 /// use qfall_math::rational::PolyOverQ;
28 /// use qfall_math::integer::PolyOverZ;
29 /// use std::str::FromStr;
30 ///
31 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
32 /// assert_eq!(PolyOverZ::from_str("2 2 1").unwrap(), value.floor());
33 ///
34 /// let value = PolyOverQ::from_str("2 -5/2 1").unwrap();
35 /// assert_eq!(PolyOverZ::from_str("2 -3 1").unwrap(), value.floor());
36 /// ```
37 pub fn floor(&self) -> PolyOverZ {
38 let mut out = PolyOverZ::from(unsafe { self.get_coeff_unchecked(0).floor() });
39 for i in 1..self.get_degree() + 1 {
40 let coeff = unsafe { self.get_coeff_unchecked(i).floor() };
41 unsafe { out.set_coeff_unchecked(i, coeff) };
42 }
43
44 out
45 }
46
47 /// Rounds all coefficients of the given rational polynomial [`PolyOverQ`] up to the next integer
48 /// as a [`PolyOverZ`].
49 ///
50 /// # Examples
51 /// ```
52 /// use qfall_math::rational::PolyOverQ;
53 /// use qfall_math::integer::PolyOverZ;
54 /// use std::str::FromStr;
55 ///
56 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
57 /// assert_eq!(PolyOverZ::from_str("2 3 1").unwrap(), value.ceil());
58 ///
59 /// let value = PolyOverQ::from_str("2 -5/2 1").unwrap();
60 /// assert_eq!(PolyOverZ::from_str("2 -2 1").unwrap(), value.ceil());
61 /// ```
62 pub fn ceil(&self) -> PolyOverZ {
63 let mut out = PolyOverZ::from(unsafe { self.get_coeff_unchecked(0).ceil() });
64 for i in 1..self.get_degree() + 1 {
65 let coeff = unsafe { self.get_coeff_unchecked(i).ceil() };
66 unsafe { out.set_coeff_unchecked(i, coeff) };
67 }
68
69 out
70 }
71
72 /// Rounds all coefficients of the given rational polynomial [`PolyOverQ`] to the closest integer
73 /// as a [`PolyOverZ`].
74 ///
75 /// # Examples
76 /// ```
77 /// use qfall_math::rational::PolyOverQ;
78 /// use qfall_math::integer::PolyOverZ;
79 /// use std::str::FromStr;
80 ///
81 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
82 /// assert_eq!(PolyOverZ::from_str("2 3 1").unwrap(), value.round());
83 ///
84 /// let value = PolyOverQ::from_str("2 -5/2 1").unwrap();
85 /// assert_eq!(PolyOverZ::from_str("2 -2 1").unwrap(), value.round());
86 /// ```
87 pub fn round(&self) -> PolyOverZ {
88 let mut out = PolyOverZ::from(unsafe { self.get_coeff_unchecked(0).round() });
89
90 for i in 1..self.get_degree() + 1 {
91 let coeff = unsafe { self.get_coeff_unchecked(i).round() };
92 unsafe { out.set_coeff_unchecked(i, coeff) };
93 }
94
95 out
96 }
97
98 seedable_function!(
99 /// Performs the randomized rounding algorithm coefficient-wise
100 /// by sampling from a discrete Gaussian over the integers shifted
101 /// by `self` with gaussian parameter `r`.
102 ///
103 /// Parameters:
104 /// - `r`: specifies the Gaussian parameter, which is proportional
105 /// to the standard deviation `sigma * sqrt(2 * pi) = r`
106 #[seeded]
107 /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
108 #[optionally_seeded]
109 /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
110 #[optionally_seeded]
111 /// If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
112 ///
113 /// Returns the rounded polynomial as a [`PolyOverZ`] or an error if `r < 0`.
114 ///
115 /// # Examples
116 /// ```
117 /// use qfall_math::rational::PolyOverQ;
118 /// use std::str::FromStr;
119 ///
120 /// let value = PolyOverQ::from_str("2 5/2 1").unwrap();
121 #[unseeded]
122 /// let rounded = value.randomized_rounding(3).unwrap();
123 #[seeded]
124 /// let rounded = value.randomized_rounding_seeded(3, [42; 32]).unwrap();
125 /// ```
126 ///
127 /// # Errors and Failures
128 /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
129 /// if `r < 0`.
130 ///
131 /// This function implements randomized rounding according to:
132 /// - \[1\] Peikert, C. (2010, August).
133 /// An efficient and parallel Gaussian sampler for lattices.
134 /// In: Annual Cryptology Conference (pp. 80-97).
135 /// <https://link.springer.com/chapter/10.1007/978-3-642-14623-7_5>
136 pub(crate) fn randomized_rounding(
137 &self,
138 r: impl Into<Q>,
139 seed: Option<[u8; 32]>,
140 ) -> Result<PolyOverZ, MathError> {
141 // derives an independent seed for every call of a seedable function below,
142 // see the documentation of `seedable_function` in `src/macros/seeded.rs`
143 let mut rng = SamplerRng::new(seed);
144
145 let r = r.into();
146 let mut out = PolyOverZ::from(unsafe {
147 self.get_coeff_unchecked(0)
148 .randomized_rounding_optionally_seeded(&r, rng.derive_seed())?
149 });
150 for i in 1..self.get_degree() + 1 {
151 let coeff = unsafe {
152 self.get_coeff_unchecked(i)
153 .randomized_rounding_optionally_seeded(&r, rng.derive_seed())?
154 };
155 unsafe { out.set_coeff_unchecked(i, coeff) };
156 }
157
158 Ok(out)
159 }
160 );
161}
162
163#[cfg(test)]
164mod test_floor {
165 use crate::{integer::PolyOverZ, rational::PolyOverQ};
166 use std::str::FromStr;
167
168 // Ensure that positive rationals are rounded correctly
169 #[test]
170 fn positive() {
171 let value = PolyOverQ::from_str(&format!("2 1/{} {}/2", u64::MAX, i64::MAX)).unwrap();
172 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (i64::MAX - 1) / 2)).unwrap();
173
174 assert_eq!(cmp, value.floor());
175 }
176
177 // Ensure that negative rationals are rounded correctly
178 #[test]
179 fn negative() {
180 let value = PolyOverQ::from_str(&format!("2 -1/{} -{}/2", u64::MAX, i64::MAX)).unwrap();
181 let cmp = PolyOverZ::from_str(&format!("2 -1 {}", (-i64::MAX - 1) / 2)).unwrap();
182
183 assert_eq!(cmp, value.floor());
184 }
185}
186
187#[cfg(test)]
188mod test_ceil {
189 use crate::{integer::PolyOverZ, rational::PolyOverQ};
190 use std::str::FromStr;
191
192 // Ensure that positive rationals are rounded correctly
193 #[test]
194 fn positive() {
195 let value = PolyOverQ::from_str(&format!("2 1/{} {}/2", u64::MAX, i64::MAX)).unwrap();
196 let cmp = PolyOverZ::from_str(&format!("2 1 {}", (i64::MAX - 1) / 2 + 1)).unwrap();
197
198 assert_eq!(cmp, value.ceil());
199 }
200
201 // Ensure that negative rationals are rounded correctly
202 #[test]
203 fn negative() {
204 let value = PolyOverQ::from_str(&format!("2 -1/{} -{}/2", u64::MAX, i64::MAX)).unwrap();
205 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (-i64::MAX - 1) / 2 + 1)).unwrap();
206
207 assert_eq!(cmp, value.ceil());
208 }
209}
210
211#[cfg(test)]
212mod test_round {
213 use crate::{integer::PolyOverZ, rational::PolyOverQ};
214 use std::str::FromStr;
215
216 // Ensure that positive rationals are rounded correctly
217 #[test]
218 fn positive() {
219 let value = PolyOverQ::from_str(&format!("2 1/{} {}/2", u64::MAX, i64::MAX)).unwrap();
220 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (i64::MAX - 1) / 2 + 1)).unwrap();
221
222 assert_eq!(cmp, value.round());
223 }
224
225 // Ensure that negative rationals are rounded correctly
226 #[test]
227 fn negative() {
228 let value = PolyOverQ::from_str(&format!("2 -1/{} -{}/2", u64::MAX, i64::MAX)).unwrap();
229 let cmp = PolyOverZ::from_str(&format!("2 0 {}", (-i64::MAX - 1) / 2 + 1)).unwrap();
230
231 assert_eq!(cmp, value.round());
232 }
233}
234
235#[cfg(test)]
236mod test_randomized_rounding {
237 use crate::rational::PolyOverQ;
238 use crate::utils::sample::test_seed;
239 use std::str::FromStr;
240
241 /// Ensure that a `r < 0` throws an error
242 #[test]
243 fn negative_r() {
244 for seeded in [false, true] {
245 let value = PolyOverQ::from_str("2 5/2 1").unwrap();
246 assert!(
247 value
248 .randomized_rounding_optionally_seeded(-1, seeded.then(test_seed))
249 .is_err()
250 );
251 }
252 }
253
254 /// Checks whether the same seed results in the same sample.
255 #[test]
256 fn same_seed_same_sample() {
257 use crate::rational::PolyOverQ;
258 use std::str::FromStr;
259 let value = PolyOverQ::from_str("2 5/2 1").unwrap();
260 let sample_0 = value.randomized_rounding_seeded(3, [42; 32]).unwrap();
261 let sample_1 = value.randomized_rounding_seeded(3, [42; 32]).unwrap();
262
263 assert_eq!(sample_0, sample_1);
264 }
265
266 /// Checks whether the seeded variant outputs the known sample for a fixed seed.
267 #[test]
268 fn known_answer() {
269 use crate::rational::PolyOverQ;
270 use std::str::FromStr;
271 let value = PolyOverQ::from_str("2 5/2 1").unwrap();
272 let sample = value.randomized_rounding_seeded(3, [42; 32]).unwrap();
273
274 assert_eq!("1 3", sample.to_string());
275 }
276
277 /// Checks whether the unseeded and the seeded function are available.
278 #[test]
279 fn availability() {
280 use crate::rational::PolyOverQ;
281 use std::str::FromStr;
282 let value = PolyOverQ::from_str("2 5/2 1").unwrap();
283
284 // explicitly checks the existence of the unseeded and the seeded function
285 let _ = value.randomized_rounding(3);
286 let _ = value.randomized_rounding_seeded(3, test_seed());
287 }
288}