rust_sike/utils/
strategy.rs

1//! Utils for tree traversal strategies
2
3/// 2-torsion tree-traversal strategy
4pub type Torsion2Strategy = Vec<usize>;
5
6/// 3-torsion tree-traversal strategy
7pub type Torsion3Strategy = Vec<usize>;
8
9/// 2-torsion reference strategy for SIKEp434 (ref C.1.1.)
10pub const P434_TWO_TORSION_STRATEGY: [usize; 107] = [
11    48, 28, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2,
12    1, 1, 13, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5, 4, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 21, 12,
13    7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 9, 5, 3, 2, 1, 1, 1,
14    1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1,
15];
16
17/// 3-torsion reference strategy for SIKEp434 (ref C.1.2.)
18pub const P434_THREE_TORSION_STRATEGY: [usize; 136] = [
19    66, 33, 17, 9, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 1, 2, 1,
20    1, 4, 2, 1, 1, 2, 1, 1, 16, 8, 4, 2, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2,
21    1, 1, 4, 2, 1, 1, 2, 1, 1, 32, 16, 8, 4, 3, 1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2,
22    1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2,
23    1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1,
24];
25
26/// 2-torsion reference strategy for SIKEp503 (ref C.2.1.)
27pub const P503_TWO_TORSION_STRATEGY: [usize; 124] = [
28    61, 32, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2,
29    1, 1, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2,
30    1, 1, 29, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1,
31    2, 1, 1, 13, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 5, 4, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1,
32];
33
34/// 3-torsion reference strategy for SIKEp503 (ref C.2.2.)
35pub const P503_THREE_TORSION_STRATEGY: [usize; 158] = [
36    71, 38, 21, 13, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 5, 4, 2, 1, 1, 2, 1, 1, 2, 1, 1,
37    1, 9, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 17, 9, 5, 3, 2, 1, 1, 1, 1, 2,
38    1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 33, 17, 9, 5,
39    3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2,
40    1, 1, 16, 8, 4, 2, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1,
41    2, 1, 1,
42];
43
44/// 2-torsion reference strategy for SIKEp610 (ref C.3.1.)
45pub const P610_TWO_TORSION_STRATEGY: [usize; 151] = [
46    67, 37, 21, 12, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 9,
47    5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 16, 9, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1,
48    1, 4, 2, 1, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 33, 16, 8, 5, 2, 1, 1,
49    1, 2, 1, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 16, 8, 4, 2,
50    1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1,
51];
52
53/// 3-torsion reference strategy for SIKEp610 (ref C.3.2.)
54pub const P610_THREE_TORSION_STRATEGY: [usize; 191] = [
55    86, 48, 27, 15, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1,
56    1, 1, 1, 12, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 21, 12,
57    7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 9, 5, 3, 2, 1, 1, 1,
58    1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 38, 21, 12, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5,
59    3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 9, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 17,
60    9, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 1, 2, 1, 1, 4, 2, 1,
61    1, 2, 1, 1,
62];
63
64/// 2-torsion reference strategy for SIKEp751 (ref C.4.1.)
65pub const P751_TWO_TORSION_STRATEGY: [usize; 185] = [
66    80, 48, 27, 15, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1,
67    1, 1, 1, 12, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 21, 12,
68    7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 9, 5, 3, 2, 1, 1, 1,
69    1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1, 33, 20, 12, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 5,
70    3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 8, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 2, 1, 1, 16, 8,
71    4, 2, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1,
72];
73
74/// 3-torsion reference strategy for SIKEp751 (ref C.4.2.)
75pub const P751_THREE_TORSION_STRATEGY: [usize; 238] = [
76    112, 63, 32, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1,
77    1, 2, 1, 1, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1,
78    1, 2, 1, 1, 31, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2,
79    1, 1, 2, 1, 1, 15, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 7, 4, 2, 1, 1, 2, 1, 1, 3, 2,
80    1, 1, 1, 1, 49, 31, 16, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 8, 4, 2, 1, 1, 2, 1, 1, 4,
81    2, 1, 1, 2, 1, 1, 15, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 7, 4, 2, 1, 1, 2, 1, 1, 3,
82    2, 1, 1, 1, 1, 21, 12, 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1, 5, 3, 2, 1, 1, 1, 1, 2, 1,
83    1, 1, 9, 5, 3, 2, 1, 1, 1, 1, 2, 1, 1, 1, 4, 2, 1, 1, 1, 2, 1, 1,
84];
85
86/// Computing optimised strategy (ref `compute_strategy`, Algorithm 46 p. 75).
87///   * Input: strategy size `n`, parameters `p`, `q`
88///   * Output: optimal strategy of size `n`  
89///
90/// # Examples
91/// ```rust
92/// use rust_sike::compute_strategy;
93/// let strat = compute_strategy(12, 13, 14);
94/// println!("{:?}", strat);
95/// ```
96pub fn compute_strategy(n: usize, p: u64, q: u64) -> Result<Vec<usize>, &'static str> {
97    // 1.
98    let mut strategies = vec![vec![]];
99
100    // 2.
101    let mut cost = vec![0];
102
103    let eval = |c: &Vec<u64>, i: u64, b: u64| {
104        c[(i - b) as usize - 1] + c[b as usize - 1] + b * p + (i - b) * q
105    };
106
107    // 3.
108    for i in 2..=(n as u64 + 1) {
109        // 4.
110        let mut min_val = eval(&cost, i, 1);
111        let mut b = 1;
112        for b_val in 2..i {
113            let c_val = eval(&cost, i, b_val);
114            if c_val < min_val {
115                min_val = c_val;
116                b = b_val;
117            }
118        }
119
120        // 5.
121        let mut new_strat = vec![b as usize];
122        new_strat.extend(&strategies[(i - b - 1) as usize]);
123        new_strat.extend(&strategies[b as usize - 1]);
124        strategies.push(new_strat);
125
126        // 6.
127        cost.push(min_val);
128    }
129
130    // 7.
131    match strategies.last() {
132        Some(s) => Ok(s.to_vec()),
133        None => Err("No valid strategy found"),
134    }
135}
rust_sike/utils/strategy.rs

rust_sike/utils/
strategy.rs
