ark_ff/fields/
fft_friendly.rs

1/// The interface for fields that are able to be used in FFTs.
2pub trait FftField: crate::Field {
3    /// The generator of the multiplicative group of the field
4    const GENERATOR: Self;
5
6    /// Let `N` be the size of the multiplicative group defined by the field.
7    /// Then `TWO_ADICITY` is the two-adicity of `N`, i.e. the integer `s`
8    /// such that `N = 2^s * t` for some odd integer `t`.
9    const TWO_ADICITY: u32;
10
11    /// 2^s root of unity computed by GENERATOR^t
12    const TWO_ADIC_ROOT_OF_UNITY: Self;
13
14    /// An integer `b` such that there exists a multiplicative subgroup
15    /// of size `b^k` for some integer `k`.
16    const SMALL_SUBGROUP_BASE: Option<u32> = None;
17
18    /// The integer `k` such that there exists a multiplicative subgroup
19    /// of size `Self::SMALL_SUBGROUP_BASE^k`.
20    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
21
22    /// GENERATOR^((MODULUS-1) / (2^s *
23    /// SMALL_SUBGROUP_BASE^SMALL_SUBGROUP_BASE_ADICITY)) Used for mixed-radix
24    /// FFT.
25    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = None;
26
27    /// Returns the root of unity of order n, if one exists.
28    /// If no small multiplicative subgroup is defined, this is the 2-adic root
29    /// of unity of order n (for n a power of 2).
30    /// If a small multiplicative subgroup is defined, this is the root of unity
31    /// of order n for the larger subgroup generated by
32    /// `FftConfig::LARGE_SUBGROUP_ROOT_OF_UNITY`
33    /// (for n = 2^i * FftConfig::SMALL_SUBGROUP_BASE^j for some i, j).
34    fn get_root_of_unity(n: u64) -> Option<Self> {
35        let mut omega: Self;
36        if let Some(large_subgroup_root_of_unity) = Self::LARGE_SUBGROUP_ROOT_OF_UNITY {
37            let q = Self::SMALL_SUBGROUP_BASE.expect(
38                "LARGE_SUBGROUP_ROOT_OF_UNITY should only be set in conjunction with SMALL_SUBGROUP_BASE",
39            ) as u64;
40            let small_subgroup_base_adicity = Self::SMALL_SUBGROUP_BASE_ADICITY.expect(
41                "LARGE_SUBGROUP_ROOT_OF_UNITY should only be set in conjunction with SMALL_SUBGROUP_BASE_ADICITY",
42            );
43
44            let q_adicity = crate::utils::k_adicity(q, n);
45            let q_part = q.checked_pow(q_adicity)?;
46
47            let two_adicity = crate::utils::k_adicity(2, n);
48            let two_part = 2u64.checked_pow(two_adicity)?;
49
50            if n != two_part * q_part
51                || (two_adicity > Self::TWO_ADICITY)
52                || (q_adicity > small_subgroup_base_adicity)
53            {
54                return None;
55            }
56
57            omega = large_subgroup_root_of_unity;
58            for _ in q_adicity..small_subgroup_base_adicity {
59                omega = omega.pow([q as u64]);
60            }
61
62            for _ in two_adicity..Self::TWO_ADICITY {
63                omega.square_in_place();
64            }
65        } else {
66            // Compute the next power of 2.
67            let size = n.next_power_of_two() as u64;
68            let log_size_of_group = ark_std::log2(usize::try_from(size).expect("too large"));
69
70            if n != size || log_size_of_group > Self::TWO_ADICITY {
71                return None;
72            }
73
74            // Compute the generator for the multiplicative subgroup.
75            // It should be 2^(log_size_of_group) root of unity.
76            omega = Self::TWO_ADIC_ROOT_OF_UNITY;
77            for _ in log_size_of_group..Self::TWO_ADICITY {
78                omega.square_in_place();
79            }
80        }
81        Some(omega)
82    }
83}
ark_ff/fields/fft_friendly.rs

ark_ff/fields/
fft_friendly.rs
