On ECFFT and applications to various poly algos (after [ECFFT](https://arxiv.org/abs/2107.08473))

# On ECFFT and applications to various poly algos (after [ECFFT](https://arxiv.org/abs/2107.08473)) ## FFTrees Let $F_q$ be a finite field of size $q$ and assume $2^k <q$. A `FFTree` of depth $k$ is a collection $\{(L^{(i)}, \phi_{(i)})\mid i = 0, ... k-1\}$ where $L^{(i)}\subseteq F_q$ and $\phi_{i}= \frac{f_i}{g_i}$ is a rational function (with coefficients in $F_q$) so that: * $|L^{(i)}| = 2^{k-i}$. * $\max(\deg(f_i), \deg(g_i))=2$. * $\phi_{i}(L^{(i)})= L^{(i+1)}$. ### Notes * For any element $s_i\in L^{(i)}$, we have $|\phi^{-1}(s_i)|=2$ so we can build a balanced binary tree corresponding to the FFTree. For example assume that $k=2$, $q=11$, $\phi_0 (x)= x^2$ and $\phi_1(z) = x^2+7x+2$: ```graphviz strict graph { node [margin=0 fontcolor=blue fixedsize=false shape=oval style=filled] s0[label = 1] s12[label = 3] s11[label = 4] s22[label = 2] s21[label = 9] s24[label = 5] s23[label = 6] subgraph cluster_0 { label=<L(2)>; s0; } subgraph cluster_1 { label=<L(1)>; s12; s11; } subgraph cluster_2 { label=<L(0)>; s21; s22; s23; s24;} s0 -- {s12 s11}; s11 -- {s22 s21}; s12 --{s24 s23}; } ``` * In the case where $F_q$ contains all the $2^k$-th roots of 1, one can construct an FFTree in which $L^{(i)} = \{a \in F_q \mid a^{2^i}=1\}$ and $\phi_i(x) =x^2$. This is the usual approach to FFT. * One can always construct a FFTree starting from a series of elliptic curves and 2-isogenies between them. We choose to not describe that here because it will just complicate the exposition. It suffices to just say that this is possible as long as $2^k \le 2\sqrt{q}$. ## Polynomial representations using FFTrees. **Definition:** Let $(L^{(i)}, \phi_{(i)})$ an FFTree of depth $k$ and $L= L_0$. * A `basic set` is a subset of $L$ that is the set of descendants of some element of some $L^{(i)}$. Note that the size of such a set is $2^{k-i-1}$. * A basic set $S$ of size $2^i$ is uniquelly decomposed as a disjoint union of two basic sets of size $2^{i-1}$. These are called the `moieties` of $S$. **Notes:** * Two basic sets are either disjoint or included in one onother. * If $S$ is a basic set of size $2^a$ and $b<a$ then the basic sets of size $2^b$ that are contained in $S$ partition $S$. * In particular the basic sets of a given size partition $L$. We fix a filtration $U_0 \subset U_1 \subset \cdots U_k \subset L$ where $U_i$ is a `basic set` of size $2^i$. Note that it follows that $U_i$ is a moiety of $U_{i+1}$. A polynomial $P$ of degree $n < 2^a$ can be uniquely represented by its values at the points of $U_a$. In other words there is an injective correspondence between polynomials of degree $n$ and `evaluation tables` on $U_a$, that is functions $f: U_a \rightarrow F_q$. If $n= 2^a$ then this correspondence is bijective but otherwise there are some "redundancy" in the evaluation table and not all correspond to polys. If $S$ is a basic set then the evaluation table of the polynomial $P$ at $S$ is denoted by $\left< P\wr S \right>$. As mentioned above if $P$ and $Q$ are two polynomials of degree less than $2^a$ and $S$ is a basic set of size $2^a$ then $\left< P\wr S \right> =\left< Q\wr S \right>$ if and only if $P=Q$. The fundamental property here is the following: **Proposition:** Let $\phi= \frac fg$ be a rational map with coefficients in $F_q$ and $\max(\deg(f), \deg(g))=2$ and $P$ is a polynomial of degree $< 2n$. 1. There is unique pair of polynomials $(P_0, P_1)$ of degree less that $\frac n 2$ so that $P(x) = (P_0(\phi(X)) + XP_1(\phi(X)))g(X)^{\frac n 2}$ 2. Suppose $\phi^{-1}(t)=\{s_1, s_2\}$ then the map $(P(s_1), P(s_2))\rightarrow (P_0(t), P_1(t))$ is linear and invertible. In another words the correspondence $P\rightarrow(P_0, P_1)$ has the property that $\left< P\wr S \right>$ can be obtained from $\left< P_0\wr \phi(S) \right>$ and $\left< P_1\wr \phi(S) \right>$. The standard example of this is the usual one from FFT in which $\phi(x)=x^2$ and so: $P(X) = (P_0(X^2) + XP_1(X^2))$ where $P_0$ comes from the the "even powers in P" and $P_1$ from the "odd powers in P". ## The extend algorithm. The definitions above seem to depend of the choices we make for the basic sets. The basic algorithm is one that allows to move from one basic set to another. Suppose that $P$ is a polynomial $\deg(P)<n$ and $S,S'\subseteq L$ are two `basic sets` of size $n$ then there is a an algorithm of complexity $O(n\log n)$ that computes $\left< P\wr S' \right>$ from $\left< P\wr S \right>$. The algorithm is quite natural. We decompose $\left< P\wr S \right> = \left< P_0\wr \phi(S) \right> \amalg \left< P_1\wr \phi(S) \right>$ and then recursively apply the algorithm to $\left< P_0\wr \phi(S) \right>$ and $\left< P_1\wr \phi(S) \right>$ to get $\left< P_0\wr \phi(S') \right>$ and $\left< P_1\wr \phi(S') \right>$ and so $\left< P\wr S' \right>$. ## The multiplication algorithm Suppose that $P$ and $Q$ are two polynomials of degree $< \frac n 2$. Let $S$ be a `basic set` of size $n$ and $S_0, S_1$ its moeities. There is an algorithm of complexity $O(n\log n)$ that recives as inputs $\left< P\wr S_0 \right>$ and $\left< Q\wr S_0 \right>$ and whose output is $\left< (P\cdot Q)\wr S \right>$. The algorithm is as follows: We first use the extend algorithm to obtain $\left< P\wr S_1 \right>$ and $\left< Q\wr S_1 \right>$ and then $\left< P\wr S \right> = \left< P\wr S_0 \right> \amalg \left< P\wr S_1 \right>$ respectively $\left< Q\wr S \right> = \left< Q\wr S_0 \right> \amalg \left< Q\wr S_1 \right>$. The resulting product only costs $O(n)$. ## Degree computation Given $S$ a basic set of size $n$ and $P$ a polymomial with $\deg(P) < n$. There is an algorithm of complexity $O(n\log n)$ that receives as input $\left< P\wr S \right>$ and computes $\deg(P)$. If $S= S_0 \amalg S_1$ is the decomposition of $S$ into moieties then we precompute $\left< Z_0\wr S_1 \right>$ where $Z_0$ is the vanishing polynomial of $S_0$. The main idea here is as follows: * consider $\left< Q \wr S_1 \right>$ the extension of $\left< P\wr S_0 \right>$ to $S_1. * If $\left< Q \wr S_1 \right>= \left$ then $\deg(P)$ is smaller than $\frac n 2$ so we apply the algorithm recusively on $\left$. * Otherwise $\deg(\left) = \frac n 2 + \deg(\left< \frac{(P-Q)}{Z_0} \wr S_1 \right>)$ ## Long Division Let $S = S_0 \amalg S_1$ be a the moiety decomposition of a base set of size $n$ and a ssume $A$ is a polynomial with $\deg(A)<\frac n 2$ so that $A$ has no zeroes in $S_0$. Let $P$ a polynomial with $\deg(P)< n$ and $P = Q\cdot A + R$ where $\deg(R)< \deg(A)$. There is an algorithm of complexity $O(n\log(n))$ that receives $\left$ and produces $\left< R \wr S \right>$ and $\left< R \wr S \right>$. TODO ## Interpolation from the set S. Let $S = S_0 \amalg S_1$ be a the moiety decomposition of a base set of size $n$. Assume that $P = \sum_{i=0}^{n-1} a_i X^i$ is a polynomial of degree less than $n$. There is an algorithm of complexity $O(n\log^2(n))$ that given as input $\left$ produces coefficients $a_i$. TODO ## Evaluation on the set S. Let $S = S_0 \amalg S_1$ be a the moiety decomposition of a base set of size $n$. Assume that $P = \sum_{i=0}^{n-1} a_i X^i$ is a polynomial of degree less than $n$. There is an algorithm of complexity $O(n\log^2(n))$ that given as input the coefficients $a_i$ produces $\left$. TODO ## Chinese reminder Let $S = S_0 \amalg S_1$ be a the moiety decomposition of a base set of size $n$ and a ssume $A, B$ polynomial with $\deg(A), \deg(B)<\frac n 2$ so that $A$ and $B$ have no zeroes in $S_0$. Let $P, Q$ polynomials with $\deg(P), \deg(Q) < \frac n 2$. and $P = Q\cdot A + R$ where $\deg(R)< \deg(A)$. There is an algorithm of complexity $O(n\log(n))$ that receives $\left, \left$ and produces $\left< R \wr S \right>$ where $R$ is the only polynomial with $\deg(R)< \deg(A) + \deg(B)$ so that $R \equiv P\pmod A$ and $R \equiv Q \pmod B$. TODO ## Evaluation on general sets. Assume that $P = \sum_{i=0}^{n-1} a_i X^i$ is a polynomial of degree less than $n$ and $n<q$. Given a set $B$ of $m$ points in $F_q$, there is an algorithm of complexity $O(n\log^2(n) +m\log^2(m) )$ that takes as input the set $B$ and the list $(a_0, \dots a_{n-1})$ and evaluates $\left$. TODO ## Interpolation from general sets Assume that $P = \sum_{i=0}^{n-1} a_i X^i$ is a polynomial of degree less than $n$ and $n<q$. Given a set $B$ of $n$ points in $F_q$, there is an algorithm of complexity $O(n\log^2(n))$ that takes as input $\left$ and computes the list $(a_0, \dots a_{n-1})$. TODO