Type Alias curve25519_dalek::edwards::EdwardsBasepointTableRadix16

source ·

pub type EdwardsBasepointTableRadix16 = EdwardsBasepointTable;

Expand description

A type-alias for EdwardsBasepointTable because the latter is used as a constructor in the constants module.

Aliased Type§

struct EdwardsBasepointTableRadix16(/* private fields */);

Trait Implementations§

source §

impl BasepointTable for EdwardsBasepointTable

source §

fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTable

Create a table of precomputed multiples of basepoint.

source §

fn basepoint(&self) -> EdwardsPoint

Get the basepoint for this table as an EdwardsPoint.

source §

fn mul_base(&self, scalar: &Scalar) -> EdwardsPoint

The computation uses Pippeneger’s algorithm, as described for the specific case of radix-16 on page 13 of the Ed25519 paper.

Piggenger’s Algorithm Generalised

Write the scalar $a$ in radix-$w$, where $w$ is a power of 2, with coefficients in $[\frac{-w}{2},\frac{w}{2})$, i.e., $$ a = a_0 + a_1 w^1 + \cdots + a_{x} w^{x}, $$ with $$ \begin{aligned} \frac{-w}{2} \leq a_i < \frac{w}{2} &&\cdots&& \frac{-w}{2} \leq a_{x} \leq \frac{w}{2} \end{aligned} $$ and the number of additions, $x$, is given by $x = \lceil \frac{256}{w} \rceil$. Then $$ a B = a_0 B + a_1 w^1 B + \cdots + a_{x-1} w^{x-1} B. $$ Grouping even and odd coefficients gives $$ \begin{aligned} a B = \quad a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B \\ + a_1 w^1 B +& a_3 w^3 B + \cdots + a_{x-1} w^{x-1} B \\ = \quad(a_0 w^0 B +& a_2 w^2 B + \cdots + a_{x-2} w^{x-2} B) \\ + w(a_1 w^0 B +& a_3 w^2 B + \cdots + a_{x-1} w^{x-2} B). \\ \end{aligned} $$ For each $i = 0 \ldots 31$, we create a lookup table of $$ [w^{2i} B, \ldots, \frac{w}{2}\cdot w^{2i} B], $$ and use it to select $ y \cdot w^{2i} \cdot B $ in constant time.

The radix-$w$ representation requires that the scalar is bounded by $2^{255}$, which is always the case.

The above algorithm is trivially generalised to other powers-of-2 radices.

§