ntt function

List<int> ntt(List<int> poly)

Implementation

List<int> ntt(List<int> poly) {
  List<int> r = List<int>.from(poly);
  int length = n;

  int k = 0;
  for (int step = 128; step >= 2; step >>= 1) {
    for (int i = 0; i < length; i += 2 * step) {
      for (int j = i; j < i + step; j++) {
        int t = modMul(r[j + step], zetas[k], q);
        r[j + step] = modSub(r[j], t, q);
        r[j] = modAdd(r[j], t, q);
        k++;
      }
    }
  }
  return r;
}