circomspect_circom_algebra/
modular_arithmetic.rs

1use num_bigint::{BigInt, ModInverse, Sign};
2use num_traits::ToPrimitive;
3
4pub enum ArithmeticError {
5    DivisionByZero,
6    BitOverFlowInShift,
7}
8
9fn modulus(a: &BigInt, b: &BigInt) -> BigInt {
10    ((a % b) + b) % b
11}
12// The maximum number of bits a BigInt can have is 18_446_744_073_709_551_615
13// Returns the LITTLE ENDIAN representation of the bigint
14fn bit_representation(elem: &BigInt) -> (Sign, Vec<u8>) {
15    elem.to_radix_le(2)
16}
17// Computes 2**b -1 where b is the number of bits of field
18fn mask(field: &BigInt) -> BigInt {
19    let two = BigInt::from(2);
20    let b = bit_representation(field).1.len();
21    let mask = num_traits::pow::pow(two, b);
22    mask - 1
23}
24
25// Arithmetic operations
26pub fn add(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
27    //let left = modulus(left,field);
28    //let right = modulus(right,field);
29    modulus(&(left + right), field)
30}
31pub fn mul(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
32    //let left = modulus(left,field);
33    //let right = modulus(right,field);
34    modulus(&(left * right), field)
35}
36pub fn sub(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
37    //let left = modulus(left,field);
38    //let right = modulus(right,field);
39    modulus(&(left - right), field)
40}
41pub fn div(left: &BigInt, right: &BigInt, field: &BigInt) -> Result<BigInt, ArithmeticError> {
42    let right_inverse =
43        right.mod_inverse(field).map_or(Err(ArithmeticError::DivisionByZero), Ok)?;
44    let res = mul(left, &right_inverse, field);
45    Ok(res)
46}
47pub fn idiv(left: &BigInt, right: &BigInt, field: &BigInt) -> Result<BigInt, ArithmeticError> {
48    let zero = BigInt::from(0);
49    let left = modulus(left, field);
50    let right = modulus(right, field);
51    if right == zero {
52        Err(ArithmeticError::DivisionByZero)
53    } else {
54        Ok(left / right)
55    }
56}
57pub fn mod_op(left: &BigInt, right: &BigInt, field: &BigInt) -> Result<BigInt, ArithmeticError> {
58    let left = modulus(left, field);
59    let right = modulus(right, field);
60    Ok(modulus(&left, &right))
61}
62pub fn pow(base: &BigInt, exp: &BigInt, field: &BigInt) -> BigInt {
63    base.modpow(exp, field)
64}
65pub fn prefix_sub(elem: &BigInt, field: &BigInt) -> BigInt {
66    let minus_one = BigInt::from(-1);
67    mul(elem, &minus_one, field)
68}
69
70//Bit operations
71
72// 256 bit complement
73pub fn complement_256(elem: &BigInt, field: &BigInt) -> BigInt {
74    let (sign, mut bit_repr) = bit_representation(elem);
75    while bit_repr.len() > 256 {
76        bit_repr.pop();
77    }
78    for _i in bit_repr.len()..256 {
79        bit_repr.push(0);
80    }
81    for bit in &mut bit_repr {
82        *bit = u8::from(*bit == 0);
83    }
84    let cp = BigInt::from_radix_le(sign, &bit_repr, 2).unwrap();
85    modulus(&cp, field)
86}
87
88pub fn shift_l(left: &BigInt, right: &BigInt, field: &BigInt) -> Result<BigInt, ArithmeticError> {
89    let two = BigInt::from(2);
90    let top = field / &two;
91    if right <= &top {
92        let usize_repr = right.to_usize().map_or(Err(ArithmeticError::DivisionByZero), Ok)?;
93        let value = modulus(&((left * &num_traits::pow(two, usize_repr)) & &mask(field)), field);
94        Ok(value)
95    } else {
96        shift_r(left, &(field - right), field)
97    }
98}
99pub fn shift_r(left: &BigInt, right: &BigInt, field: &BigInt) -> Result<BigInt, ArithmeticError> {
100    let two = BigInt::from(2);
101    let top = field / &two;
102    if right <= &top {
103        let usize_repr = right.to_usize().map_or(Err(ArithmeticError::DivisionByZero), Ok)?;
104        let value = left / &num_traits::pow(two, usize_repr);
105        Ok(value)
106    } else {
107        shift_l(left, &(field - right), field)
108    }
109}
110pub fn bit_or(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
111    modulus(&(left | right), field)
112}
113pub fn bit_and(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
114    modulus(&(left & right), field)
115}
116pub fn bit_xor(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
117    modulus(&(left ^ right), field)
118}
119
120// Boolean operations
121fn constant_true() -> BigInt {
122    BigInt::from(1)
123}
124fn constant_false() -> BigInt {
125    BigInt::from(0)
126}
127fn val(elem: &BigInt, field: &BigInt) -> BigInt {
128    let c = (field / &BigInt::from(2)) + 1;
129    if &c <= elem && elem < field {
130        elem - field
131    } else {
132        elem.clone()
133    }
134}
135fn comparable_element(elem: &BigInt, field: &BigInt) -> BigInt {
136    val(&modulus(elem, field), field)
137}
138fn normalize(elem: &BigInt, field: &BigInt) -> BigInt {
139    let f = constant_false();
140    let t = constant_true();
141    if comparable_element(elem, field) == f {
142        f
143    } else {
144        t
145    }
146}
147pub fn as_bool(elem: &BigInt, field: &BigInt) -> bool {
148    normalize(elem, field) != constant_false()
149}
150pub fn not(elem: &BigInt, field: &BigInt) -> BigInt {
151    (normalize(elem, field) + 1) % 2
152}
153pub fn bool_or(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
154    (normalize(left, field) + normalize(right, field) + bool_and(left, right, field)) % 2
155}
156pub fn bool_and(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
157    normalize(left, field) * normalize(right, field)
158}
159pub fn eq(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
160    let left = modulus(left, field);
161    let right = modulus(right, field);
162    if left == right {
163        constant_true()
164    } else {
165        constant_false()
166    }
167}
168pub fn lesser(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
169    let left = comparable_element(left, field);
170    let right = comparable_element(right, field);
171    if left < right {
172        constant_true()
173    } else {
174        constant_false()
175    }
176}
177pub fn not_eq(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
178    not(&eq(left, right, field), field)
179}
180pub fn lesser_eq(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
181    bool_or(&lesser(left, right, field), &eq(left, right, field), field)
182}
183pub fn greater(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
184    not(&lesser_eq(left, right, field), field)
185}
186pub fn greater_eq(left: &BigInt, right: &BigInt, field: &BigInt) -> BigInt {
187    bool_or(&greater(left, right, field), &eq(left, right, field), field)
188}
189
190#[cfg(test)]
191mod tests {
192    use super::*;
193    const FIELD: &str = "257";
194    #[test]
195    fn mod_check() {
196        let a = BigInt::from(-8);
197        let b = BigInt::from(5);
198        let res = super::modulus(&a, &b);
199        assert_eq!(res, BigInt::from(2));
200    }
201    #[test]
202    fn comparison_check() {
203        let field = BigInt::parse_bytes(FIELD.as_bytes(), 10)
204            .expect("generating the big int was not possible");
205        let a = sub(&BigInt::from(2), &BigInt::from(1), &field);
206        let b = BigInt::from(-1);
207        let res = not_eq(&a, &b, &field);
208        assert!(as_bool(&res, &field));
209    }
210    #[test]
211    fn mod_operation_check() {
212        let field = BigInt::parse_bytes(FIELD.as_bytes(), 10)
213            .expect("generating the big int was not possible");
214        let a = BigInt::from(17);
215        let b = BigInt::from(32);
216        if let Ok(res) = mod_op(&a, &b, &field) {
217            assert_eq!(a, res)
218        } else {
219            unreachable!();
220        }
221    }
222    #[test]
223    fn complement_of_complement_is_the_original_test() {
224        let field = BigInt::parse_bytes(FIELD.as_bytes(), 10)
225            .expect("generating the big int was not possible");
226        let big_num = BigInt::parse_bytes("1234".as_bytes(), 10)
227            .expect("generating the big int was not possible");
228        let big_num_complement = complement_256(&big_num, &field);
229        let big_num_complement_complement = complement_256(&big_num_complement, &field);
230        let big_num_modulus = modulus(&big_num, &field);
231        assert_eq!(big_num_complement_complement, big_num_modulus);
232    }
233    #[test]
234    fn lesser_eq_test() {
235        let field = BigInt::parse_bytes(FIELD.as_bytes(), 10)
236            .expect("generating the big int was not possible");
237        let zero = BigInt::from(0);
238        let two = BigInt::from(2);
239        assert!(zero < two);
240        assert!(as_bool(&lesser_eq(&zero, &two, &field), &field));
241    }
242}
circomspect_circom_algebra/modular_arithmetic.rs

circomspect_circom_algebra/
modular_arithmetic.rs
