# [−][src]Struct curve25519_dalek::backend::serial::scalar_mul::straus::Straus

Perform multiscalar multiplication by the interleaved window method, also known as Straus' method (since it was apparently first published by Straus in 1964, as a solution to a problem posted in the American Mathematical Monthly in 1963).

It is easy enough to reinvent, and has been repeatedly. The basic idea is that when computing \[ Q = s_1 P_1 + \cdots + s_n P_n \] by means of additions and doublings, the doublings can be shared across the \( P_i \).

We implement two versions, a constant-time algorithm using fixed windows and a variable-time algorithm using sliding windows. They are slight variations on the same idea, and are described in more detail in the respective implementations.

## Trait Implementations

`impl MultiscalarMul for Straus`

[src]

`type Point = EdwardsPoint`

The type of point being multiplied, e.g., `RistrettoPoint`

.

`fn multiscalar_mul<I, J>(scalars: I, points: J) -> EdwardsPoint where`

I: IntoIterator,

I::Item: Borrow<Scalar>,

J: IntoIterator,

J::Item: Borrow<EdwardsPoint>,

[src]

I: IntoIterator,

I::Item: Borrow<Scalar>,

J: IntoIterator,

J::Item: Borrow<EdwardsPoint>,

Constant-time Straus using a fixed window of size \(4\).

Our goal is to compute \[ Q = s_1 P_1 + \cdots + s_n P_n. \]

For each point \( P_i \), precompute a lookup table of \[ P_i, 2P_i, 3P_i, 4P_i, 5P_i, 6P_i, 7P_i, 8P_i. \]

For each scalar \( s_i \), compute its radix-\(2^4\) signed digits \( s_{i,j} \), i.e., \[ s_i = s_{i,0} + s_{i,1} 16^1 + ... + s_{i,63} 16^{63}, \] with \( -8 \leq s_{i,j} < 8 \). Since \( 0 \leq |s_{i,j}| \leq 8 \), we can retrieve \( s_{i,j} P_i \) from the lookup table with a conditional negation: using signed digits halves the required table size.

Then as in the single-base fixed window case, we have \[ \begin{aligned} s_i P_i &= P_i (s_{i,0} + s_{i,1} 16^1 + \cdots + s_{i,63} 16^{63}) \\ s_i P_i &= P_i s_{i,0} + P_i s_{i,1} 16^1 + \cdots + P_i s_{i,63} 16^{63} \\ s_i P_i &= P_i s_{i,0} + 16(P_i s_{i,1} + 16( \cdots +16P_i s_{i,63})\cdots ) \end{aligned} \] so each \( s_i P_i \) can be computed by alternately adding a precomputed multiple \( P_i s_{i,j} \) of \( P_i \) and repeatedly doubling.

Now consider the two-dimensional sum \[ \begin{aligned} s_1 P_1 &=& P_1 s_{1,0} &+& 16 (P_1 s_{1,1} &+& 16 ( \cdots &+& 16 P_1 s_{1,63}&) \cdots ) \\ + & & + & & + & & & & + & \\ s_2 P_2 &=& P_2 s_{2,0} &+& 16 (P_2 s_{2,1} &+& 16 ( \cdots &+& 16 P_2 s_{2,63}&) \cdots ) \\ + & & + & & + & & & & + & \\ \vdots & & \vdots & & \vdots & & & & \vdots & \\ + & & + & & + & & & & + & \\ s_n P_n &=& P_n s_{n,0} &+& 16 (P_n s_{n,1} &+& 16 ( \cdots &+& 16 P_n s_{n,63}&) \cdots ) \end{aligned} \] The sum of the left-hand column is the result \( Q \); by computing the two-dimensional sum on the right column-wise, top-to-bottom, then right-to-left, we need to multiply by \( 16\) only once per column, sharing the doublings across all of the input points.

`impl VartimeMultiscalarMul for Straus`

[src]

`type Point = EdwardsPoint`

The type of point being multiplied, e.g., `RistrettoPoint`

.

`fn optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<EdwardsPoint> where`

I: IntoIterator,

I::Item: Borrow<Scalar>,

J: IntoIterator<Item = Option<EdwardsPoint>>,

[src]

I: IntoIterator,

I::Item: Borrow<Scalar>,

J: IntoIterator<Item = Option<EdwardsPoint>>,

Variable-time Straus using a non-adjacent form of width \(5\).

This is completely similar to the constant-time code, but we use a non-adjacent form for the scalar, and do not do table lookups in constant time.

The non-adjacent form has signed, odd digits. Using only odd digits halves the table size (since we only need odd multiples), or gives fewer additions for the same table size.

`fn vartime_multiscalar_mul<I, J>(scalars: I, points: J) -> Self::Point where`

I: IntoIterator,

I::Item: Borrow<Scalar>,

J: IntoIterator,

J::Item: Borrow<Self::Point>,

Self::Point: Clone,

[src]

I: IntoIterator,

I::Item: Borrow<Scalar>,

J: IntoIterator,

J::Item: Borrow<Self::Point>,

Self::Point: Clone,

## Auto Trait Implementations

`impl RefUnwindSafe for Straus`

`impl Send for Straus`

`impl Sync for Straus`

`impl Unpin for Straus`

`impl UnwindSafe for Straus`

## Blanket Implementations

`impl<T> Any for T where`

T: 'static + ?Sized,

[src]

T: 'static + ?Sized,

`impl<T> Borrow<T> for T where`

T: ?Sized,

[src]

T: ?Sized,

`impl<T> BorrowMut<T> for T where`

T: ?Sized,

[src]

T: ?Sized,

`fn borrow_mut(&mut self) -> &mut T`

[src]

`impl<T, U> Cast<U> for T where`

U: FromCast<T>,

U: FromCast<T>,

`fn cast(self) -> U`

`impl<T> From<T> for T`

[src]

`impl<T> FromBits<T> for T`

`fn from_bits(t: T) -> T`

`impl<T> FromCast<T> for T`

`fn from_cast(t: T) -> T`

`impl<T, U> Into<U> for T where`

U: From<T>,

[src]

U: From<T>,

`impl<T, U> IntoBits<U> for T where`

U: FromBits<T>,

U: FromBits<T>,

`fn into_bits(self) -> U`

`impl<T> Same<T> for T`

`type Output = T`

Should always be `Self`

`impl<T, U> TryFrom<U> for T where`

U: Into<T>,

[src]

U: Into<T>,

`type Error = !`

The type returned in the event of a conversion error.

`fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>`

[src]

`impl<T, U> TryInto<U> for T where`

U: TryFrom<T>,

[src]

U: TryFrom<T>,