addchain：生成加法链的Rust crate

用法

查找一个短加法链

let chain = addchain::find_shortest_chain(num_bigint::BigUint::from(87u32));

构建加法链的步骤

let steps = addchain::build_addition_chain(num_bigint::BigUint::from(87u32));

许可证

许可协议为以下之一

• Apache License，版本2.0，(LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

任选其一。

贡献

除非你明确声明，否则根据Apache-2.0许可证定义，你有意提交的任何贡献，都应按照上述方式双重许可，不附加任何额外条款或条件。

lib.rs:

生成加法链的库

对于某个正整数 n 的加法链 C 是一个整数序列，它具有以下性质

• 第一个整数是 1。
• 最后一个整数是 n。
• 整数只出现一次。
• 每个整数要么是两个较早整数的和，要么是较早整数的两倍。

一个加法链对应一系列 len(C) - 1 基本操作（加倍和加法），可以用来计算目标整数。对于 n 的 最优 加法链具有最短的长度，因此需要最少的操作来计算 n。这在密码学算法中特别有用，如模幂运算，其中 n 通常至少为 2^128。

示例

为了计算数字 87，我们可以将其表示为二进制 1010111，然后使用二进制加倍和加法算法（其中每个位加倍，每个置位为 1 的位加 1）我们得到以下步骤

 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 |

这对应于加法链 [1, 2, 4, 5, 10, 20, 21, 42, 43, 86, 87]，其长度为11。然而，87的最优加法链长度为10，并且可以构造出多个具有最优长度的加法链。其中之一是 [1, 2, 3, 6, 7, 10, 20, 40, 80, 87]，它对应以下步骤

 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

用法

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 },
    ],
);