ark_ec/scalar_mul/
wnaf.rs

1use crate::PrimeGroup;
2use ark_ff::{BigInteger, PrimeField};
3use ark_std::vec::*;
4
5/// A helper type that contains all the context required for computing
6/// a window NAF multiplication of a group element by a scalar.
7pub struct WnafContext {
8    pub window_size: usize,
9}
10
11impl WnafContext {
12    /// Constructs a new context for a window of size `window_size`.
13    ///
14    /// # Panics
15    ///
16    /// This function will panic if not `2 <= window_size < 64`
17    pub fn new(window_size: usize) -> Self {
18        assert!(window_size >= 2);
19        assert!(window_size < 64);
20        Self { window_size }
21    }
22
23    pub fn table<G: PrimeGroup>(&self, mut base: G) -> Vec<G> {
24        let mut table = Vec::with_capacity(1 << (self.window_size - 1));
25        let dbl = base.double();
26
27        for _ in 0..(1 << (self.window_size - 1)) {
28            table.push(base);
29            base += &dbl;
30        }
31        table
32    }
33
34    /// Computes scalar multiplication of a group element `g` by `scalar`.
35    ///
36    /// This method uses the wNAF algorithm to perform the scalar
37    /// multiplication; first, it uses `Self::table` to calculate an
38    /// appropriate table of multiples of `g`, and then uses the wNAF
39    /// algorithm to compute the scalar multiple.
40    pub fn mul<G: PrimeGroup>(&self, g: G, scalar: &G::ScalarField) -> G {
41        let table = self.table(g);
42        self.mul_with_table(&table, scalar).unwrap()
43    }
44
45    /// Computes scalar multiplication of a group element by `scalar`.
46    /// `base_table` holds precomputed multiples of the group element; it can be
47    /// generated using `Self::table`. `scalar` is an element of
48    /// `G::ScalarField`.
49    ///
50    /// Returns `None` if the table is too small.
51    pub fn mul_with_table<G: PrimeGroup>(
52        &self,
53        base_table: &[G],
54        scalar: &G::ScalarField,
55    ) -> Option<G> {
56        if 1 << (self.window_size - 1) > base_table.len() {
57            return None;
58        }
59        let scalar_wnaf = scalar.into_bigint().find_wnaf(self.window_size).unwrap();
60
61        let mut result = G::zero();
62
63        let mut found_non_zero = false;
64
65        for n in scalar_wnaf.iter().rev() {
66            if found_non_zero {
67                result.double_in_place();
68            }
69
70            if *n != 0 {
71                found_non_zero = true;
72
73                if *n > 0 {
74                    result += &base_table[(n / 2) as usize];
75                } else {
76                    result -= &base_table[((-n) / 2) as usize];
77                }
78            }
79        }
80
81        Some(result)
82    }
83}
ark_ec/scalar_mul/wnaf.rs

ark_ec/scalar_mul/
wnaf.rs
