Skip to content

NTT/INTT operations seemingly giving wrong values #57

Description

@CardboardTurkey

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?

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions