Function rug_fft::bit_rev_radix_2_ntt

pub fn bit_rev_radix_2_ntt(xs: &mut [Integer], p: &Integer, w: &Integer)

Computes, for i in 0..n, sum_{j=0}^{n-1} w^{ij}*x_j, modulo p.

Requires n to be a power of two, and w to be an nth root of unity.

Example

use rug::Integer;
use rug_fft::bit_rev_radix_2_ntt;

let mut xs = vec![1, 4]
    .into_iter()
    .map(Integer::from)
    .collect::<Vec<_>>();
let p = Integer::from(7);
let w = Integer::from(6);
bit_rev_radix_2_ntt(&mut xs, &p, &w);
let ys_ex = vec![5, 4]
    .into_iter()
    .map(Integer::from)
    .collect::<Vec<_>>();
assert_eq!(xs, ys_ex);

Algorithm

Starts by doing a bit-reversal permutation on the input. Then applies blocks of successively wider butterfly transformations.

Based on this pseudocode.