snarkvm_fields/traits/
fft_parameters.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use snarkvm_utilities::biginteger::BigInteger;
17
18/// A trait that defines parameters for a field that can be used for FFTs.
19pub trait FftParameters: 'static + Send + Sync + Sized {
20    type BigInteger: BigInteger;
21
22    /// Let `N` be the size of the multiplicative group defined by the field.
23    /// Then `TWO_ADICITY` is the two-adicity of `N`, i.e. the integer `s`
24    /// such that `N = 2^s * t` for some odd integer `t`.
25    /// 2^s * t = MODULUS - 1 with t odd. This is the two-adicity of the prime.
26    const TWO_ADICITY: u32;
27
28    /// 2^s root of unity, defined as `GENERATOR^t`.
29    const TWO_ADIC_ROOT_OF_UNITY: Self::BigInteger;
30
31    /// An integer `b` such that there exists a multiplicative subgroup
32    /// of size `b^k` for some integer `k`.
33    const SMALL_SUBGROUP_BASE: Option<u32> = None;
34
35    /// The integer `k` such that there exists a multiplicative subgroup
36    /// of size `Self::SMALL_SUBGROUP_BASE^k`.
37    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
38
39    /// GENERATOR^((MODULUS-1) / (2^s *
40    /// SMALL_SUBGROUP_BASE^SMALL_SUBGROUP_BASE_ADICITY)) Used for mixed-radix FFT.
41    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self::BigInteger> = None;
42
43    /// `TWO_ADIC_ROOT_OF_UNITY^2^i` for `i := 0..TWO_ADICITY-1`
44    const POWERS_OF_ROOTS_OF_UNITY: &'static [Self::BigInteger];
45}
snarkvm_fields/traits/fft_parameters.rs

snarkvm_fields/traits/
fft_parameters.rs
