# Number Theoretic Transform (NTT) II

[toc]

## - Multiplication Tecnhiques

### Common Sub-Expression Elimination (CSE)
$(A+BX)(C+DX)$
$= AC + ((A+B)(C+D)-AC-BD)+BDX^2$
$= (AC-BDX)(1-X) + (A+B)(C+D)X$

#### Karatsuba's Algorithm: 1 multiplication equals to 3 addition
$M(2n)\approx 3M(n)$
Whether transform or not depends the on cost of multiplication and addition on a different system.
In breif, if cost of 3M(n) is larger than M(2n), we don't transform it.

### Lagrange Polynomial
一個n次多項式需要n+1個條件決定

For a polynomial with degree 4, in general, we use 0, infinity, 1, -1. Sometimes we choose 2 or -2 as the fifth value.

### Toom-Cook Algorithm

$(A_0 + A_1X + A_2X^2)(B_0 + B_1X + B_2X^2)$
Equals to the calculation listed below

$M(3n) \approx 5M(n)$
$M(kn) \approx (2k-1)M(n)$

More efficient than Karatsuba's Algorithm, since $\frac{\log3}{\log2} > \frac{\log5}{\log3}$ (time cost)

Toom-Cook v.s. Karatsuba
:::info
The Lagrange Polynomials might cause unexpected extra multiplication. As a result, sometimes use 2 Karatsuba Algorithm to substitute a single Toom-Cook Algorithm.
:::

### FFT (Fast Fourier transform)
Recall CRT(Chinese Remainder Theorem)
If $\frac{1}{2c}$ exists,

$\frac{R[x]}{<x^{2n}-c^2>} \approx \frac{R[x]}{<x^n-c>} \times \frac{R[x]}{<x^n+c>}$

If

$f_0 + f_1x^n \mapsto (f_0 +cf_1, f_0 - cf_1)$

Then

$\frac{g_0+g_1}{2} + \frac{g_0-g_1}{2c}x^n \leftarrow (g_0, g_1)$
> `p.s. no left-mapsto`

Also, can be written in the form of

$\begin{cases} A_i = a_i + cb_i \\
B_i = a_i - cb_i \end{cases}$

$\frac{R[x]}{{<x^{2^k}> - 1}}$ 的 $\ \omega^{2^{k-1}} = -1$ 的 $\ \omega$ 存在 ($2^k$次的主根或素根)

> - ex: 

1. Normal FFT, mod x equals to f(x)
2. Kyber: did not have a constant, it mods $x^2 + c$, so the result is a polynomials with degree 1

密碼學中的FFT，不需要將訊號重排，僅需對應幾個頻率相乘 (無特定順序)。

---
---
### Note

Some note taken by me below
> [name=sixkwnp(王科元)]
> [time=Fri, Jul 7, 2023 3:36 PM]
>
> [color=#48e252]