p3_field/
exponentiation.rs

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

p3_field/
exponentiation.rs
