p3_monty_31/
data_traits.rs

1use core::fmt::Debug;
2use core::hash::Hash;
3
4use p3_field::{Field, FieldAlgebra};
5
6use crate::MontyField31;
7
8/// MontyParameters contains the prime P along with constants needed to convert elements into and out of MONTY form.
9/// The MONTY constant is assumed to be a power of 2.
10pub trait MontyParameters:
11    Copy + Clone + Default + Debug + Eq + PartialEq + Sync + Send + Hash + 'static
12{
13    // A 31-bit prime.
14    const PRIME: u32;
15
16    // The log_2 of our MONTY constant.
17    const MONTY_BITS: u32;
18
19    // We define MONTY_MU = PRIME^-1 (mod 2^MONTY_BITS). This is different from the usual convention
20    // (MONTY_MU = -PRIME^-1 (mod 2^MONTY_BITS)) but it avoids a carry.
21    const MONTY_MU: u32;
22
23    const MONTY_MASK: u32 = ((1u64 << Self::MONTY_BITS) - 1) as u32;
24}
25
26/// PackedMontyParameters contains constants needed for MONTY operations for packings of Monty31 fields.
27#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
28pub trait PackedMontyParameters: crate::MontyParametersNeon + MontyParameters {}
29#[cfg(all(
30    target_arch = "x86_64",
31    target_feature = "avx2",
32    not(all(feature = "nightly-features", target_feature = "avx512f"))
33))]
34/// PackedMontyParameters contains constants needed for MONTY operations for packings of Monty31 fields.
35pub trait PackedMontyParameters: crate::MontyParametersAVX2 + MontyParameters {}
36#[cfg(all(
37    feature = "nightly-features",
38    target_arch = "x86_64",
39    target_feature = "avx512f"
40))]
41/// PackedMontyParameters contains constants needed for MONTY operations for packings of Monty31 fields.
42pub trait PackedMontyParameters: crate::MontyParametersAVX512 + MontyParameters {}
43#[cfg(not(any(
44    all(target_arch = "aarch64", target_feature = "neon"),
45    all(
46        target_arch = "x86_64",
47        target_feature = "avx2",
48        not(all(feature = "nightly-features", target_feature = "avx512f"))
49    ),
50    all(
51        feature = "nightly-features",
52        target_arch = "x86_64",
53        target_feature = "avx512f"
54    ),
55)))]
56/// PackedMontyParameters contains constants needed for MONTY operations for packings of Monty31 fields.
57pub trait PackedMontyParameters: MontyParameters {}
58
59/// BarrettParameters contains constants needed for the Barrett reduction used in the MDS code.
60pub trait BarrettParameters: MontyParameters {
61    const N: usize = 40; // beta = 2^N, fixing N = 40 here
62    const PRIME_I128: i128 = Self::PRIME as i128;
63    const PSEUDO_INV: i64 = (((1_i128) << (2 * Self::N)) / Self::PRIME_I128) as i64; // I = 2^80 / P => I < 2**50
64    const MASK: i64 = !((1 << 10) - 1); // Lets us 0 out the bottom 10 digits of an i64.
65}
66
67/// FieldParameters contains constants and methods needed to imply FieldAlgebra, Field and PrimeField32 for MontyField31.
68pub trait FieldParameters: PackedMontyParameters + Sized {
69    // Simple field constants.
70    const MONTY_ZERO: MontyField31<Self> = MontyField31::new(0);
71    const MONTY_ONE: MontyField31<Self> = MontyField31::new(1);
72    const MONTY_TWO: MontyField31<Self> = MontyField31::new(2);
73    const MONTY_NEG_ONE: MontyField31<Self> = MontyField31::new(Self::PRIME - 1);
74
75    // A generator of the fields multiplicative group. Needs to be given in Monty Form.
76    const MONTY_GEN: MontyField31<Self>;
77
78    const HALF_P_PLUS_1: u32 = (Self::PRIME + 1) >> 1;
79
80    fn exp_u64_generic<FA: FieldAlgebra>(val: FA, power: u64) -> FA;
81    fn try_inverse<F: Field>(p1: F) -> Option<F>;
82}
83
84/// TwoAdicData contains constants needed to imply TwoAdicField for Monty31 fields.
85pub trait TwoAdicData: MontyParameters {
86    /// Largest n such that 2^n divides p - 1.
87    const TWO_ADICITY: usize;
88
89    /// The odd constant r such that p = r * 2^n + 1
90    const ODD_FACTOR: i32 = (Self::PRIME >> Self::TWO_ADICITY) as i32;
91
92    /// ArrayLike should usually be `&'static [MontyField31]`.
93    type ArrayLike: AsRef<[MontyField31<Self>]> + Sized;
94
95    /// A list of generators of 2-adic subgroups.
96    /// The i'th element must be a 2^i root of unity and the i'th element squared must be the i-1'th element.
97    const TWO_ADIC_GENERATORS: Self::ArrayLike;
98
99    /// Precomputation of the first 3 8th-roots of unity.
100    ///
101    /// Must agree with the 8th-root in TWO_ADIC_GENERATORS, i.e.
102    /// ROOTS_8[1] == TWO_ADIC_GENERATORS[3]
103    const ROOTS_8: Self::ArrayLike;
104
105    /// Precomputation of the inverses of ROOTS_8.
106    const INV_ROOTS_8: Self::ArrayLike;
107
108    /// Precomputation of the first 7 16th-roots of unity.
109    ///
110    /// Must agree with the 16th-root in TWO_ADIC_GENERATORS, i.e.
111    /// ROOTS_16[1] == TWO_ADIC_GENERATORS[4]
112    const ROOTS_16: Self::ArrayLike;
113
114    /// Precomputation of the inverses of ROOTS_16.
115    const INV_ROOTS_16: Self::ArrayLike;
116}
117
118/// TODO: This should be deleted long term once we have improved our API for defining extension fields.
119/// This allows us to implement Binomial Extensions over Monty31 fields.
120pub trait BinomialExtensionData<const DEG: usize>: MontyParameters + Sized {
121    /// W is a value such that (x^DEG - WN) is irreducible.
122    const W: MontyField31<Self>;
123
124    /// DTH_ROOT = W^((p - 1)/DEG)
125    const DTH_ROOT: MontyField31<Self>;
126
127    /// A generator of the extension fields multiplicative group.
128    const EXT_GENERATOR: [MontyField31<Self>; DEG];
129
130    const EXT_TWO_ADICITY: usize;
131
132    /// ArrayLike should usually be [MontyField31; EXT_TWO_ADICITY - TWO_ADICITY].
133    type ArrayLike: AsRef<[[MontyField31<Self>; DEG]]> + Sized;
134
135    /// A list of generators of 2-adic subgroups not contained in the base field.
136    const TWO_ADIC_EXTENSION_GENERATORS: Self::ArrayLike;
137}
p3_monty_31/data_traits.rs

p3_monty_31/
data_traits.rs
