fntt64 fntt64 - Fast Number Theoretic Transform 64x64
Define a prime number $2^{64}-2^{32}+1$ as $p$ , and $7$ is $p-1$ -th primitive root on $\mathbb Z/p\mathbb Z$
Define $r_{c,n}$ as $\left(\left(7^{2^{32}-1}\right)^{2^{(32-c)}}\right)^{n+1}\equiv r_{c,n}\mod p\quad\forall(c,n)\in\mathbb Z,1\leq c\leq 32,0\leq n\leq 2^c-1$
For two inputs $f(x),g(x)$ , the convolution of them, $\left(f\ast g\right)$ , is able to be calculated as below.
$$
F_{c,j}=\sum_{i=0}^{2^c-1}{r_{c,ij}f(i)}
\quad
G_{c,j}=\sum_{i=0}^{2^c-1}{r_{c,ij}g(i)}
$$
$$
\lparen f\ast g\rparen_{c,j}=\frac{1}{2^c}\sum_{i=0}^{2^c-1}{\dfrac{F_{c,j}G_{c,j}}{r_{c,ij}}}
$$
Please note that, $\dfrac{1}{2^c}$ is a value of $x$ which satisfies $2^cx\equiv 1\mod p$ ,
and also $\dfrac{1}{r_{c,ij}}$ is implied from $r_{c,ij}x\equiv 1\mod p$
fntt64 depends on $r_{6,n}$ because $7^{2^{-6}\left(p-1\right)}\equiv 2^{39}\mod p$ is established.
I've described more detail in 高速数論変換で多倍長整数の畳み込み乗算
Action
Status
Build
CodeQL
Coverage
Run
The scripts and documentation in this project are released under the BSD-3-Clause License
