majin_blob_core/
math.rs

1use lazy_static::lazy_static;
2use num_bigint::{BigUint, ToBigUint};
3
4lazy_static! {
5    pub static ref TWO: BigUint = 2u32.to_biguint().unwrap();
6}
7
8/// Performs the inverse Fast Fourier Transform on a vector of `BigUint`.
9///
10/// # Arguments
11///
12/// * `arr` - A vector of `BigUint` representing the input array.
13/// * `xs` - A vector of `BigUint` representing the evaluation points.
14/// * `p` - The modulus as a `BigUint`.
15///
16/// # Returns
17///
18/// A vector of `BigUint` representing the transformed array.
19pub fn ifft(arr: Vec<BigUint>, xs: Vec<BigUint>, p: &BigUint) -> Vec<BigUint> {
20    // Base case: return immediately if the array length is 1
21    if arr.len() == 1 {
22        return arr;
23    }
24
25    let n = arr.len() / 2;
26    let mut res0 = Vec::with_capacity(n);
27    let mut res1 = Vec::with_capacity(n);
28    let mut new_xs = Vec::with_capacity(n);
29
30    for i in (0..2 * n).step_by(2) {
31        let a = &arr[i];
32        let b = &arr[i + 1];
33        let x = &xs[i];
34
35        res0.push(div_mod(a + b, TWO.clone(), p));
36        // Handle subtraction to avoid underflow
37        let diff = if b > a { p - (b - a) } else { a - b };
38        res1.push(div_mod(diff, TWO.clone() * x, p));
39
40        new_xs.push(x.modpow(&TWO.clone(), p));
41    }
42
43    // Recursive calls
44    let merged_res0 = ifft(res0, new_xs.clone(), p);
45    let merged_res1 = ifft(res1, new_xs, p);
46
47    // Merging the results
48    let mut merged = Vec::with_capacity(arr.len());
49    for i in 0..n {
50        merged.push(merged_res0[i].clone());
51        merged.push(merged_res1[i].clone());
52    }
53    merged
54}
55
56/// Divides two `BigUint` numbers modulo a third `BigUint` number.
57///
58/// # Arguments
59///
60/// * `a` - The numerator as a `BigUint`.
61/// * `b` - The denominator as a `BigUint`.
62/// * `p` - The modulus as a `BigUint`.
63///
64/// # Returns
65///
66/// The result of the division modulo `p` as a `BigUint`.
67pub fn div_mod(a: BigUint, b: BigUint, p: &BigUint) -> BigUint {
68    a * b.modpow(&(p - TWO.clone()), p) % p
69}
majin_blob_core/math.rs

majin_blob_core/
math.rs
