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

ark_ff/fields/
cyclotomic.rs
