Halo中的快速傅里叶（逆）变换算法(I)FFT

1. FFT背景知识

FFT背景知识可参看博客十分简明易懂的FFT（快速傅里叶变换）。

2. Halo中的FFT代码实现

在4核8G ubuntu16.04服务器上运行：

cargo test test_fft -- --nocapture

test_fft函数中实现的是对两个999阶（1000个系数）多项式的乘法运算，在该函数内，分别进行了直接乘法运算naive_product和通过FFT实现的乘法运算multiply_polynomials。

2.1 a和b系数列表均扩展为 2 e x p 2^{exp} 2exp

multiply_polynomials函数中会首先将两个多项式相乘后的系数总数扩展为 2 e x p 2^{exp} 2exp，将a和b系数列表补零扩展为 2 e x p 2^{exp} 2exp：

 	let degree_of_result = (a.len() - 1) + (b.len() - 1); //1998
    let coeffs_of_result = degree_of_result + 1; //1999

    // Compute the size of our evaluation domain
    let mut m = 1; //2048
    let mut exp = 0; //11
    while m < coeffs_of_result {
        m *= 2;
        exp += 1;

        // The pairing-friendly curve may not be able to support
        // large enough (radix2) evaluation domains.
        if exp >= F::S {
            panic!("polynomial too large");
        }
    }
	//将`a`和`b`系数列表补零扩展为$2^{exp}$
	// Extend the vectors with zeroes
    a.resize(m, F::zero());
    b.resize(m, F::zero());

2.2 获取 2 e x p 2^{exp} 2exp-th primitive root of unity

F::ALPHA为 2 32 2^{32} 232-th primitive root of unity，基于该值获取相应的 2 e x p 2^{exp} 2exp-th primitive root of unity：

// Compute alpha, the 2^exp primitive root of unity
    let mut alpha = F::ALPHA;
    for _ in exp..F::S {
        alpha = alpha.square();
    }
   //alpha为$2^{exp}$-th primitive root of unity

2.3 分别对a和b系数列表做FFT

	alpha为$2^{exp}$-th primitive root of unity，exp=11
	best_fft(&mut a, alpha, exp); 
    best_fft(&mut b, alpha, exp);

注意best_fft(&mut a, alpha, exp);返回的数组 a a a中（对多项式 A ( x ) = a 0 + a 1 x + a 2 x 2 + . . . + a n x n A(x)=a_0+a_1x+a_2x^2+...+a_nx^n A(x)=a0​+a1​x+a2​x2+...+an​xn）依次 x x x取 w n 0 , w n 1 , w n 2 , . . . , w n ( n − 1 ) w_n^0,w_n^1,w_n^2,...,w_n^{(n-1)} wn0​,wn1​,wn2​,...,wn(n−1)​的值 a = [ A ( w n 0 ) , A ( w n 1 ) , A ( w n 2 ) , . . . , A ( w n ( n − 1 ) ) ] a=[A(w_n^0), A(w_n^1),A(w_n^2),...,A(w_n^{(n-1)})] a=[A(wn0​),A(wn1​),A(wn2​),...,A(wn(n−1)​)]。 也就是说，通过best_fft函数，可将系数表示的多项式转换为点值表示： ( w n 0 , A ( w n 0 ) ) , . . . . , ( w n ( n − 1 ) , A ( w n ( n − 1 ) ) ) (w_n^0,A(w_n^0)),....,(w_n^{(n-1)},A(w_n^{(n-1)})) (wn0​,A(wn0​)),....,(wn(n−1)​,A(wn(n−1)​))。

best_fft中会针对exp与cpu核数的关系来决定调用串行方式serial_fft还是并行方式parallel_fft。

fn best_fft(a: &mut [F], omega: F, log_n: u32) {
    let cpus = num_cpus::get(); //4
    let log_cpus = log2_floor(cpus); //2

    if log_n 2
        parallel_fft(a, omega, log_n, log_cpus);
    }
}

2.3.1 并行FFT算法parallel_fft

// omega为$2^{exp}$-th primitive root of unity，exp=11, log_n=11, log_cpus=2
fn parallel_fft(a: &mut [F], omega: F, log_n: u32, log_cpus: u32) {
    assert!(log_n >= log_cpus);

    let num_cpus = 1