Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

NTT/INTT operations seemingly giving wrong values #57

Open
CardboardTurkey opened this issue Oct 19, 2023 · 0 comments
Open

NTT/INTT operations seemingly giving wrong values #57

CardboardTurkey opened this issue Oct 19, 2023 · 0 comments

Comments

@CardboardTurkey
Copy link

CardboardTurkey commented Oct 19, 2023

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant