1
$\begingroup$

in reference here the FFT trick for $X^n+1$ is discussed with reference to the Number Theoretic transformation. On page 5, the Chinese Remainder Theorem is used to define the mapping.

enter image description here

So far so good. But I am particularly interested in how to arrive at the statement that on the k-th level we have the following relationship:

enter image description here

Where $i = 0,...,2^k-1$. Here $\text{brv}$ maps an $log(n)$-bit number to its bitreversal, $brv(b_{log(n)−1}2^{log(n)−1} + · · · + b_1 2 + b_0) = b_0 2^{ log(n)−1} + · · · + b_{log(n)−2}2 + b_{log(n)−1}$.

I cannot deduce from the text how to arrive at the expression in the exponent $\text{brv}(2^k+i)$. That is the reason for my question, how exactly do you arrive at the exponent here?

$\endgroup$
1
  • $\begingroup$ Please edit into question to make it self contained: here brv maps an log(n)-bit number to its bitreversal, brv(blog(n)−12 log(n)−1 + · · · + b12 + b0) = b02 log(n)−1 + · · · + blog(n)−22 + blog(n)−1. $\endgroup$
    – kodlu
    Commented Feb 22 at 14:35

1 Answer 1

2
$\begingroup$

It's first worth clarifying that your question has nothing (directly) to do with cryptography, and instead is entirely a question about how the FFT works. The map

$$f\mapsto (f\bmod X^{n/2}-\zeta^{n/2}, f\bmod X^{n/2}+\zeta^{n/2})$$

is typically called a "butterfly" (though often $\zeta$ is a root of unity in $\mathbb{C}$ rather than $\mathbb{Z}_p$. This difference doesn't really matter). Bit reversal appears when one studies the inplace Cooley-Tukey FFT in particular. So to understand this you can look for any explanation of the (inplace) Cooley-Tukey FFT. See for example this random website I found, though if you want something else the thing to search on is "inplace Cooley-Tukey", perhaps with "bit reversal" thrown in there.

At this point it is worth clarifying the one point here that is of cryptographic relevance. The inplace Cooley-Tukey FFT $\mathcal{F}_{\mathsf{CT}}$ can be decomposed into

  1. A bunch of computations of butterflies, which I will call $\mathcal{B}$, followed by
  2. a bit-reversal permutation to "fix" that the outputs being in the wrong order, which I will call $\sigma$.

This is to say that

$$\mathcal{F}_{\mathsf{CT}}(x) = (\sigma\circ \mathcal{B})(x).$$

Some schemes (namely Kyber/ML-KEM) choose to omit $\sigma$. This is to say that they leave their FFT domain values "in the wrong order", and $\mathcal{F}_{\mathsf{Kyber}} = \mathcal{B}$. This has some benefits when it comes to AVX implementations of the FFT, but does mean that the FFT in Kyber is not exactly the same as a standard FFT, both because

  1. it is done over $\mathbb{Z}_p$ rather than $\mathbb{C}$ (this requires $p$ to be NTT friendly, but besides that is standard/boring), and
  2. the output is (not) permuted by $\sigma$.

Some more details:

One way of viewing the FFT is linear algebraically. The following is from Tolimieri et al., "Algorithms for Discrete Fourier Transform and Convolution", section 4.

The DFT is linear on a finite-dimensional space, and so can be written as a matrix multiplication. One can write an $N = 2M$ dimensional DFT as

$$F_{N} = P_N(I_2\otimes F_M)T_N(F_2\otimes I_M)$$

Here, $A\otimes B$ is the kronecker product of matrices, $T_N$ is the matrix of "twiddle factors", and $P_N$ is the matrix such that $P_N(A\otimes B) = B\otimes A$.

Anyway, applying the above relation a few times, one can find (Theorem 1) that if $N = 2^k$

$$ F_N = Q_N\prod_{i = 1}^k(I_{2^{i-1}}\otimes T_{2^{k-i+1}})\otimes (I_{2^{i-1}}\otimes F_2\otimes I_{2^{k-1}}) $$

Note that the kronecker product $A\otimes B$ satisfies the "mixed-product property" $(A\otimes B)(C\otimes D) = (AC)\otimes (BC)$, at least when the matrix sizes match up. One also has that $I_{2^k} = I_2\otimes I_{2^{k-1}} = I_{2^{k-1}}\otimes I_2$.

Here, one can compute that

$$Q_N = P_N(I_2\otimes P_{N/2})\dots (I_{N/4}\otimes P_4)$$

All that remains is to show that $Q_N$ is actually bit reversal. This is done in discussion around eq. 19 in the source.

$\endgroup$
5
  • $\begingroup$ Hi Mark, thanks for your reply and your efforts! I would agree with what you say. But: For me, this does not yet conclusively clarify how to apply this to my question. For me, the aspect that explains how the exponent $\text{brv}(2^k+i)$ is obtained is still missing. $\endgroup$
    – TreeBook1
    Commented Feb 22 at 19:12
  • $\begingroup$ @TreeBook1 the link "random website that I found" goes through a worked example for $N = 2^3$, though for FFTs over $\mathbb{C}$. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 22 at 19:44
  • $\begingroup$ @TreeBook1 you can also view this (linear)-algebraically. See example section 4 of "Algorithms for Discrete Fourier Transform and Convolution" by Tolimieri et. al, which includes a derivation where bit reversal pops out. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 22 at 19:56
  • $\begingroup$ Thanks for the references! Quick note, I know that the indices of the coefficients follow the bit reversal. This is also shown by the formula in your first source $(f_0 + ... f_4) + ... + (f_3 + ... f_7)$. But: How the exponent is then explained, from my source, is not yet completely transparent. Let me take a look at your second source. $\endgroup$
    – TreeBook1
    Commented Feb 22 at 20:02
  • $\begingroup$ +1 for mentioning Tolimieri's book $\endgroup$
    – kodlu
    Commented Feb 22 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.