Skip to content

NTT/INTT operations seemingly giving wrong values #57

@CardboardTurkey

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?

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