2

I'm researching on different variants of Number Theoretic Transform (NTT) and some concepts just got me confused.

  1. What's the difference between Cooley-Tukey transform and Gentleman-Sande transform? My understanding is that both CT and GS transform are just a way to calculate NTT/INTT, so they may use different strategy to apply divide and conquer, their outputs however, should be the same. I see lots of implementation use both of them: they use CT for NTT and GS for INTT. So it's a bit confusing.

  2. When you do NTT/INTT on module ring like $\mathbb{Z}_q[X]/(X^N\pm1)$, you can also apply some technique like cyclic convolution (for mod $X^N-1$) or negative wrapped convolution (NWC-NTT, for mod $X^N+1$). What's the difference of them and why they apply to different quotient ring? What's the relationship between these two techniques with CT & GS butterflies?

Daisy Ding
  • 53

1 Answers1

0

To the first question:

The GS butterfly can be seen as a reversing of the CT butterfly, this can be a side answer to this question(why use CT in NTT, and GS in INTT?).

The CT butterfly can be represented as $$ a' = a + b \zeta $$ $$ b' = a - b \zeta $$

therefore, in the INTT phase, the GS butterfly can be used to get $$ a = (a'+b') * 2^{-1} $$ $$ b = (a'-b') * \zeta^{-1} * 2^{-1} $$

take the $* 2^{-1}$ away, it is the original GS butterfly.

To the second question:

The cyclic convolution is also named as "positive wrapped convolution (PWC)", The $\mod X^n+1(-1)$ means $X^n = -1(1)$, which is origin of the "negtive (positive)". An example:

$$ 2x^2 * 3x^4 = 6x^6 = -6x \mod x^5 + 1 $$

The NWC and PWC donot have relationship with CT & GS.

Julian
  • 1