ark_ff/fields/
cyclotomic.rs

1/// Fields that have a cyclotomic multiplicative subgroup, and which can
2/// leverage efficient inversion and squaring algorithms for elements in this subgroup.
3/// If a field has multiplicative order p^d - 1, the cyclotomic subgroups refer to subgroups of order φ_n(p),
4/// for any n < d, where φ_n is the [n-th cyclotomic polynomial](https://en.wikipedia.org/wiki/Cyclotomic_polynomial).
5///
6/// ## Note
7///
8/// Note that this trait is unrelated to the `Group` trait from the `ark_ec` crate. That trait
9/// denotes an *additive* group, while this trait denotes a *multiplicative* group.
10pub trait CyclotomicMultSubgroup: crate::Field {
11    /// Is the inverse fast to compute? For example, in quadratic extensions, the inverse
12    /// can be computed at the cost of negating one coordinate, which is much faster than
13    /// standard inversion.
14    /// By default this is `false`, but should be set to `true` for quadratic extensions.
15    const INVERSE_IS_FAST: bool = false;
16
17    /// Compute a square in the cyclotomic subgroup. By default this is computed using [`Field::square`](crate::Field::square), but for
18    /// degree 12 extensions, this can be computed faster than normal squaring.
19    ///
20    /// # Warning
21    ///
22    /// This method should be invoked only when `self` is in the cyclotomic subgroup.
23    fn cyclotomic_square(&self) -> Self {
24        let mut result = *self;
25        *result.cyclotomic_square_in_place()
26    }
27
28    /// Square `self` in place. By default this is computed using
29    /// [`Field::square_in_place`](crate::Field::square_in_place), but for degree 12 extensions,
30    /// this can be computed faster than normal squaring.
31    ///
32    /// # Warning
33    ///
34    /// This method should be invoked only when `self` is in the cyclotomic subgroup.
35    fn cyclotomic_square_in_place(&mut self) -> &mut Self {
36        self.square_in_place()
37    }
38
39    /// Compute the inverse of `self`. See [`Self::INVERSE_IS_FAST`] for details.
40    /// Returns [`None`] if `self.is_zero()`, and [`Some`] otherwise.
41    ///
42    /// # Warning
43    ///
44    /// This method should be invoked only when `self` is in the cyclotomic subgroup.
45    fn cyclotomic_inverse(&self) -> Option<Self> {
46        let mut result = *self;
47        result.cyclotomic_inverse_in_place().copied()
48    }
49
50    /// Compute the inverse of `self`. See [`Self::INVERSE_IS_FAST`] for details.
51    /// Returns [`None`] if `self.is_zero()`, and [`Some`] otherwise.
52    ///
53    /// # Warning
54    ///
55    /// This method should be invoked only when `self` is in the cyclotomic subgroup.
56    fn cyclotomic_inverse_in_place(&mut self) -> Option<&mut Self> {
57        self.inverse_in_place()
58    }
59
60    /// Compute a cyclotomic exponentiation of `self` with respect to `e`.
61    ///
62    /// # Warning
63    ///
64    /// This method should be invoked only when `self` is in the cyclotomic subgroup.
65    fn cyclotomic_exp(&self, e: impl AsRef<[u64]>) -> Self {
66        let mut result = *self;
67        result.cyclotomic_exp_in_place(e);
68        result
69    }
70
71    /// Set `self` to be the result of exponentiating `self` by `e`,
72    /// using efficient cyclotomic algorithms.
73    ///
74    /// # Warning
75    ///
76    /// This method should be invoked only when `self` is in the cyclotomic subgroup.
77    fn cyclotomic_exp_in_place(&mut self, e: impl AsRef<[u64]>) {
78        if self.is_zero() {
79            return;
80        }
81
82        if Self::INVERSE_IS_FAST {
83            // We only use NAF-based exponentiation if inverses are fast to compute.
84            let naf = crate::biginteger::arithmetic::find_naf(e.as_ref());
85            exp_loop(self, naf.into_iter().rev())
86        } else {
87            exp_loop(
88                self,
89                crate::bits::BitIteratorBE::without_leading_zeros(e.as_ref()).map(|e| e as i8),
90            )
91        };
92    }
93}
94
95/// Helper function to calculate the double-and-add loop for exponentiation.
96fn exp_loop<F: CyclotomicMultSubgroup, I: Iterator<Item = i8>>(f: &mut F, e: I) {
97    // If the inverse is fast and we're using naf, we compute the inverse of the base.
98    // Otherwise we do nothing with the variable, so we default it to one.
99    let self_inverse = if F::INVERSE_IS_FAST {
100        f.cyclotomic_inverse().unwrap() // The inverse must exist because self is not zero.
101    } else {
102        F::one()
103    };
104    let mut res = F::one();
105    let mut found_nonzero = false;
106    for value in e {
107        if found_nonzero {
108            res.cyclotomic_square_in_place();
109        }
110
111        if value != 0 {
112            found_nonzero = true;
113
114            if value > 0 {
115                res *= &*f;
116            } else if F::INVERSE_IS_FAST {
117                // only use naf if inversion is fast.
118                res *= &self_inverse;
119            }
120        }
121    }
122    *f = res;
123}
ark_ff/fields/cyclotomic.rs

ark_ff/fields/
cyclotomic.rs
