phantom-zone/src/utils.rs
src/utils.rsRaw
1use std::{fmt::Debug, usize, vec};
2
3use itertools::{izip, Itertools};
4use num_traits::{FromPrimitive, PrimInt, Signed};
5
6use crate::{
7 backend::Modulus,
8 random::{RandomElementInModulus, RandomFill},
9 Matrix,
10};
11pub trait WithLocal {
12 fn with_local<F, R>(func: F) -> R
13 where
14 F: Fn(&Self) -> R;
15
16 fn with_local_mut<F, R>(func: F) -> R
17 where
18 F: Fn(&mut Self) -> R;
19
20 fn with_local_mut_mut<F, R>(func: &mut F) -> R
21 where
22 F: FnMut(&mut Self) -> R;
23}
24
25pub trait Global {
26 fn global() -> &'static Self;
27}
28
29pub(crate) trait ShoupMul {
30 fn representation(value: Self, q: Self) -> Self;
31 fn mul(a: Self, b: Self, b_shoup: Self, q: Self) -> Self;
32}
33
34impl ShoupMul for u64 {
35 #[inline]
36 fn representation(value: Self, q: Self) -> Self {
37 ((value as u128 * (1u128 << 64)) / q as u128) as u64
38 }
39
40 #[inline]
41 /// Returns a * b % q
42 fn mul(a: Self, b: Self, b_shoup: Self, q: Self) -> Self {
43 (b.wrapping_mul(a))
44 .wrapping_sub(q.wrapping_mul(((b_shoup as u128 * a as u128) >> 64) as u64))
45 }
46}
47
48pub(crate) trait ToShoup {
49 type Modulus;
50 fn to_shoup(value: &Self, modulus: Self::Modulus) -> Self;
51}
52
53impl ToShoup for u64 {
54 type Modulus = u64;
55 fn to_shoup(value: &Self, modulus: Self) -> Self {
56 ((*value as u128 * (1u128 << 64)) / modulus as u128) as u64
57 }
58}
59
60impl ToShoup for Vec<Vec<u64>> {
61 type Modulus = u64;
62 fn to_shoup(value: &Self, modulus: Self::Modulus) -> Self {
63 let (row, col) = value.dimension();
64 let mut shoup_value = vec![vec![0u64; col]; row];
65 izip!(shoup_value.iter_mut(), value.iter()).for_each(|(shoup_r, r)| {
66 izip!(shoup_r.iter_mut(), r.iter()).for_each(|(s, e)| {
67 *s = u64::to_shoup(e, modulus);
68 })
69 });
70 shoup_value
71 }
72}
73
74pub fn fill_random_ternary_secret_with_hamming_weight<
75 T: Signed,
76 R: RandomFill<[u8]> + RandomElementInModulus<usize, usize>,
77>(
78 out: &mut [T],
79 hamming_weight: usize,
80 rng: &mut R,
81) {
82 let mut bytes = vec![0u8; hamming_weight.div_ceil(8)];
83 RandomFill::<[u8]>::random_fill(rng, &mut bytes);
84
85 let size = out.len();
86 let mut secret_indices = (0..size).into_iter().map(|i| i).collect_vec();
87 let mut bit_index = 0;
88 let mut byte_index = 0;
89 for _ in 0..hamming_weight {
90 let s_index = RandomElementInModulus::<usize, usize>::random(rng, &secret_indices.len());
91
92 let curr_bit = (bytes[byte_index] >> bit_index) & 1;
93 if curr_bit == 1 {
94 out[secret_indices[s_index]] = T::one();
95 } else {
96 out[secret_indices[s_index]] = -T::one();
97 }
98
99 secret_indices[s_index] = *secret_indices.last().unwrap();
100 secret_indices.truncate(secret_indices.len());
101
102 if bit_index == 7 {
103 bit_index = 0;
104 byte_index += 1;
105 } else {
106 bit_index += 1;
107 }
108 }
109}
110
111// TODO (Jay): this is only a workaround. Add a propoer way to perform primality
112// tests.
113fn is_probably_prime(candidate: u64) -> bool {
114 num_bigint_dig::prime::probably_prime(&num_bigint_dig::BigUint::from(candidate), 0)
115}
116
117/// Finds prime that satisfy
118/// - $prime \lt upper_bound$
119/// - $\log{prime} = num_bits$
120/// - `prime % modulo == 1`
121pub(crate) fn generate_prime(num_bits: usize, modulo: u64, upper_bound: u64) -> Option<u64> {
122 let leading_zeros = (64 - num_bits) as u32;
123
124 let mut tentative_prime = upper_bound - 1;
125 while tentative_prime % modulo != 1 && tentative_prime.leading_zeros() == leading_zeros {
126 tentative_prime -= 1;
127 }
128
129 while !is_probably_prime(tentative_prime)
130 && tentative_prime.leading_zeros() == leading_zeros
131 && tentative_prime >= modulo
132 {
133 tentative_prime -= modulo;
134 }
135
136 if is_probably_prime(tentative_prime) && tentative_prime.leading_zeros() == leading_zeros {
137 Some(tentative_prime)
138 } else {
139 None
140 }
141}
142
143/// Returns a^b mod q
144pub fn mod_exponent(a: u64, mut b: u64, q: u64) -> u64 {
145 let mod_mul = |v1: &u64, v2: &u64| {
146 let tmp = *v1 as u128 * *v2 as u128;
147 (tmp % q as u128) as u64
148 };
149
150 let mut acc = a;
151 let mut out = 1;
152 while b != 0 {
153 let flag = b & 1;
154
155 if flag == 1 {
156 out = mod_mul(&acc, &out);
157 }
158 acc = mod_mul(&acc, &acc);
159
160 b >>= 1;
161 }
162
163 out
164}
165
166pub fn mod_inverse(a: u64, q: u64) -> u64 {
167 mod_exponent(a, q - 2, q)
168}
169
170pub fn negacyclic_mul<T: PrimInt, F: Fn(&T, &T) -> T>(
171 a: &[T],
172 b: &[T],
173 mul: F,
174 modulus: T,
175) -> Vec<T> {
176 let mut r = vec![T::zero(); a.len()];
177 for i in 0..a.len() {
178 for j in 0..i + 1 {
179 // println!("i: {j} {}", i - j);
180 r[i] = (r[i] + mul(&a[j], &b[i - j])) % modulus;
181 }
182
183 for j in i + 1..a.len() {
184 // println!("i: {j} {}", a.len() - j + i);
185 r[i] = (r[i] + modulus - mul(&a[j], &b[a.len() - j + i])) % modulus;
186 }
187 // println!("")
188 }
189
190 return r;
191}
192
193pub trait TryConvertFrom1<T: ?Sized, P> {
194 fn try_convert_from(value: &T, parameters: &P) -> Self;
195}
196
197impl<P: Modulus<Element = u64>> TryConvertFrom1<[i64], P> for Vec<u64> {
198 fn try_convert_from(value: &[i64], parameters: &P) -> Self {
199 value
200 .iter()
201 .map(|v| parameters.map_element_from_i64(*v))
202 .collect_vec()
203 }
204}
205
206impl<P: Modulus<Element = u64>> TryConvertFrom1<[i32], P> for Vec<u64> {
207 fn try_convert_from(value: &[i32], parameters: &P) -> Self {
208 value
209 .iter()
210 .map(|v| parameters.map_element_from_i64(*v as i64))
211 .collect_vec()
212 }
213}
214
215impl<P: Modulus> TryConvertFrom1<[P::Element], P> for Vec<i64> {
216 fn try_convert_from(value: &[P::Element], parameters: &P) -> Self {
217 value
218 .iter()
219 .map(|v| parameters.map_element_to_i64(v))
220 .collect_vec()
221 }
222}
223
224pub(crate) struct Stats<T> {
225 pub(crate) samples: Vec<T>,
226}
227
228impl<T: PrimInt + FromPrimitive + Debug> Stats<T>
229where
230 // T: for<'a> Sum<&'a T>,
231 T: for<'a> std::iter::Sum<&'a T> + std::iter::Sum<T>,
232{
233 pub(crate) fn new() -> Self {
234 Self { samples: vec![] }
235 }
236
237 pub(crate) fn mean(&self) -> f64 {
238 self.samples.iter().sum::<T>().to_f64().unwrap() / (self.samples.len() as f64)
239 }
240
241 pub(crate) fn std_dev(&self) -> f64 {
242 let mean = self.mean();
243
244 // diff
245 let diff_sq = self
246 .samples
247 .iter()
248 .map(|v| {
249 let t = v.to_f64().unwrap() - mean;
250 t * t
251 })
252 .into_iter()
253 .sum::<f64>();
254
255 (diff_sq / (self.samples.len() as f64)).sqrt()
256 }
257
258 pub(crate) fn add_more(&mut self, values: &[T]) {
259 self.samples.extend(values.iter());
260 }
261}
262
263#[cfg(test)]
264mod tests {
265 use super::is_probably_prime;
266 // let n = 1 << (11 + 1);
267 // let mut start = 1 << 55;
268 // while start < (1 << 56) {
269 // if start % n == 1 {
270 // break;
271 // }
272 // start += 1;
273 // }
274
275 // let mut prime = None;
276 // while start < (1 << 56) {
277 // if is_probably_prime(start) {
278 // dbg!(start);
279 // prime = Some(start);
280 // break;
281 // }
282 // dbg!(start);
283 // start += (n);
284 // }
285 #[test]
286 fn gg() {
287 let q = 30;
288 for i in 0..1000 {
289 let x = (1u64 << (q * 2)) + (i * (1 << q)) + 1;
290 let is_prime = is_probably_prime(x);
291 if is_prime {
292 println!("{x} = 2^{} + {i} * 2^{q} + 1", 2 * q);
293 }
294 }
295
296 // println!("{:?}", prime);
297 }
298}