p3_field/
exponentiation.rs

Help
1use crate::FieldAlgebra;
2
3pub fn exp_u64_by_squaring<FA: FieldAlgebra>(val: FA, power: u64) -> FA {
4    let mut current = val;
5    let mut product = FA::ONE;
6
7    for j in 0..bits_u64(power) {
8        if (power >> j & 1) != 0 {
9            product *= current.clone();
10        }
11        current = current.square();
12    }
13    product
14}
15
16const fn bits_u64(n: u64) -> usize {
17    (64 - n.leading_zeros()) as usize
18}
19
20pub fn exp_1717986917<FA: FieldAlgebra>(val: FA) -> FA {
21    // Note that 5 * 1717986917 = 4*(2^31 - 2) + 1 = 1 mod p - 1.
22    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{1717986917})^5 = a.
23    // Note the binary expansion: 1717986917 = 1100110011001100110011001100101_2
24    // This uses 30 Squares + 7 Multiplications => 37 Operations total.
25    // Suspect it's possible to improve this with enough effort. For example 1717986918 takes only 4 Multiplications.
26    let p1 = val;
27    let p10 = p1.square();
28    let p11 = p10.clone() * p1;
29    let p101 = p10 * p11.clone();
30    let p110000 = p11.exp_power_of_2(4);
31    let p110011 = p110000 * p11.clone();
32    let p11001100000000 = p110011.exp_power_of_2(8);
33    let p11001100110011 = p11001100000000.clone() * p110011;
34    let p1100110000000000000000 = p11001100000000.exp_power_of_2(8);
35    let p1100110011001100110011 = p1100110000000000000000 * p11001100110011;
36    let p11001100110011001100110000 = p1100110011001100110011.exp_power_of_2(4);
37    let p11001100110011001100110011 = p11001100110011001100110000 * p11;
38    let p1100110011001100110011001100000 = p11001100110011001100110011.exp_power_of_2(5);
39    p1100110011001100110011001100000 * p101
40}
41
42pub fn exp_1420470955<FA: FieldAlgebra>(val: FA) -> FA {
43    // Note that 3 * 1420470955 = 2*(2^31 - 2^24) + 1 = 1 mod (p - 1).
44    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{1420470955})^3 = a.
45    // Note the binary expansion: 1420470955 = 1010100101010101010101010101011_2
46    // This uses 29 Squares + 7 Multiplications => 36 Operations total.
47    // Suspect it's possible to improve this with enough effort.
48    let p1 = val;
49    let p100 = p1.exp_power_of_2(2);
50    let p101 = p100.clone() * p1.clone();
51    let p10000 = p100.exp_power_of_2(2);
52    let p10101 = p10000 * p101;
53    let p10101000000 = p10101.clone().exp_power_of_2(6);
54    let p10101010101 = p10101000000.clone() * p10101.clone();
55    let p101010010101 = p10101000000 * p10101010101.clone();
56    let p101010010101000000000000 = p101010010101.exp_power_of_2(12);
57    let p101010010101010101010101 = p101010010101000000000000 * p10101010101;
58    let p101010010101010101010101000000 = p101010010101010101010101.exp_power_of_2(6);
59    let p101010010101010101010101010101 = p101010010101010101010101000000 * p10101;
60    let p1010100101010101010101010101010 = p101010010101010101010101010101.square();
61    p1010100101010101010101010101010 * p1.clone()
62}
63
64pub fn exp_1725656503<FA: FieldAlgebra>(val: FA) -> FA {
65    // Note that 7 * 1725656503 = 6*(2^31 - 2^27) + 1 = 1 mod (p - 1).
66    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{1725656503})^7 = a.
67    // Note the binary expansion: 1725656503 = 1100110110110110110110110110111_2
68    // This uses 29 Squares + 8 Multiplications => 37 Operations total.
69    // Suspect it's possible to improve this with enough effort.
70    let p1 = val;
71    let p10 = p1.square();
72    let p11 = p10 * p1.clone();
73    let p110 = p11.square();
74    let p111 = p110.clone() * p1;
75    let p11000 = p110.exp_power_of_2(2);
76    let p11011 = p11000.clone() * p11;
77    let p11000000 = p11000.exp_power_of_2(3);
78    let p11011011 = p11000000.clone() * p11011;
79    let p110011011 = p11011011.clone() * p11000000;
80    let p110011011000000000 = p110011011.exp_power_of_2(9);
81    let p110011011011011011 = p110011011000000000 * p11011011.clone();
82    let p110011011011011011000000000 = p110011011011011011.exp_power_of_2(9);
83    let p110011011011011011011011011 = p110011011011011011000000000 * p11011011;
84    let p1100110110110110110110110110000 = p110011011011011011011011011.exp_power_of_2(4);
85    p1100110110110110110110110110000 * p111
86}
87
88pub fn exp_10540996611094048183<FA: FieldAlgebra>(val: FA) -> FA {
89    // Note that 7*10540996611094048183 = 4*(2^64 - 2**32) + 1 = 1 mod (p - 1).
90    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{10540996611094048183})^7 = a.
91    // Also: 10540996611094048183 = 1001001001001001001001001001000110110110110110110110110110110111_2.
92    // This uses 63 Squares + 8 Multiplications => 71 Operations total.
93    // Suspect it's possible to improve this a little with enough effort.
94    let p1 = val;
95    let p10 = p1.square();
96    let p11 = p10.clone() * p1.clone();
97    let p100 = p10.square();
98    let p111 = p100.clone() * p11.clone();
99    let p100000000000000000000000000000000 = p100.exp_power_of_2(30);
100    let p100000000000000000000000000000011 = p100000000000000000000000000000000 * p11;
101    let p100000000000000000000000000000011000 =
102        p100000000000000000000000000000011.exp_power_of_2(3);
103    let p100100000000000000000000000000011011 =
104        p100000000000000000000000000000011000 * p100000000000000000000000000000011;
105    let p100100000000000000000000000000011011000000 =
106        p100100000000000000000000000000011011.exp_power_of_2(6);
107    let p100100100100000000000000000000011011011011 =
108        p100100000000000000000000000000011011000000 * p100100000000000000000000000000011011.clone();
109    let p100100100100000000000000000000011011011011000000000000 =
110        p100100100100000000000000000000011011011011.exp_power_of_2(12);
111    let p100100100100100100100100000000011011011011011011011011 =
112        p100100100100000000000000000000011011011011000000000000
113            * p100100100100000000000000000000011011011011;
114    let p100100100100100100100100000000011011011011011011011011000000 =
115        p100100100100100100100100000000011011011011011011011011.exp_power_of_2(6);
116    let p100100100100100100100100100100011011011011011011011011011011 =
117        p100100100100100100100100000000011011011011011011011011000000
118            * p100100000000000000000000000000011011;
119    let p1001001001001001001001001001000110110110110110110110110110110000 =
120        p100100100100100100100100100100011011011011011011011011011011.exp_power_of_2(4);
121
122    p1001001001001001001001001001000110110110110110110110110110110000 * p111
123}
p3_field/exponentiation.rs

p3_field/
exponentiation.rs
