1  // Copyright (c) 2025-2026 ACDC Network
 2  // This file is part of the alphavm library.
 3  //
 4  // Alpha Chain | Delta Chain Protocol
 5  // International Monetary Graphite.
 6  //
 7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
 8  // They built world-class ZK infrastructure. We installed the EASY button.
 9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
11  //
12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
14  // No rights reserved. No permission required. No warranty. No refunds.
15  //
16  // https://creativecommons.org/publicdomain/zero/1.0/
17  // SPDX-License-Identifier: CC0-1.0
18  
19  use alphavm_utilities::biginteger::BigInteger;
20  
21  /// A trait that defines parameters for a field that can be used for FFTs.
22  pub trait FftParameters: 'static + Send + Sync + Sized {
23      type BigInteger: BigInteger;
24  
25      /// Let `N` be the size of the multiplicative group defined by the field.
26      /// Then `TWO_ADICITY` is the two-adicity of `N`, i.e. the integer `s`
27      /// such that `N = 2^s * t` for some odd integer `t`.
28      /// 2^s * t = MODULUS - 1 with t odd. This is the two-adicity of the prime.
29      const TWO_ADICITY: u32;
30  
31      /// 2^s root of unity, defined as `GENERATOR^t`.
32      const TWO_ADIC_ROOT_OF_UNITY: Self::BigInteger;
33  
34      /// An integer `b` such that there exists a multiplicative subgroup
35      /// of size `b^k` for some integer `k`.
36      const SMALL_SUBGROUP_BASE: Option<u32> = None;
37  
38      /// The integer `k` such that there exists a multiplicative subgroup
39      /// of size `Self::SMALL_SUBGROUP_BASE^k`.
40      const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
41  
42      /// GENERATOR^((MODULUS-1) / (2^s *
43      /// SMALL_SUBGROUP_BASE^SMALL_SUBGROUP_BASE_ADICITY)) Used for mixed-radix FFT.
44      const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self::BigInteger> = None;
45  
46      /// `TWO_ADIC_ROOT_OF_UNITY^2^i` for `i := 0..TWO_ADICITY-1`
47      const POWERS_OF_ROOTS_OF_UNITY: &'static [Self::BigInteger];
48  }