fancy_garbling/circuits/binary/
binary_division.rs

1use crate::{
2    BinaryBundle, FancyBinary,
3    circuit::Circuit,
4    circuits::binary::{BinaryAddition, BinaryConstant, BinaryMultiplex, BinaryTwosComplement},
5};
6use core::marker::PhantomData;
7use swanky_channel::Channel;
8use swanky_error::Result;
9
10/// For [`BinaryBundle`]s `x` and `y`, output `x / y`.
11#[derive(Default)]
12pub struct BinaryDivision<'a>(PhantomData<&'a ()>);
13
14impl<'a> BinaryDivision<'a> {
15    /// Create a new [`BinaryDivision`] circuit.
16    pub fn new() -> Self {
17        Default::default()
18    }
19}
20
21impl<'a, F: FancyBinary> Circuit<F> for BinaryDivision<'a>
22where
23    F::Item: 'a,
24{
25    type Input = (&'a BinaryBundle<F::Item>, &'a BinaryBundle<F::Item>);
26    type Output = BinaryBundle<F::Item>;
27
28    fn execute(
29        &self,
30        backend: &mut F,
31        inputs: Self::Input,
32        channel: &mut Channel,
33    ) -> Result<Self::Output> {
34        let (xs, ys) = inputs;
35        assert_eq!(xs.moduli(), ys.moduli());
36
37        let ys_neg = BinaryTwosComplement::new().execute(backend, ys, channel)?;
38        let mut acc = BinaryConstant::new(0, xs.size()).execute(backend, (), channel)?;
39        let mut qs = BinaryBundle::new(Vec::new());
40        for x in xs.iter().rev() {
41            acc.pop();
42            acc.insert(0, x.clone());
43            let (res, cout) =
44                BinaryAddition::default().execute(backend, (&acc, &ys_neg), channel)?;
45            acc = BinaryMultiplex::new().execute(backend, (cout.clone(), &acc, &res), channel)?;
46            qs.push(cout);
47        }
48        qs.reverse(); // Switch back to little-endian
49        Ok(qs)
50    }
51}
52
53#[cfg(test)]
54mod test {
55    use rand::{Rng, thread_rng};
56
57    use crate::{
58        circuits::binary::BinaryDivision,
59        dummy::{Dummy, DummyVal},
60    };
61
62    #[test]
63    fn test_binary_division() {
64        let mut rng = thread_rng();
65        let nbits = 64;
66        let q = 1 << nbits;
67
68        for _ in 0..16 {
69            let x = rng.r#gen::<u128>() % q;
70            let mut y = rng.r#gen::<u128>() % q;
71            while y == 0 {
72                y = rng.r#gen::<u128>() % q;
73            }
74            let x_input = DummyVal::to_binary(x, nbits);
75            let y_input = DummyVal::to_binary(y, nbits);
76            let output = Dummy::eval(&BinaryDivision::new(), (&x_input, &y_input)).unwrap();
77            assert_eq!(DummyVal::from_binary(&output), x / y);
78        }
79    }
80}
fancy_garbling/circuits/binary/binary_division.rs

fancy_garbling/circuits/binary/
binary_division.rs
