# Question about the Cooley-Tukey operation in NTT

**URL:** <https://openfhe.discourse.group/t/question-about-the-cooley-tukey-operation-in-ntt/1842>\
**Category:** Library Questions\
**Created:** [January 27, 2025, 5:29am UTC](https://openfhe.discourse.group/t/question-about-the-cooley-tukey-operation-in-ntt/1842 "2025-01-27T05:29:36Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Yusaku\_suzuki](https://avatars.discourse-cdn.com/v4/letter/y/f19dbf/32.png) [@Yusaku\_suzuki](https://openfhe.discourse.group/u/Yusaku_suzuki)\
**Post date:** [January 27, 2025, 5:29am UTC](https://openfhe.discourse.group/t/question-about-the-cooley-tukey-operation-in-ntt/1842/1 "2025-01-27T05:29:36Z")

</div>

I have a question about the `ForwardTransformToBitReverseInPlace` method in the `NumberTheoreticTransformNat` class.  
Source name is `transformnat-impl.h`.  
Function Name is below.  
`template <typename VecType> void NumberTheoreticTransformNat<VecType>::ForwardTransformToBitReverseInPlace(const VecType& rootOfUnityTable, const VecType& preconRootOfUnityTable, VecType* element);`

Does the Cooley-Tukey (CT) butterfly operation follow the structure shown in the diagram “Figure 1”?

The legend is “Figure 2”.

This structure differs from the general Cooley-Tukey butterfly operation shown “Figure 3”

Could you explain the reason for this difference?

 ![Figure](https://canada1.discourse-cdn.com/flex031/uploads/openfhe/original/1X/a5b0097007b88a34d9e32407e3860f40cb81de23.jpeg)

---

<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:** [January 27, 2025, 3:29pm UTC](https://openfhe.discourse.group/t/question-about-the-cooley-tukey-operation-in-ntt/1842/2 "2025-01-27T15:29:36Z")

</div>

Figure (1) is not complete. First, we do not skip points as we move from one stage to the next. Also, the twiddle factors for each stage are not shown.

Anyway, forward NTT in OpenFHE employs the standard Cooley-Tukey dataflow with a slight modification of the twiddles order.  
The NTT implementation in OpenFHE follows the NTT algorithms in this [work](https://eprint.iacr.org/2016/504.pdf).

At a high level, for NTT, in stage 0 \leq s \lt \log\_{2}{N}, you divide the points into 2^{s+1} groups of points. The butterfly operation is then applied to these groups in an interleaved manner, processing pairs of groups sequentially. My description might not be very clear, but it should be straightforward to figure out the pattern if you trace `ForwardTransformToBitReverseInPlace`.

---

<div class="post-metadata">

**Author:** ![Yusaku\_suzuki](https://avatars.discourse-cdn.com/v4/letter/y/f19dbf/32.png) [@Yusaku\_suzuki](https://openfhe.discourse.group/u/Yusaku_suzuki)\
**Post date:** [January 28, 2025, 1:48am UTC](https://openfhe.discourse.group/t/question-about-the-cooley-tukey-operation-in-ntt/1842/3 "2025-01-28T01:48:47Z")

</div>

Thank you for response.

I have traced the code.  
I included the traced code (Figure 4) and its output (Figure 5) in the attached images.

The trace code is a butterfly operation part.  
The indices of the elements used in the operation (`loIdx`, `hiIdx`) and the indices of omega (`omegaIdx`) were output according to the base code.

I would like to confirm the case of `Step m=2, t=2, logt=1` specifically `Step i=1`.  
In this case, the butterfly operation is applied to ‘elements 2–5’.  
However, I understand that in the standard Cooley-Tukey FFT, this operation would involve `elements 4–7`.  
Additionally, in `Step m=2, t=2, logt=1` no operation is performed for `elements 6 and 7`.

Could you give me your opinion on the above?

 ![Figure2](https://canada1.discourse-cdn.com/flex031/uploads/openfhe/original/1X/2fd4bdcce9e302f0cfbff0d140f56b6d39c963bd.png)

---

<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:** [January 28, 2025, 5:13pm UTC](https://openfhe.discourse.group/t/question-about-the-cooley-tukey-operation-in-ntt/1842/4 "2025-01-28T17:13:53Z")

</div>

This does not seem correct to me. You might have implemented it incorrectly. Instead of pulling the code out of OpenFHE and re-implementing it, why don’t you trace it inside OpenFHE itself? This way, you can rule out the possibility of incorrect implementation. Your code differs significantly from OpenFHE’s implementation.

The code you provided must have an issue since all elements must be touched in every stage in NTT.

---

<div class="post-metadata">

**Author:** ![Yusaku\_suzuki](https://avatars.discourse-cdn.com/v4/letter/y/f19dbf/32.png) [@Yusaku\_suzuki](https://openfhe.discourse.group/u/Yusaku_suzuki)\
**Post date:** [January 29, 2025, 2:30am UTC](https://openfhe.discourse.group/t/question-about-the-cooley-tukey-operation-in-ntt/1842/5 "2025-01-29T02:30:12Z")

</div>

Thank you for your response.

Upon rechecking in OpenFHE, I identified the cause of my misunderstanding. I had incorrectly interpreted the behavior of `GetMSB`.  
For example, I assumed `GetMSB(4)` would be equivalent to `log2(4) = 2`, counting from 0. However, it actually counts from 1, making `GetMSB(4) = 3`.

As a result, the Cooley-Tukey FFT was being executed correctly.

I will close this Q&A. Thank you very much for your support.