# [−][src]Struct curve25519_dalek::backend::serial::scalar_mul::pippenger::Pippenger

Implements a version of Pippenger's algorithm.

The algorithm works as follows:

Let `n`

be a number of point-scalar pairs.
Let `w`

be a window of bits (6..8, chosen based on `n`

, see cost factor).

- Prepare
`2^(w-1) - 1`

buckets with indices`[1..2^(w-1))`

initialized with identity points. Bucket 0 is not needed as it would contain points multiplied by 0. - Convert scalars to a radix-
`2^w`

representation with signed digits in`[-2^w/2, 2^w/2]`

. Note: only the last digit may equal`2^w/2`

. - Starting with the last window, for each point
`i=[0..n)`

add it to a a bucket indexed by the point's scalar's value in the window. - Once all points in a window are sorted into buckets, add buckets by multiplying each by their index. Efficient way of doing it is to start with the last bucket and compute two sums: intermediate sum from the last to the first, and the full sum made of all intermediate sums.
- Shift the resulting sum of buckets by
`w`

bits by using`w`

doublings. - Add to the return value.
- Repeat the loop.

Approximate cost w/o wNAF optimizations (A = addition, D = doubling):

```
cost = (n*A + 2*(2^w/2)*A + w*D + A)*256/w
| | | | |
| | | | looping over 256/w windows
| | | adding to the result
sorting points | shifting the sum by w bits (to the next window, starting from last window)
one by one |
into buckets adding/subtracting all buckets
multiplied by their indexes
using a sum of intermediate sums
```

For large `n`

, dominant factor is (n*256/w) additions.
However, if `w`

is too big and `n`

is not too big, then `(2^w/2)*A`

could dominate.
Therefore, the optimal choice of `w`

grows slowly as `n`

grows.

This algorithm is adapted from section 4 of https://eprint.iacr.org/2012/549.pdf.

## Trait Implementations

`impl VartimeMultiscalarMul for Pippenger`

[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>>,

`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 Pippenger`

`impl Send for Pippenger`

`impl Sync for Pippenger`

`impl Unpin for Pippenger`

`impl UnwindSafe for Pippenger`

## 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>,