mina_curves/pasta/fields/
fft.rs

1use ark_ff::biginteger::BigInteger;
2
3/// A trait that defines parameters for a field that can be used for FFTs.
4pub trait FftParameters: 'static + Send + Sync + Sized {
5    type BigInt: BigInteger;
6
7    /// Let `N` be the size of the multiplicative group defined by the field.
8    /// Then `TWO_ADICITY` is the two-adicity of `N`, i.e. the integer `s`
9    /// such that `N = 2^s * t` for some odd integer `t`.
10    const TWO_ADICITY: u32;
11
12    /// 2^s root of unity computed by GENERATOR^t
13    const TWO_ADIC_ROOT_OF_UNITY: Self::BigInt;
14
15    /// An integer `b` such that there exists a multiplicative subgroup
16    /// of size `b^k` for some integer `k`.
17    const SMALL_SUBGROUP_BASE: Option<u32> = None;
18
19    /// The integer `k` such that there exists a multiplicative subgroup
20    /// of size `Self::SMALL_SUBGROUP_BASE^k`.
21    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
22
23    /// GENERATOR^((MODULUS-1) / (2^s *
24    /// SMALL_SUBGROUP_BASE^SMALL_SUBGROUP_BASE_ADICITY)) Used for mixed-radix FFT.
25    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self::BigInt> = None;
26}
27
28/// A trait that defines parameters for a prime field.
29pub trait FpParameters: FftParameters {
30    /// The modulus of the field.
31    const MODULUS: Self::BigInt;
32
33    /// The number of bits needed to represent the `Self::MODULUS`.
34    const MODULUS_BITS: u32;
35
36    /// The number of bits that must be shaved from the beginning of
37    /// the representation when randomly sampling.
38    const REPR_SHAVE_BITS: u32;
39
40    /// Let `M` be the power of 2^64 nearest to `Self::MODULUS_BITS`. Then
41    /// `R = M % Self::MODULUS`.
42    const R: Self::BigInt;
43
44    /// R2 = R^2 % Self::MODULUS
45    const R2: Self::BigInt;
46
47    /// INV = -MODULUS^{-1} mod 2^64
48    const INV: u64;
49
50    /// A multiplicative generator of the field.
51    /// `Self::GENERATOR` is an element having multiplicative order
52    /// `Self::MODULUS - 1`.
53    const GENERATOR: Self::BigInt;
54
55    /// The number of bits that can be reliably stored.
56    /// (Should equal `SELF::MODULUS_BITS - 1`)
57    const CAPACITY: u32;
58
59    /// t for 2^s * t = MODULUS - 1, and t coprime to 2.
60    const T: Self::BigInt;
61
62    /// (t - 1) / 2
63    const T_MINUS_ONE_DIV_TWO: Self::BigInt;
64
65    /// (Self::MODULUS - 1) / 2
66    const MODULUS_MINUS_ONE_DIV_TWO: Self::BigInt;
67}
68
69pub trait Fp256Parameters {}
mina_curves/pasta/fields/fft.rs

mina_curves/pasta/fields/
fft.rs
