Fixed-window non-adjacent form (WNAF) scalar decomposition for elliptic curve scalar multiplication.
More...
|
| template<size_t bits, size_t bit_position> |
| uint64_t | get_wnaf_bits_const (const uint64_t *scalar) noexcept |
| | Extract a window of bits consecutive bits starting at bit_position from a 128-bit scalar.
|
| |
| uint64_t | get_wnaf_bits (const uint64_t *scalar, const uint64_t bits, const uint64_t bit_position) noexcept |
| | A variant of the previous function that the bit position and number of bits are provided at runtime.
|
| |
| void | fixed_wnaf (const uint64_t *scalar, uint64_t *wnaf, bool &skew_map, const uint64_t point_index, const uint64_t num_points, const size_t wnaf_bits) noexcept |
| | Performs fixed-window non-adjacent form (WNAF) computation for scalar multiplication.
|
| |
| template<size_t num_points, size_t wnaf_bits, size_t round_i> |
| void | wnaf_round (uint64_t *scalar, uint64_t *wnaf, const uint64_t point_index, const uint64_t previous) noexcept |
| | Recursive WNAF round for a fixed 127-bit scalar (SCALAR_BITS).
|
| |
| template<size_t scalar_bits, size_t num_points, size_t wnaf_bits, size_t round_i> |
| void | wnaf_round (uint64_t *scalar, uint64_t *wnaf, const uint64_t point_index, const uint64_t previous) noexcept |
| | Recursive WNAF round for an arbitrary-width scalar.
|
| |
| template<size_t num_points, size_t wnaf_bits> |
| void | fixed_wnaf (uint64_t *scalar, uint64_t *wnaf, bool &skew_map, const size_t point_index) noexcept |
| |
| template<size_t num_bits, size_t num_points, size_t wnaf_bits> |
| void | fixed_wnaf (uint64_t *scalar, uint64_t *wnaf, bool &skew_map, const size_t point_index) noexcept |
| |
Fixed-window non-adjacent form (WNAF) scalar decomposition for elliptic curve scalar multiplication.
WNAF decomposes a scalar into a sequence of odd signed digits in the range [-(2^w - 1), 2^w - 1], where w = wnaf_bits. Each digit is packed into a uint64_t entry with the following bit layout:
Bit 63 32 31 30 0
┌────────────────────────┬────┬──────────────────────────┐ │ point_index │sign│ table_index │ └────────────────────────┴────┴──────────────────────────┘
- table_index (bits 0-30): abs(digit) >> 1. Since all digits are odd, the absolute value is always 2*k + 1 for some k, so table_index = k. This directly indexes a precomputed lookup table of odd multiples [1·P, 3·P, 5·P, ...]. In the Pippenger MSM path, this is the bucket index that determines which bucket the point is accumulated into.
- sign (bit 31): 0 = positive digit, 1 = negative digit (negate the point's y-coordinate).
- point_index (bits 32-63): identifies which input point this entry refers to. In single-scalar multiplication this is 0. In multi-scalar multiplication (Pippenger), this records which of the N input points the entry belongs to, since the schedule is later sorted by bucket and the original point ordering is lost.
The template wnaf_round / fixed_wnaf variants shift point_index into bits 32+ internally. The runtime fixed_wnaf variant expects the caller to pass point_index pre-shifted.
| void bb::wnaf::fixed_wnaf |
( |
const uint64_t * |
scalar, |
|
|
uint64_t * |
wnaf, |
|
|
bool & |
skew_map, |
|
|
const uint64_t |
point_index, |
|
|
const uint64_t |
num_points, |
|
|
const size_t |
wnaf_bits |
|
) |
| |
|
inlinenoexcept |
Performs fixed-window non-adjacent form (WNAF) computation for scalar multiplication.
WNAF is a method for representing integers which optimizes the number of non-zero terms, which in turn optimizes the number of point doublings in scalar multiplication, in turn aiding efficiency.
- Parameters
-
| scalar | Pointer to 128-bit scalar for which WNAF is to be computed. |
| wnaf | Pointer to num_points+1 size array where the computed WNAF will be stored. |
| skew_map | Reference to a boolean variable which will be set based on the least significant bit of the scalar. |
| point_index | The index of the point being computed in the context of multiple point multiplication. |
| num_points | The number of points being computed in parallel. |
| wnaf_bits | The number of bits to use in each window of the WNAF representation. |
Definition at line 117 of file wnaf.hpp.
template<size_t bits, size_t bit_position>
| uint64_t bb::wnaf::get_wnaf_bits_const |
( |
const uint64_t * |
scalar | ) |
|
|
inlinenoexcept |
Extract a window of bits consecutive bits starting at bit_position from a 128-bit scalar.
- Template Parameters
-
| bits | The number of bits in the window (0 returns 0). |
| bit_position | The starting bit index within the 128-bit scalar. |
- Parameters
-
| scalar | Pointer to a 128-bit scalar stored as two consecutive uint64_t limbs (little-endian word order). |
- Returns
- The integer value of the extracted bit window.
We determine which 64-bit limb(s) the window touches by computing lo_limb_idx = bit_position / 64 and hi_limb_idx = (bit_position + bits - 1) / 64. For the low limb, we right-shift by (bit_position % 64) to align the desired bits to position 0. If the window fits entirely within one limb (lo_limb_idx == hi_limb_idx), we simply mask off bits bits. Otherwise, the window straddles two limbs: we left-shift the high limb by (64 - bit_position % 64) to place its contributing bits adjacent to the low limb's bits, OR them together, and then mask to bits bits.
Definition at line 59 of file wnaf.hpp.
template<size_t num_points, size_t wnaf_bits, size_t round_i>
| void bb::wnaf::wnaf_round |
( |
uint64_t * |
scalar, |
|
|
uint64_t * |
wnaf, |
|
|
const uint64_t |
point_index, |
|
|
const uint64_t |
previous |
|
) |
| |
|
inlinenoexcept |
Recursive WNAF round for a fixed 127-bit scalar (SCALAR_BITS).
Processes one window per recursive call, using compile-time unrolling via round_i. Uses the runtime get_wnaf_bits for bit extraction. The WNAF output array is interleaved: entry for round r is stored at index (wnaf_entries - r) << log2(num_points), so that entries for the same round across different points are contiguous for cache locality. Each entry packs: bits [0..30] = lookup table index, bit 31 = sign, bits [32..63] = point_index.
Definition at line 168 of file wnaf.hpp.
template<size_t scalar_bits, size_t num_points, size_t wnaf_bits, size_t round_i>
| void bb::wnaf::wnaf_round |
( |
uint64_t * |
scalar, |
|
|
uint64_t * |
wnaf, |
|
|
const uint64_t |
point_index, |
|
|
const uint64_t |
previous |
|
) |
| |
|
inlinenoexcept |
Recursive WNAF round for an arbitrary-width scalar.
Same algorithm as the SCALAR_BITS overload above, but parametrized by scalar_bits so it can handle scalars of any bit width (e.g., after an endomorphism split produces shorter scalars). Uses the compile-time get_wnaf_bits_const for bit extraction since all parameters are template constants. Correctly handles the edge case where scalar_bits is an exact multiple of wnaf_bits (the final window is a full wnaf_bits wide rather than the remainder).
Definition at line 201 of file wnaf.hpp.
1.9.8