p3-field 0.5.2

A modular framework for finite fields, including support for generic binomial extensions, SIMD-packed field arithmetic.
Documentation 
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

use crate::PrimeCharacteristicRing;

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

/// Compute the exponential `x -> x^1717986917` using a custom addition chain.
///
/// This map computes the fifth root of `x` if `x` is a member of the field `Mersenne31`.
/// This follows from the computation: `5 * 1717986917 = 4*(2^31 - 2) + 1 = 1 mod p - 1`.
#[must_use]
pub fn exp_1717986917<R: PrimeCharacteristicRing>(val: R) -> R {
    // 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.dup() * p1;
    let p101 = p10 * p11.dup();
    let p110000 = p11.exp_power_of_2(4);
    let p110011 = p110000 * p11.dup();
    let p11001100000000 = p110011.exp_power_of_2(8);
    let p11001100110011 = p11001100000000.dup() * 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
}

/// Compute the exponential `x -> x^1420470955` using a custom addition chain.
///
/// This map computes the third root of `x` if `x` is a member of the field `KoalaBear`.
/// This follows from the computation: `3 * 1420470955 = 2*(2^31 - 2^24) + 1 = 1 mod (p - 1)`.
#[must_use]
pub fn exp_1420470955<R: PrimeCharacteristicRing>(val: R) -> R {
    // 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.dup() * p1.dup();
    let p10000 = p100.exp_power_of_2(2);
    let p10101 = p10000 * p101;
    let p10101000000 = p10101.exp_power_of_2(6);
    let p10101010101 = p10101000000.dup() * p10101.dup();
    let p101010010101 = p10101000000 * p10101010101.dup();
    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
}

/// Compute the exponential `x -> x^1725656503` using a custom addition chain.
///
/// This map computes the seventh root of `x` if `x` is a member of the field `BabyBear`.
/// This follows from the computation: `7 * 1725656503 = 6*(2^31 - 2^27) + 1 = 1 mod (p - 1)`.
#[must_use]
pub fn exp_1725656503<R: PrimeCharacteristicRing>(val: R) -> R {
    // 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.dup();
    let p110 = p11.square();
    let p111 = p110.dup() * p1;
    let p11000 = p110.exp_power_of_2(2);
    let p11011 = p11000.dup() * p11;
    let p11000000 = p11000.exp_power_of_2(3);
    let p11011011 = p11000000.dup() * p11011;
    let p110011011 = p11011011.dup() * p11000000;
    let p110011011000000000 = p110011011.exp_power_of_2(9);
    let p110011011011011011 = p110011011000000000 * p11011011.dup();
    let p110011011011011011000000000 = p110011011011011011.exp_power_of_2(9);
    let p110011011011011011011011011 = p110011011011011011000000000 * p11011011;
    let p1100110110110110110110110110000 = p110011011011011011011011011.exp_power_of_2(4);
    p1100110110110110110110110110000 * p111
}

/// Compute the exponential `x -> x^10540996611094048183` using a custom addition chain.
///
/// This map computes the seventh root of `x` if `x` is a member of the field `Goldilocks`.
/// This follows from the computation: `7 * 10540996611094048183 = 4*(2^64 - 2**32) + 1 = 1 mod (p - 1)`.
#[must_use]
pub fn exp_10540996611094048183<R: PrimeCharacteristicRing>(val: R) -> R {
    // Note the binary expansion: 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.dup() * p1;
    let p100 = p10.square();
    let p111 = p100.dup() * p11.dup();
    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.dup();
    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
}