ffSamplingFft function

List<List<Complex>> ffSamplingFft(List<List<Complex>> t, FfTree tree, double sigmin, RandomBytes randombytes,)

Fast Fourier sampling of the target t = t0, t1 using the ffLDL tree as auxiliary information. Returns z = z0, z1 in FFT representation, where (z0, z1) is a lattice point close to (t0, t1) sampled with the right discrete-Gaussian distribution. Corresponds to algorithm 11 (ffSampling).

Implementation

List<List<Complex>> ffSamplingFft(
  List<List<Complex>> t,
  FfTree tree,
  double sigmin,
  RandomBytes randombytes,
) {
  final n = t[0].length;
  if (n > 1) {
    final branch = tree as FfBranch;
    final z1 = FalconFFT.mergeFft(
      ffSamplingFft(
        FalconFFT.splitFft(t[1]),
        branch.right,
        sigmin,
        randombytes,
      ),
    );
    final t0b = FalconFFT.addFft(
      t[0],
      FalconFFT.mulFft(FalconFFT.subFft(t[1], z1), branch.l10),
    );
    final z0 = FalconFFT.mergeFft(
      ffSamplingFft(FalconFFT.splitFft(t0b), branch.left, sigmin, randombytes),
    );
    return [z0, z1];
  }
  // Leaf: sample each coordinate from a discrete Gaussian centered on t[i].
  final leaf = tree as FfLeaf;
  final z0 = GaussianSampler.samplerZ(
    t[0][0].real,
    leaf.value,
    sigmin,
    randombytes,
  );
  final z1 = GaussianSampler.samplerZ(
    t[1][0].real,
    leaf.value,
    sigmin,
    randombytes,
  );
  return [
    [Complex(z0.toDouble(), 0)],
    [Complex(z1.toDouble(), 0)],
  ];
}