# [−][src]Crate addchain

*Library for generating addition chains*

An addition chain `C`

for some positive integer `n`

is a sequence of integers that
have the following properties:

- The first integer is 1.
- The last integer is
`n`

. - Integers only appear once.
- Every integer is either the sum of two earlier integers, or double an earlier integer.

An addition chain corresponds to a series of `len(C) - 1`

primitive operations
(doubling and addition) that can be used to compute a target integer. An *optimal*
addition chain for `n`

has the shortest possible length, and therefore requires the
fewest operations to compute `n`

. This is particularly useful in cryptographic
algorithms such as modular exponentiation, where `n`

is usually at least `2^128`

.

# Example

To compute the number 87, we can represent it in binary as `1010111`

, and then using
the binary double-and-add algorithm (where we double for every bit, and add 1 for
every bit that is set to 1) we have the following steps:

```
i | n_i | Operation | b_i
---|-----|-----------|-----
0 | 1 | | 1
1 | 2 | n_0 * 2 | 0
2 | 4 | n_1 * 2 | 1
3 | 5 | n_2 + n_0 |
4 | 10 | n_3 * 2 | 0
5 | 20 | n_4 * 2 | 1
6 | 21 | n_5 + n_0 |
7 | 42 | n_6 * 2 | 1
8 | 43 | n_7 + n_0 |
9 | 86 | n_8 * 2 | 1
10 | 87 | n_9 + n_0 |
```

This corresponds to the addition chain `[1, 2, 4, 5, 10, 20, 21, 42, 43, 86, 87]`

,
which has length 11. However, the optimal addition chain length for 87 is 10, and
several addition chains can be constructed with optimal length. One such chain is
`[1, 2, 3, 6, 7, 10, 20, 40, 80, 87]`

, which corresponds to the following steps:

```
i | n_i | Operation
---|-----|----------
0 | 1 |
1 | 2 | n_0 * 2
2 | 3 | n_1 + n_0
3 | 6 | n_2 * 2
4 | 7 | n_3 + n_0
5 | 10 | n_4 + n_2
6 | 20 | n_5 * 2
7 | 40 | n_6 * 2
8 | 80 | n_7 * 2
9 | 87 | n_8 + n_4
```

# Usage

use addchain::{build_addition_chain, Step}; use num_bigint::BigUint; assert_eq!( build_addition_chain(BigUint::from(87u32)), vec![ Step::Double { index: 0 }, Step::Add { left: 1, right: 0 }, Step::Double { index: 2 }, Step::Add { left: 3, right: 0 }, Step::Add { left: 4, right: 2 }, Step::Double { index: 5 }, Step::Double { index: 6 }, Step::Double { index: 7 }, Step::Add { left: 8, right: 4 }, ], );

## Enums

Error | The error kinds returned by |

Step | A single step in computing an addition chain. |

## Functions

build_addition_chain | Generates a series of steps that will compute an addition chain for the given number. The addition chain is the shortest we can find using all available algorithms. |

build_steps | Converts an addition chain into a series of steps. |

find_shortest_chain | Returns the shortest addition chain we can find for the given number, using all available algorithms. |