openvm_algebra_guest/
exp_bytes.rs

1use core::ops::Mul;
2
3use crate::Field;
4
5pub trait ExpBytes: Field {
6    /// Exponentiates a field element by a value with a sign in big endian byte order
7    fn exp_bytes(&self, is_positive: bool, bytes_be: &[u8]) -> Self
8    where
9        for<'a> &'a Self: Mul<&'a Self, Output = Self>,
10    {
11        let mut x = self.clone();
12
13        if !is_positive {
14            x = Self::ONE.div_unsafe(&x);
15        }
16
17        let mut res = Self::ONE;
18
19        let x_sq = &x * &x;
20        let ops = [x.clone(), x_sq.clone(), &x_sq * &x];
21
22        for &b in bytes_be.iter() {
23            let mut mask = 0xc0;
24            for j in 0..4 {
25                res = &res * &res * &res * &res;
26                let c = (b & mask) >> (6 - 2 * j);
27                if c != 0 {
28                    res *= &ops[(c - 1) as usize];
29                }
30                mask >>= 2;
31            }
32        }
33        res
34    }
35
36    /// Exponentiates a field element using a signed digit representation (e.g. NAF).
37    /// `digits_naf` is expected to be in LSB-first order with entries in {-1, 0, 1}.
38    fn exp_naf(&self, is_positive: bool, digits_naf: &[i8]) -> Self
39    where
40        for<'a> &'a Self: Mul<&'a Self, Output = Self>,
41    {
42        if digits_naf.is_empty() {
43            return Self::ONE;
44        }
45
46        let mut base = self.clone();
47        if !is_positive {
48            base = Self::ONE.div_unsafe(&base);
49        }
50
51        let base_inv = digits_naf.contains(&-1).then(|| base.invert());
52
53        let mut res = Self::ONE;
54        for &digit in digits_naf.iter().rev() {
55            res.square_assign();
56            if digit == 1 {
57                res *= &base;
58            } else if digit == -1 {
59                res *= base_inv
60                    .as_ref()
61                    .expect("negative digit requires available inverse");
62            }
63        }
64        res
65    }
66}
67
68impl<F: Field> ExpBytes for F where for<'a> &'a Self: Mul<&'a Self, Output = Self> {}
openvm_algebra_guest/exp_bytes.rs

openvm_algebra_guest/
exp_bytes.rs
