pairing_plus/
wnaf.rs

1use super::{CurveProjective, PrimeField, PrimeFieldRepr};
2
3/// Replaces the contents of `table` with a w-NAF window table for the given window size.
4pub(crate) fn wnaf_table<G: CurveProjective>(table: &mut Vec<G>, mut base: G, window: usize) {
5    table.truncate(0);
6    table.reserve(1 << (window - 1));
7
8    let mut dbl = base;
9    dbl.double();
10
11    for _ in 0..(1 << (window - 1)) {
12        table.push(base);
13        base.add_assign(&dbl);
14    }
15}
16
17/// Replaces the contents of `wnaf` with the w-NAF representation of a scalar.
18pub(crate) fn wnaf_form<S: PrimeFieldRepr>(wnaf: &mut Vec<i64>, mut c: S, window: usize) {
19    wnaf.truncate(0);
20
21    while !c.is_zero() {
22        let mut u;
23        if c.is_odd() {
24            u = (c.as_ref()[0] % (1 << (window + 1))) as i64;
25
26            if u > (1 << window) {
27                u -= 1 << (window + 1);
28            }
29
30            if u > 0 {
31                c.sub_noborrow(&S::from(u as u64));
32            } else {
33                c.add_nocarry(&S::from((-u) as u64));
34            }
35        } else {
36            u = 0;
37        }
38
39        wnaf.push(u);
40
41        c.div2();
42    }
43}
44
45/// Performs w-NAF exponentiation with the provided window table and w-NAF form scalar.
46///
47/// This function must be provided a `table` and `wnaf` that were constructed with
48/// the same window size; otherwise, it may panic or produce invalid results.
49pub(crate) fn wnaf_exp<G: CurveProjective>(table: &[G], wnaf: &[i64]) -> G {
50    let mut result = G::zero();
51
52    let mut found_one = false;
53
54    for n in wnaf.iter().rev() {
55        if found_one {
56            result.double();
57        }
58
59        if *n != 0 {
60            found_one = true;
61
62            if *n > 0 {
63                result.add_assign(&table[(n / 2) as usize]);
64            } else {
65                result.sub_assign(&table[((-n) / 2) as usize]);
66            }
67        }
68    }
69
70    result
71}
72
73/// A "w-ary non-adjacent form" exponentiation context.
74#[derive(Debug)]
75pub struct Wnaf<W, B, S> {
76    base: B,
77    scalar: S,
78    window_size: W,
79}
80
81impl<G: CurveProjective> Wnaf<(), Vec<G>, Vec<i64>> {
82    /// Construct a new wNAF context without allocating.
83    pub fn new() -> Self {
84        Wnaf {
85            base: vec![],
86            scalar: vec![],
87            window_size: (),
88        }
89    }
90
91    /// Given a base and a number of scalars, compute a window table and return a `Wnaf` object that
92    /// can perform exponentiations with `.scalar(..)`.
93    pub fn base(&mut self, base: G, num_scalars: usize) -> Wnaf<usize, &[G], &mut Vec<i64>> {
94        // Compute the appropriate window size based on the number of scalars.
95        let window_size = G::recommended_wnaf_for_num_scalars(num_scalars);
96
97        // Compute a wNAF table for the provided base and window size.
98        wnaf_table(&mut self.base, base, window_size);
99
100        // Return a Wnaf object that immutably borrows the computed base storage location,
101        // but mutably borrows the scalar storage location.
102        Wnaf {
103            base: &self.base[..],
104            scalar: &mut self.scalar,
105            window_size,
106        }
107    }
108
109    /// Given a scalar, compute its wNAF representation and return a `Wnaf` object that can perform
110    /// exponentiations with `.base(..)`.
111    pub fn scalar(
112        &mut self,
113        scalar: <<G as CurveProjective>::Scalar as PrimeField>::Repr,
114    ) -> Wnaf<usize, &mut Vec<G>, &[i64]> {
115        // Compute the appropriate window size for the scalar.
116        let window_size = G::recommended_wnaf_for_scalar(scalar);
117
118        // Compute the wNAF form of the scalar.
119        wnaf_form(&mut self.scalar, scalar, window_size);
120
121        // Return a Wnaf object that mutably borrows the base storage location, but
122        // immutably borrows the computed wNAF form scalar location.
123        Wnaf {
124            base: &mut self.base,
125            scalar: &self.scalar[..],
126            window_size,
127        }
128    }
129}
130
131impl<'a, G: CurveProjective> Wnaf<usize, &'a [G], &'a mut Vec<i64>> {
132    /// Constructs new space for the scalar representation while borrowing
133    /// the computed window table, for sending the window table across threads.
134    pub fn shared(&self) -> Wnaf<usize, &'a [G], Vec<i64>> {
135        Wnaf {
136            base: self.base,
137            scalar: vec![],
138            window_size: self.window_size,
139        }
140    }
141}
142
143impl<'a, G: CurveProjective> Wnaf<usize, &'a mut Vec<G>, &'a [i64]> {
144    /// Constructs new space for the window table while borrowing
145    /// the computed scalar representation, for sending the scalar representation
146    /// across threads.
147    pub fn shared(&self) -> Wnaf<usize, Vec<G>, &'a [i64]> {
148        Wnaf {
149            base: vec![],
150            scalar: self.scalar,
151            window_size: self.window_size,
152        }
153    }
154}
155
156impl<B, S: AsRef<[i64]>> Wnaf<usize, B, S> {
157    /// Performs exponentiation given a base.
158    pub fn base<G: CurveProjective>(&mut self, base: G) -> G
159    where
160        B: AsMut<Vec<G>>,
161    {
162        wnaf_table(self.base.as_mut(), base, self.window_size);
163        wnaf_exp(self.base.as_mut(), self.scalar.as_ref())
164    }
165}
166
167impl<B, S: AsMut<Vec<i64>>> Wnaf<usize, B, S> {
168    /// Performs exponentiation given a scalar.
169    pub fn scalar<G: CurveProjective>(
170        &mut self,
171        scalar: <<G as CurveProjective>::Scalar as PrimeField>::Repr,
172    ) -> G
173    where
174        B: AsRef<[G]>,
175    {
176        wnaf_form(self.scalar.as_mut(), scalar, self.window_size);
177        wnaf_exp(self.base.as_ref(), self.scalar.as_mut())
178    }
179}
pairing_plus/wnaf.rs

pairing_plus/
wnaf.rs
