# How to transform something to NTT space

**URL:** <https://openfhe.discourse.group/t/how-to-transform-something-to-ntt-space/842>\
**Category:** Library Questions\
**Created:** [October 12, 2023, 7:52pm UTC](https://openfhe.discourse.group/t/how-to-transform-something-to-ntt-space/842 "2023-10-12T19:52:40Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![mmazz](https://avatars.discourse-cdn.com/v4/letter/m/50afbb/32.png) [@mmazz](https://openfhe.discourse.group/u/mmazz)\
**Post date:** [October 12, 2023, 7:52pm UTC](https://openfhe.discourse.group/t/how-to-transform-something-to-ntt-space/842/1 "2023-10-12T19:52:40Z")

</div>

Hello!

Sorry if this is not the place to ask something like this or if a to simple question.

I’m trying to test for my Ph.D. a little bit the NTT of OpenFHE, and I’m a little bit lost…  
How can I transform an input, say an std::vector\<uint64\_t\> to a NTT space?

I suppose that first I need to create the NTT tables, how I do that?

---

<div class="post-metadata">

**Author:** ![Caesar](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/caesar/32/63_2.png) [@Caesar](https://openfhe.discourse.group/u/Caesar)\
**Post date:** [October 13, 2023, 9:51pm UTC](https://openfhe.discourse.group/t/how-to-transform-something-to-ntt-space/842/2 "2023-10-13T21:51:40Z")

</div>

You can check the code [here](https://github.com/openfheorg/openfhe-development/blob/main/benchmark/src/poly-benchmark-1k.cpp#L231), which shows how to invoke NTT for a `NativePoly`. The file also includes code to perform NTT of a `DCRTPoly` object (`DCRT_ntt`).

OpenFHE must be initialized properly (by creating a `cryptocontext`) before you are able to use NTT. The NTT tables will be created automatically as part of OpenFHE initialization.

---

<div class="post-metadata">

**Author:** ![ypolyakov](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/ypolyakov/32/47_2.png) [@ypolyakov](https://openfhe.discourse.group/u/ypolyakov)\
**Post date:** [October 13, 2023, 11:49pm UTC](https://openfhe.discourse.group/t/how-to-transform-something-to-ntt-space/842/3 "2023-10-13T23:49:06Z")

</div>

I suggest looking at the following unit test: [https://github.com/openfheorg/openfhe-development/blob/v1.1.1/src/core/unittest/UnitTestTransform.cpp#L60](https://github.com/openfheorg/openfhe-development/blob/v1.1.1/src/core/unittest/UnitTestTransform.cpp#L60)

---

<div class="post-metadata">

**Author:** ![JianmingTong](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/jianmingtong/32/380_2.png) [@JianmingTong](https://openfhe.discourse.group/u/JianmingTong)\
**Post date:** [March 6, 2025, 1:53am UTC](https://openfhe.discourse.group/t/how-to-transform-something-to-ntt-space/842/4 "2025-03-06T01:53:48Z")

</div>

Hi a naive question: how shall I set as the type V in the following code?

```auto
template <typename V>
void CRT_polynomial_mult(const std::string& msg) {
    typename V::Integer primeModulus("113"); // 65537
    usint cycloOrder = 8;
    usint n = cycloOrder / 2;

    typename V::Integer primitiveRootOfUnity = lbcrypto::RootOfUnity(cycloOrder, primeModulus);

    ChineseRemainderTransformFTT<V>().PreCompute(primitiveRootOfUnity, cycloOrder, primeModulus);

    V a(n, primeModulus);
    a.at(0) = typename V::Integer("1");
    a.at(1) = typename V::Integer("2");
    a.at(2) = typename V::Integer("4");
    a.at(3) = typename V::Integer("1");
    V b(a);

    V A(cycloOrder / 2);
    ChineseRemainderTransformFTT<V>().ForwardTransformToBitReverse(a, primitiveRootOfUnity, cycloOrder, &A);
    V B(cycloOrder / 2);
    ChineseRemainderTransformFTT<V>().ForwardTransformToBitReverse(b, primitiveRootOfUnity, cycloOrder, &B);

    V AB = A * B;

    V InverseFFTAB(cycloOrder / 2);
    ChineseRemainderTransformFTT<V>().InverseTransformFromBitReverse(AB, primitiveRootOfUnity, cycloOrder,
                                                                     &InverseFFTAB);

    V expectedResult(n, primeModulus);
    expectedResult.at(0) = typename V::Integer("94");
    expectedResult.at(1) = typename V::Integer("109");
    expectedResult.at(2) = typename V::Integer("11");
    expectedResult.at(3) = typename V::Integer("18");

    EXPECT_EQ(expectedResult, InverseFFTAB) << msg << "inverse transform";
}

```

I wanna copy this code into the src/pke/examples folder to run it and print out ciphertext at eval domain and coef domain, modulus. RootOfUnity, Modulus. Might I seek suggestions on how to do it?

I need these information to make sure my custom NTT implementation matching current OpenFHE NTT.

---

<div class="post-metadata">

**Author:** ![JianmingTong](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/jianmingtong/32/380_2.png) [@JianmingTong](https://openfhe.discourse.group/u/JianmingTong)\
**Post date:** [March 6, 2025, 2:01am UTC](https://openfhe.discourse.group/t/how-to-transform-something-to-ntt-space/842/5 "2025-03-06T02:01:21Z")

</div>

I think I figure it out, let me know if I do it wrongly

```auto
BigInteger primeModulus("113"); // 65537
     uint32_t cycloOrder = 8;
     uint32_t n = cycloOrder / 2;
     uint64_t m = n << 1;
 
     NativeInteger modulusQ(primeModulus);
     NativeInteger rootOfUnity = RootOfUnity(m, modulusQ);
 
     DiscreteUniformGeneratorImpl<NativeVector> dug;
     NativeVector x = dug.GenerateVector(n, modulusQ);
     NativeVector X(n);
 
    ChineseRemainderTransformFTT<NativeVector> crtFTT;
    crtFTT.PreCompute(rootOfUnity, m, modulusQ);
 
    std::cout << "x before INTT: " << x << std::endl;
    crtFTT.ForwardTransformToBitReverse(x, rootOfUnity, m, &X);
    std::cout << "X after INTT: " << X << std::endl;

    crtFTT.InverseTransformFromBitReverse(X, rootOfUnity, m, &x);

    std::cout << "x after NTT: " << x << std::endl;

```

Might I ask how shall I understand the value being printed out from here? Should it be the coefficients of the ciphertext?

```auto
CycloOrder: 8
rootOfUnity: 18
x after INTT: [1 2 4 1] modulus: 113
X after INTT: [46 62 104 18] modulus: 113
x after INTT: [1 2 4 1] modulus: 113

```

I get above messages, where 18 is the 2n-th root of unity instead of n-th root of unity for a degree N=4. And the naive NTT following the algorithm ([Discrete Fourier transform over a ring - Wikipedia](https://en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring#Number-theoretic_transform)) gives me the result of [8, 95, 2, 12]. Here come the Python code of implementing it. Might I seek suggestions on why am I obtaining a different result?

```auto
import math

def bit_reverse_indices(n):
    """
    Return a list of indices in bit-reversed order for an array of length n (n must be a power of 2).
    """
    bits = n.bit_length() - 1
    result = []
    for i in range(n):
        rev = 0
        x = i
        for _ in range(bits):
            rev = (rev << 1) | (x & 1)
            x >>= 1
        result.append(rev)
    return result

def bit_reverse_permutation(arr):
    """
    Reorder the array 'arr' according to the bit-reversal permutation.
    """
    n = len(arr)
    indices = bit_reverse_indices(n)
    return [arr[i] for i in indices]

def ntt_bit_reverse(x, q, omega):
    """
    Compute the forward Number Theoretic Transform (NTT) of the input vector x over GF(q)
    using the iterative Cooley–Tukey algorithm with bit-reversal reordering.
    
    The NTT is defined as:
       X[k] = sum_{j=0}^{N-1} x[j] * omega^(j*k) mod q,
    where omega is a primitive N-th root of unity in GF(q).
    
    Parameters:
      x : list of integers, length must be a power of 2.
      q : prime modulus.
      omega : a primitive N-th root of unity in GF(q), where N = len(x).
    
    Returns:
      A list of integers representing the NTT of x in natural (standard) order.
    """
    n = len(x)
    
    # Step 1: Reorder the input into bit-reversed order.
    a = bit_reverse_permutation(x[:]) # copy and reorder
    
    # Step 2: Iteratively perform butterfly updates.
    # The algorithm runs in log2(n) stages.
    m = 2
    while m <= n:
        # Compute twiddle factor for this stage:
        # In each stage, we need a factor: w_m = omega^(n/m) mod q.
        w_m = pow(omega, n // m, q)
        # Process blocks of length m.
        for k in range(0, n, m):
            w = 1
            for j in range(m // 2):
                t = (w * a[k + j + m//2]) % q
                u = a[k + j]
                a[k + j] = (u + t) % q
                a[k + j + m//2] = (u - t) % q
                w = (w * w_m) % q
        m *= 2
    return a

# Example usage:
if __name__ == ' __main__':
    # Parameters: 
    # Let q = 17, N = 8, and omega = 2.
    # 2 is a primitive 8-th root of unity modulo 17 since 2^8 = 256 ≡ 1 (mod 17) and no smaller power yields 1.
    q = 113
    N = 4
    omega = 18 ** 2 % q # 98
    # Input vector x.
    x = [1, 2, 4, 1]   
    # Compute the NTT using the bit-reverse based iterative algorithm.
    X = ntt_bit_reverse(x, q, omega)
    print("NTT of x:", X)

```

Aha I found that I’m implementing the vanilla NTT, which is not for RLWE. The problem goes away after supporting negacyclic NTT via (1) 2n-primitive root and (2) twist input before sending it to NTT and twisted it back after getting the result.