quarkslab / NFLlib

NTT-based Fast Lattice library
MIT License
165 stars 52 forks source link

NTT/INTT operations seemingly giving wrong values #57

Open CardboardTurkey opened 11 months ago

CardboardTurkey commented 11 months ago

I am attempting to perform an NTT operation like so: output=INNT(NTT(input_1)*NTT(input_2)).

I have tried with the following code:

#include <memory>
#include <nfl/poly.hpp>

static constexpr size_t qNum = 1;
static constexpr size_t N = 32;

nfl::poly<uint64_t, N, qNum> nfl_1, nfl_2, nfl_3;

int main(int argc, char *argv[]) {

  uint64_t input_1[] = {0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0,
                        0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1};
  uint64_t input_2[] = {0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0,
                        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

  memcpy(nfl_1.begin(), input_1, sizeof(uint64_t) * N);
  memcpy(nfl_2.begin(), input_2, sizeof(uint64_t) * N);

  nfl_1.ntt_pow_phi();
  nfl_2.ntt_pow_phi();
  nfl::mul(nfl_3, nfl_1, nfl_2);
  nfl_3.invntt_pow_invphi();

  return 0;
}

From other NTT implementations that I've used (e.g. sympy or rug-fft) I would expect the output to be

{2, 3, 1, 2, 2, 3, 3, 4, 2, 5, 3, 3, 3, 5, 2, 3, 3, 1, 3, 3, 1, 2, 2, 3, 3, 2, 3, 2, 3, 2, 2}

however instead I find the data in nfl_3 to be

{4611686018326724607, 4611686018326724606, 4611686018326724608, 0, 0, 4611686018326724608, 3, 2, 2, 3, 3, 3, 3, 5, 2, 3, 3, 3, 1, 3, 3, 1, 2, 2, 3, 3, 2, 3, 2, 3, 2, 2}

Am I do something wrong here? The data actually agrees in the second half but not the first. I find the big numbers particularly confusing. Why are they there?