concrete_integer/client_key/
utils.rs

1use serde::{Deserialize, Serialize};
2
3#[derive(Debug, PartialEq, Eq, Copy, Clone, Serialize, Deserialize)]
4pub struct RadixDecomposition {
5    pub msg_space: usize,
6    pub block_number: usize,
7}
8
9/// Computes possible radix decompositions
10///
11/// Takes the number of bit of the message space as input and output a vector containing all the
12/// correct
13/// possible block decomposition assuming the same message space for all blocks.
14/// Lower and upper bounds define the minimal and maximal space to be considered
15/// Example: 6,2,4 -> [ [2,3], [3,2]] : [msg_space = 2 bits, block_number = 3]
16///
17/// # Example
18///
19/// ```rust
20/// use concrete_integer::client_key::radix_decomposition;
21/// let input_space = 16; //
22/// let min = 2;
23/// let max = 4;
24/// let decomp = radix_decomposition(input_space, min, max);
25///
26/// // Check that 3 possible radix decompositions are provided
27/// assert_eq!(decomp.len(), 3);
28/// ```
29pub fn radix_decomposition(
30    input_space: usize,
31    min_space: usize,
32    max_space: usize,
33) -> Vec<RadixDecomposition> {
34    let mut out: Vec<RadixDecomposition> = vec![];
35    let mut max = max_space;
36    if max_space > input_space {
37        max = input_space;
38    }
39    for msg_space in min_space..max + 1 {
40        let mut block_number = input_space / msg_space;
41        //Manual ceil of the division
42        if input_space % msg_space != 0 {
43            block_number += 1;
44        }
45        out.push(RadixDecomposition {
46            msg_space,
47            block_number,
48        })
49    }
50    out
51}
52
53// Tools to compute the inverse Chinese Remainder Theorem
54pub(crate) fn extended_euclid(f: i64, g: i64) -> (usize, Vec<i64>, Vec<i64>, Vec<i64>, Vec<i64>) {
55    let mut s: Vec<i64> = vec![1, 0];
56    let mut t: Vec<i64> = vec![0, 1];
57    let mut r: Vec<i64> = vec![f, g];
58    let mut q: Vec<i64> = vec![0];
59    let mut i = 1;
60    while r[i] != 0 {
61        q.push(r[i - 1] / r[i]); //q[i]
62        r.push(r[i - 1] - q[i] * r[i]); //r[i+1]
63        s.push(s[i - 1] - q[i] * s[i]); //s[i+1]
64        t.push(t[i - 1] - q[i] * t[i]); //t[i+1]
65        i += 1;
66    }
67    let l: usize = i - 1;
68    (l, r, s, t, q)
69}
70
71pub(crate) fn i_crt(modulus: &[u64], val: &[u64]) -> u64 {
72    let big_mod = modulus.iter().product::<u64>();
73    let mut c: Vec<u64> = vec![0; val.len()];
74    let mut out: u64 = 0;
75
76    for i in 0..val.len() {
77        let tmp_mod = big_mod / modulus[i];
78        let (l, _, s, _, _) = extended_euclid(tmp_mod as i64, modulus[i] as i64);
79        let sl: u64 = if s[l] < 0 {
80            //a is positive
81            (s[l] % modulus[i] as i64 + modulus[i] as i64) as u64
82        } else {
83            s[l] as u64
84        };
85        c[i] = val[i].wrapping_mul(sl);
86        c[i] %= modulus[i];
87
88        out = out.wrapping_add(c[i] * tmp_mod);
89    }
90    out % big_mod
91}
concrete_integer/client_key/utils.rs

concrete_integer/client_key/
utils.rs
