Elliptic butterflies
Jean-Marc Couveignes, Reynald Lercier · 2025
Read Elliptic butterflies by Jean-Marc Couveignes, Reynald Lercier (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-27375.txt.
Introduction
Jean-Marc Couveignes and Reynald Lercier speed up key sums for wavy functions in this 2025 paper. The functions are elliptic functions, which repeat in two directions like a tiled pattern. Two tasks recur: finding values at many points, and the reverse, rebuilding a function from values. Both tasks are basic in coding and secrecy work.
The pair show both tasks split neatly into halves, again and again. The split echoes butterfly schemes, swap-and-combine patterns first used by Gauss for kindred sums. The result is a straight-line program, a fixed list of steps, whose cost grows gently with problem size. That is far cheaper than naive methods for large cases. The speedups carry into finite field arithmetic, coding theory, and cryptography.
Catalog record
| CREATOR | Jean-Marc Couveignes, Reynald Lercier |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-27375
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Elliptic butterflies Jean-Marc Couveignes, Reynald Lercier Abstract . We study natural evaluation and interpolation problems for elliptic functions and prove that they allow a recursive treatment using a variant of classical butterflies first introduced by Gauss. We deduce the existence of straight-line programs with d log ( d ) d\log(d) complexity for these problems and present applications to finite field arithmetic, coding theory and cryptography. Butterflyfish (freely adapted from [ Sha24 ] ) 1. Introduction Let {\mathbf{K}} be a field and let X be a smooth, projective, absolutely integral curve over {\mathbf{K}} . Let D be a divisor on X . We denote by {\mathcal{L}}(D) the associated linear space and call d its dimension. Let b_{0} , b_{1} , …, b_{d-1} be {\mathbf{K}} -points on X and not in the support of D . We consider the evaluation map (1) {\lx@inpgf@ignorespaces\mathop{\rm{ev}}\nolimits:} {\lx@inpgf@ignorespaces{\mathcal{L}}(D)} {\lx@inpgf@ignorespaces{\mathbf{K}}^{d}\,,} {\lx@inpgf@ignorespaces f} {\lx@inpgf@ignorespaces f(b_{l})_{0\leqslant l\leqslant d-1}\,.} which we assume to be invertible. We are interested in the complexity of evaluation (evaluating the map \mathop{\rm{ev}}\nolimits ) and interpolation (evaluating the reciprocal map \mathop{\rm{ev}}\nolimits^{-1} ). Elements in {\mathbf{K}}^{d} are represented by their entries. Elements in {\mathcal{L}}(D) are represented by their coordinates in a basis u=(u_{0},u_{1},\ldots,u_{d-1}) that must be specified. It is traditional to use bases satisfying one or several among the following properties: (1) the sum of the degrees of the u_{l} is minimal among all bases, (2) the u_{l} are eigenvalues of some automorphism of X , (3) the u_{l} are permuted by some automorphism of X . One looks for a straight-line program that solves the evaluation problem using additions and multiplications by constants in {\mathbf{K}} . The complexity of evaluation is then the minimum number of operations in such a straight-line program. One defines the complexity of interpolation in the same way. The classical and most important case is when X={\mathbf{P}}^{1} and D=(d-1)[\infty] and {\mathcal{L}}(D) is the space of polynomials of degree \leqslant d-1 in one variable x . In this situation, and assuming that {\mathbf{K}} contains a primitive d -th root of unity, the monomial basis (1,x,x^{2},\ldots,x^{d-1}) satisfies the first two conditions above. If further d is a power of two, which implies that the characteristic of {\mathbf{K}} is not two, then the complexities of evaluation and interpolation are bounded by (2) (3/2)d\log(d)+1. This is achieved using the well-known fast Fourier transform or FFT, first discovered by Gauss. See [ BCS97 , Theorem 2.6] and the historical account in [ HJB85 ] . Bostan and Schost give in [ BS05 ] a range of nice upper bounds for the complexity of evaluation and interpolation when the basis is the monomial basis or the Newton basis, and the evaluation set is an arithmetic sequence, a geometric sequence, or any set. They make no assumption on {\mathbf{K}} . For example, without making any restriction on {\mathbf{K}} nor on the evaluation set, the complexity of evaluation and interpolation in the monomial basis is bounded by an absolute constant times M(d)\log(d) where M(d) is the complexity of multiplying two polynomials of degree \leqslant d with coefficients in {\mathbf{K}} . Since the latter is bounded by a constant times d\log(d)\log(\log(d)) operations in {\mathbf{K}} , according to a result of Schönhage and Strassen [ BCS97 , Theorem 2.13] , we end up with a general bound of a constant times (3) d\log^{2}(d)\log(\log(d)) for evaluation and interpolation in the monomial basis, at a general set of points. Comparing Equations ( 3 ) and ( 2 ) we see that we save a factor \log(d)\log(\log(d)) when d is a power of two, {\mathbf{K}} contains a primitive d -th root of unity, \omega_{d} , and the evaluation set is the set of all d -th roots of 1 . This gain is not marginal as is demonstrated by the many implementations and applications of FFT. Indeed general evaluation and interpolation methods often use specific ones as subroutines. The key idea behind FFT is to use the involution x\mapsto-x to decompose the polynomial to be evaluated P(x)=\sum_{0\leqslant l\leqslant d-1}p_{l}\,x^{l} as a sum P(x)=P^{+}(x)+P^{-}(x) where P^{+}(x)=\sum_{0\leqslant 2l\leqslant d-1}p_{2l}\,x^{2l}\text{\,\,\, and \,\,\,}P^{-}(x)=\sum_{0\leqslant 2l+1\leqslant d-1}p_{2l+1}\,x^{2l+1}=x\sum_{0\leqslant 2l+1\leqslant d-1}p_{2l+1}\,x^{2l} are the even and odd parts of P(x) . This decomposition reduces the evaluation of P(x) to two similar problems of halved size, allowing a recursive approach that is classically illustrated using diagrams called butterflies (see Figure 1 ). 4-point FFT 4-point FFT p_{0} p_{2} p_{4} p_{6} p_{1} p_{3} p_{5} p_{7} {P^{+}(\omega_{4}^{0})} {P(\omega_{8}^{0})} {P^{+}(\omega_{4}^{1})} {P(\omega_{8}^{1})} {P^{+}(\omega_{4}^{2})} {P(\omega_{8}^{2})} {P^{+}(\omega_{4}^{3})} {P(\omega_{8}^{3})} {P^{-}(\omega_{4}^{0})} {P(\omega_{8}^{4})} {P^{-}(\omega_{4}^{1})} {P(\omega_{8}^{5})} {P^{-}(\omega_{4}^{2})} {P(\omega_{8}^{6})} {P^{-}(\omega_{4}^{3})} {P(\omega_{8}^{7})} \omega_{8}^{4} \omega_{8}^{0} \omega_{8}^{5} \omega_{8}^{1} \omega_{8}^{6} \omega_{8}^{2} \omega_{8}^{7} \omega_{8}^{3} Figure 1. An 8-point FFT butterfly In this work we define and study a family of evaluation and interpolation problems on an elliptic curve E having a {\mathbf{K}} -rational point t of order d , a power of two. We show that there are natural analogues of butterflies in this context. We replace roots of unity by multiples of the point t and the associated translations, while polynomials are replaced by functions in the space {\mathcal{L}}({\langle t\rangle}) equipped with a basis u of functions of degree \leqslant 2 . In particular the role of the involution x\mapsto-x is now played by the translation by T=(d/2)t , a point of order two. This results in complexity bounds {\mathcal{Q}}d\log(d) for the evaluation and interpolation problems 1 1 1 Note that everywhere in this article, the notation {\mathcal{Q}} stands for a positive absolute constant. Any sentence containing this symbol becomes true if the symbol is replaced in every occurrence by some large enough real number. . To be complete we should say that evaluation and interpolation are not quite enough for our purposes. We need another linear map on functions that we call reduction and which we now define in a general context. We now have three divisors D , E and B on the curve X . We denote by d the dimension of {\mathcal{L}}(D) . We assume that B is effective of degree d . We assume that D and B have disjoint support. We denote by {\mathbf{L}} the residue ring at B . This is a {\mathbf{K}} -algebra of dimension d . We assume that the residue map {\lx@inpgf@ignorespaces\mathop{\rm{ev}}\nolimits_{D}^{B}:} {\lx@inpgf@ignorespaces{\mathcal{L}}(D)} {\lx@inpgf@ignorespaces{\mathbf{L}}\,,} {\lx@inpgf@ignorespaces f} {\lx@inpgf@ignorespaces f\bmod B\,.} is invertible. We also assume that E and B have disjoint support and define {\lx@inpgf@ignorespaces\mathop{\rm{ev}}\nolimits_{E}^{B}:} {\lx@inpgf@ignorespaces{\mathcal{L}}(E)} {\lx@inpgf@ignorespaces{\mathbf{L}}\,,} {\lx@inpgf@ignorespaces f} {\lx@inpgf@ignorespaces f\bmod B\,.} the residue map. For every function F in {\mathcal{L}}(E) there exists a unique function f in {\mathcal{L}}(D) such that F\equiv f\pmod{B}\text{\,\,\, that is \,\,\,}\mathop{\rm{ev}}\nolimits_{E}^{B}(F)=\mathop{\rm{ev}}\nolimits_{D}^{B}(f)\in{\mathbf{L}}. We choose a basis for {\mathcal{L}}(D) and a basis for {\mathcal{L}}(E) . The reduction problem takes as input the coordinates of F and returns the coordinates of f . We will explain how to efficiently solve a family of reduction problems on elliptic curves. In the situation we are interested in, the divisor E is 2D because we need to reduce the product of two functions in {\mathcal{L}}(D) . We will present three applications of these fast evaluation, interpolation, and reduction algorithms. The first one is the construction of normal bases for extensions of finite fields of degree a power of two, allowing particularly fast multiplication. The second one is the description of [d,d/2,d/2+1] -error correcting codes that can be encoded and checked