p3_field/
exponentiation.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
use crate::AbstractField;

pub fn exp_u64_by_squaring<AF: AbstractField>(val: AF, power: u64) -> AF {
    let mut current = val;
    let mut product = AF::ONE;

    for j in 0..bits_u64(power) {
        if (power >> j & 1) != 0 {
            product *= current.clone();
        }
        current = current.square();
    }
    product
}

const fn bits_u64(n: u64) -> usize {
    (64 - n.leading_zeros()) as usize
}

pub fn exp_1717986917<AF: AbstractField>(val: AF) -> AF {
    // Note that 5 * 1717986917 = 4*(2^31 - 2) + 1 = 1 mod p - 1.
    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{1717986917})^5 = a.
    // Note the binary expansion: 1717986917 = 1100110011001100110011001100101_2
    // This uses 30 Squares + 7 Multiplications => 37 Operations total.
    // Suspect it's possible to improve this with enough effort. For example 1717986918 takes only 4 Multiplications.
    let p1 = val;
    let p10 = p1.square();
    let p11 = p10.clone() * p1;
    let p101 = p10 * p11.clone();
    let p110000 = p11.exp_power_of_2(4);
    let p110011 = p110000 * p11.clone();
    let p11001100000000 = p110011.exp_power_of_2(8);
    let p11001100110011 = p11001100000000.clone() * p110011;
    let p1100110000000000000000 = p11001100000000.exp_power_of_2(8);
    let p1100110011001100110011 = p1100110000000000000000 * p11001100110011;
    let p11001100110011001100110000 = p1100110011001100110011.exp_power_of_2(4);
    let p11001100110011001100110011 = p11001100110011001100110000 * p11;
    let p1100110011001100110011001100000 = p11001100110011001100110011.exp_power_of_2(5);
    p1100110011001100110011001100000 * p101
}

pub fn exp_1420470955<AF: AbstractField>(val: AF) -> AF {
    // Note that 3 * 1420470955 = 2*(2^31 - 2^24) + 1 = 1 mod (p - 1).
    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{1420470955})^3 = a.
    // Note the binary expansion: 1420470955 = 1010100101010101010101010101011_2
    // This uses 29 Squares + 7 Multiplications => 36 Operations total.
    // Suspect it's possible to improve this with enough effort.
    let p1 = val;
    let p100 = p1.exp_power_of_2(2);
    let p101 = p100.clone() * p1.clone();
    let p10000 = p100.exp_power_of_2(2);
    let p10101 = p10000 * p101;
    let p10101000000 = p10101.clone().exp_power_of_2(6);
    let p10101010101 = p10101000000.clone() * p10101.clone();
    let p101010010101 = p10101000000 * p10101010101.clone();
    let p101010010101000000000000 = p101010010101.exp_power_of_2(12);
    let p101010010101010101010101 = p101010010101000000000000 * p10101010101;
    let p101010010101010101010101000000 = p101010010101010101010101.exp_power_of_2(6);
    let p101010010101010101010101010101 = p101010010101010101010101000000 * p10101;
    let p1010100101010101010101010101010 = p101010010101010101010101010101.square();
    p1010100101010101010101010101010 * p1.clone()
}

pub fn exp_1725656503<AF: AbstractField>(val: AF) -> AF {
    // Note that 7 * 1725656503 = 6*(2^31 - 2^27) + 1 = 1 mod (p - 1).
    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{1725656503})^7 = a.
    // Note the binary expansion: 1725656503 = 1100110110110110110110110110111_2
    // This uses 29 Squares + 8 Multiplications => 37 Operations total.
    // Suspect it's possible to improve this with enough effort.
    let p1 = val;
    let p10 = p1.square();
    let p11 = p10 * p1.clone();
    let p110 = p11.square();
    let p111 = p110.clone() * p1;
    let p11000 = p110.exp_power_of_2(2);
    let p11011 = p11000.clone() * p11;
    let p11000000 = p11000.exp_power_of_2(3);
    let p11011011 = p11000000.clone() * p11011;
    let p110011011 = p11011011.clone() * p11000000;
    let p110011011000000000 = p110011011.exp_power_of_2(9);
    let p110011011011011011 = p110011011000000000 * p11011011.clone();
    let p110011011011011011000000000 = p110011011011011011.exp_power_of_2(9);
    let p110011011011011011011011011 = p110011011011011011000000000 * p11011011;
    let p1100110110110110110110110110000 = p110011011011011011011011011.exp_power_of_2(4);
    p1100110110110110110110110110000 * p111
}

pub fn exp_10540996611094048183<AF: AbstractField>(val: AF) -> AF {
    // Note that 7*10540996611094048183 = 4*(2^64 - 2**32) + 1 = 1 mod (p - 1).
    // Thus as a^{p - 1} = 1 for all a \in F_p, (a^{10540996611094048183})^7 = a.
    // Also: 10540996611094048183 = 1001001001001001001001001001000110110110110110110110110110110111_2.
    // This uses 63 Squares + 8 Multiplications => 71 Operations total.
    // Suspect it's possible to improve this a little with enough effort.
    let p1 = val;
    let p10 = p1.square();
    let p11 = p10.clone() * p1.clone();
    let p100 = p10.square();
    let p111 = p100.clone() * p11.clone();
    let p100000000000000000000000000000000 = p100.exp_power_of_2(30);
    let p100000000000000000000000000000011 = p100000000000000000000000000000000 * p11;
    let p100000000000000000000000000000011000 =
        p100000000000000000000000000000011.exp_power_of_2(3);
    let p100100000000000000000000000000011011 =
        p100000000000000000000000000000011000 * p100000000000000000000000000000011;
    let p100100000000000000000000000000011011000000 =
        p100100000000000000000000000000011011.exp_power_of_2(6);
    let p100100100100000000000000000000011011011011 =
        p100100000000000000000000000000011011000000 * p100100000000000000000000000000011011.clone();
    let p100100100100000000000000000000011011011011000000000000 =
        p100100100100000000000000000000011011011011.exp_power_of_2(12);
    let p100100100100100100100100000000011011011011011011011011 =
        p100100100100000000000000000000011011011011000000000000
            * p100100100100000000000000000000011011011011;
    let p100100100100100100100100000000011011011011011011011011000000 =
        p100100100100100100100100000000011011011011011011011011.exp_power_of_2(6);
    let p100100100100100100100100100100011011011011011011011011011011 =
        p100100100100100100100100000000011011011011011011011011000000
            * p100100000000000000000000000000011011;
    let p1001001001001001001001001001000110110110110110110110110110110000 =
        p100100100100100100100100100100011011011011011011011011011011.exp_power_of_2(4);

    p1001001001001001001001001001000110110110110110110110110110110000 * p111
}