Multiplication of polynomials over the binary field
Chunlei Liu · 2025
Read Multiplication of polynomials over the binary field by Chunlei Liu (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-2505-03101.txt.
Introduction
Chunlei Liu wrote a 2025 note in computer algebra on multiplying polynomials over the binary field, where coefficients are only zero or one. Such multiplication sits inside error correcting codes and cryptography, so faster methods matter. Liu studies the additive Fourier transform and builds a fast multiplication algorithm on it. The stated bit complexity grows just above the near linear rate of the best known transforms, with two extra logarithmic factors. The hosted text gives only this summary.
Catalog record
| CREATOR | Chunlei Liu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-03101
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multiplication of polynomials over the binary field Chunlei Liu Abstract Additive Fourier Transform for polynomials over the binary field is studied. The technique of Gao-Mateer is generalized, giving an algorithm which compute the product of two polynomials of degree < n <n over the binary field in O ( n log n ( log log n ) 2 ) O(n\log n(\log\log n)^{2}) bit operations. Key words : finite field, polynomial multiplication, evaluation, interpolation, Additive Fourier Transform. 1 INTRODUCTION Fast multiplication of polynomials is an important problem in computational number theory, computer algebra, algebraic coding theory and in cryptography. In fast, fast multiplication of polynomials gives rise to fast division of polynomials, and thus gives rise to fast Generalized Euclidean Algorithm of polynomials [ AHU74 , Kn81 ] . Similarly, fast Midway Euclidean Algorithm of polynomial, which plays an equal role as Berlekamp-Massey Algorithm [ Be68 , Ma69 , Mc78 ] . Researches on Fast Polynomial Multiplication have given birth to ingenious ideas as well as beautiful results. Contributors to these ideas are Karatsuba-Ofman [ KO63 ] , Cooley-Tukey [ CT65 ] , Wang-Zhu [ WZ88 ] , Gathen-Gerhard [ GG96 ] , Schönhage [ Sch77 ] , Cantor [ Ca89 ] , and etc. In 1965, Cooley-Tukey invented the Fast Fourier Transform to get a Fast Polynomial Multiplication Algorithm. In 1977, Schönhage invented the Number Theoretic Transform to get a Fast Polynomial Multiplication Algorithm. And, Wang-Zhu and Cantor invented the Additive Fourier Transform to get a fast polynomial multiplication algorithm. In the Additive Fourier Transform approach to fast polynomial multiplication, a fast evaluation algorithm is needed. In 1996, Gao-Matter [ GM10 ] introduced an evaluation algorithm, which is efficient for polynomials whose degree is of the form 2^{2^{l}} . We shall generalize the method of Gao-Mateer to prove the following theorem. Theorem 1.1 There exists a polynomial multiplication algorithm which computes the product of two polynomials of degree <n over {\rm GF}(2) in O(n\log n(\log\log n)^{2}) bit operations. Notice that, Wang-Zhu’s algorithm may yield the bit complexity O(n(\log_{2}n)^{2}) , Cantor’s algorithm yields the bit complexity O(n(\log_{2}n)^{\log_{2}3/2}) , and Gao-Mateer’s algorithm may yields the bit complexity O(n(\log_{2}n)(\log\log n)^{2}) when n is of the form 2^{2^{l}} . 2 Evaluation and Remaindering In this section we generalize the evaluation algorithm of Gao-Mateer [ GM10 ] . We shall split it into an evaluation algorithm {\rm EA}(f,a,m,L) and a remaindering algorithm {\rm RA}(f,b,m,l,L) . We begin with the following definition. Definition 2.1 Let L be a positive integer. A basis (\beta_{1},\cdots,\beta_{2^{L}}) of {\rm GF}(2^{2^{L}}) over {\rm GF}(2) is called a Cantor basis if \beta_{1}=1 , and \beta_{i}^{2}-\beta_{i}=\beta_{i-1} for all i>1 . Let (\beta_{1},\cdots,\beta_{2^{L}}) be a Cantor basis of {\rm GF}(2^{2^{L}}) over {\rm GF}(2) . We write W_{i}=\sum_{j=1}^{i}{\rm GF}(2)\beta_{j},\ i=1,\cdots,2^{L}. One can show that W_{i} is independent of the choice of the Cantor basis. The basis (\beta_{1},\cdots,\beta_{2^{L}}) certainly gives an isomorphism from {\rm GF}(2)^{2^{L}} to {\rm GF}(2^{2^{L}}) , and thus the lexicographic order in {\rm GF}(2)^{2^{L}} induces an order in {\rm GF}(2^{2^{L}}) . Under this induced order, elements of {\rm GF}(2^{2^{L}}) can be ordered increasingly as \varpi_{0},\varpi_{1},\cdots,\varpi_{2^{2^{L}}-1} . That is, \varpi_{0}<\varpi_{1}<\cdots<\varpi_{2^{2^{L}}-1}. The tasks of {\rm EA}(f,a,m,L) and {\rm RA}(f,b,m,l,L) are described in the following tables. Task of {\rm EA}(f,a,m,L) input 1 L : a number; input 2 m : a number \leq 2^{L} ; input 3 a : an element in W_{2^{L}}\backslash W_{m} ; input 4 f : a polynomial over {\rm GF}(2^{2^{L}}) of degree <2^{m} ; install (\beta_{1},\cdots,\beta_{2^{L}}) : a Cantor basis of {\rm GF}(2^{2^{L}}) over {\rm GF}(2) ; output (v_{0},\cdots,v_{2^{m}-1}) : v_{i}=f(a+\varpi_{i}) , i=0,\cdots,2^{m}-1 ; Task of {\rm RA}(f,b,m,l,L) input 1 L : a number; input 2 l : a number \leq L ; input 3 m : a number satisfying 2^{l-1}<m\leq 2^{l} ; input 4 b : an element in W_{2^{L}}\backslash W_{m-2^{l-1}} ; input 5 f : a polynomial over {\rm GF}(2^{2^{L}}) of degree <2^{m} ; install (\beta_{1},\cdots,\beta_{2^{L}}) : a Cantor basis of {\rm GF}(2^{2^{L}}) over {\rm GF}(2) ; output (r_{0},\cdots,r_{2^{m-2^{l-1}}-1}) : r_{j} is the remainder of f modulo x^{2^{2^{l-1}}}-x-(b+\varpi_{j}) ; We now describe the mechanisms of the evaluation algorithm and the remaindering algorithm. Lemma 2.2 (evaluation mechanism) Let L,m be numbers with 1<m\leq 2^{L} , and l=\lceil\log_{2}m\rceil . Let a\in W_{2^{L}}\backslash W_{m} , and b=a^{2^{2^{l-1}}}-a . Let f be a polynomial over {\rm GF}(2^{2^{L}}) of degree <2^{m} . Let 0\leq i<2^{l-1},0\leq j<2^{m-2^{l-1}} , a_{j}=a+\varpi_{j2^{2^{l-1}}} , and r_{j} the remainder of f modulo x^{2^{2^{l-1}}}-x-(b+\varpi_{j}) . Then f(a+\varpi_{i+j2^{2^{l-1}}})=r_{j}(a_{j}+\varpi_{i}). Proof. It is easy to see that (a+\varpi_{j2^{2^{l-1}}}+\varpi_{i})^{2^{2^{l-1}}}-(a+\varpi_{j2^{2^{l-1}}}+\varpi_{i})=b+\varpi_{j}. That is, x^{2^{2^{l-1}}}-x-(b+\varpi_{j}) vanishes at a+\varpi_{j2^{2^{l-1}}}+\varpi_{u} . As r_{j} is the remainder of f modulo x^{2^{2^{l-1}}}-x-(b+\varpi_{j}) , we have f(a+\varpi_{j2^{2^{l-1}}}+\varpi_{i})=r_{j}(a+\varpi_{j2^{2^{l-1}}}+\varpi_{i})=r_{j}(a_{j}+\varpi_{i}). It is easy to see that \varpi_{j2^{2^{l-1}}}+\varpi_{i}=\varpi_{i+j2^{2^{l-1}}} . Therefore f(a+\varpi_{i+j2^{2^{l-1}}})=r_{j}(a_{j}+\varpi_{i}) . The lemma is proved. The above lemma reduces the evaluation of f to simultaneous remaindering of f modulo x^{2^{2^{l-1}}}-x-(b+\varpi_{j}) , j=0,\cdots,2^{m-2^{l-1}}-1. Before describing the remaindering mechanism, we recall following expansion of polynomials introduced by Gao-Mateer [ GM10 ] . Definition 2.3 Let k be a positive number, and f(x) a polynomial over \overline{{\rm GF}(2)} . The Gao-Mateer polynomials of f at x^{2^{k}}-x is the tuple (\hat{f}_{0},\cdots,\hat{f}_{2^{k}-1}) of polynomials over \overline{{\rm GF}(2)} such that f(x)=\sum_{i=0}^{2^{k}-1}x^{i}\hat{f}_{i}(x^{2^{k}}-x)^{j}. Lemma 2.4 (remaindering mechanism) Let L,m be numbers with 1<m\leq 2^{L} . Let l=\lceil\log_{2}m\rceil , and b\in W_{2^{L}}\backslash W_{m-2^{l-1}} . Let f be a polynomial over {\rm GF}(2^{2^{L}}) of degree <2^{m} , and (\hat{f}_{0},\cdots,\hat{f}_{2^{2^{l-1}}-1}) the Gao-Mateer polynomials of f at x^{2^{2^{l-1}}}-x . Let 0\leq i<2^{l-1},0\leq j<2^{m-2^{l-1}} , r_{ij}=\hat{f}_{i}(b+\varpi_{j}) , and r_{j}(x)=\sum_{i=0}^{2^{2^{l-1}}-1}r_{ij}x^{i} . Then r_{j} is the remainder of f modulo x^{2^{2^{l-1}}}-x-(b+\varpi_{j}) . Proof. In fact, \displaystyle f(x) \displaystyle= \displaystyle\sum_{i=0}^{2^{2^{l-1}}-1}x^{i}\hat{f}_{i}(x^{2^{2^{l-1}}}-x) \displaystyle\equiv \displaystyle\sum_{i=0}^{2^{2^{l-1}}-1}x^{i}\hat{f}_{i}(b+\varpi_{j}) \displaystyle\equiv \displaystyle\sum_{i=0}^{2^{2^{l-1}}-1}r_{ij}x^{i} \displaystyle\equiv \displaystyle r_{j}(x)\left({\rm mod}x^{2^{2^{l-1}}}-x-(b+\varpi_{j})\right). The lemma is proved. The above lemma reduces to remaindering of f to evaluations of \hat{f}_{0},\cdots,\hat{f}_{2^{2^{l-1}}-1} . The above two lemmas together show that the evaluation algorithm and the remaindering algorithm interplay between each other, and justify the following pseudo-codes. Pseudo-codes of {\rm EA}(f,a,m,L) 1 if m=1 ; 2 (v_{0},v_{1}):=(f(a),f(a+1)) ; 3 else 4 l:=\lceil\log_{2}m\rceil ; 5 b:=a^{2^{2^{l-1}}}-a ; 6 r:={\rm RA}(f,b,m,l,L) ; 7 for j=0 to 2^{m-2^{l-1}}-1 ; 8 a_{j}:=a+\varpi_{j2^{2^{l-1}}} ; 9 (v_{0+j2^{2^{l-1}}},\cdots,v_{2^{2^{l-1}}-1+j2^{2^{l-1}}}):={\rm EA}(r_{j},a_{j},2^{l-1},L) ; 10 end for 11 end if Return (v_{0},\cdots,v_{2^{m}-1}) ; Pseudo-codes of {\rm RA}(f,b,m,l,L) 1 \hat{f}:= the Gao-Mateer polynomials of f at x^{2^{2^{l-1}}}-x ; 2 for i=0 to 2^{2^{l-1}}-1 ; 3 (r_{i0},\cdots,r_{i,2^{m-2^{l-1}}-1}):={\rm EA}(\hat{f}_{i},b,m-2^{l-1},L) ; 4 end for 5 for j=0 to 2^{m-2^{l-1}}-1 ; 6 r_{j}:=\sum_{i=0}^{2^{m-2^{l-1}}-1}r_{ij}x^{i} ; 7 end for 8 Return (r_{0},\cdots,r_{2^{m-2^{l-1}}}) ; Theorem 2.5 The evaluation algorithm {\rm EA}(f,a,m,L) costs at most 2^{m-1}m multiplications in {\rm GF}(2^{2^{L}}) . Proof. Let E_{0}(m) and R_{0}(m) be the maximum number of multiplications in running {\rm EA}(f,a,m,L) and {\rm RA}(f,b,m,l,L) respectively. If m=1 , then by Line 2 in {\rm EA}(f,a,m,L) , E_{0}(m)=2^{m-1}m. Assume that m>1 . By Lines 6 and 9 in {\rm EA}(f,a,m,L) , E_{0}(m)\leq 2^{m-2^{l-1}}E_{0}(2^{l-1})+R_{0}(m). By Gao-Mateer’s result, Line 1 in {\rm RA}(f,b,m,l,L) costs no multiplications. So, by Line 3 in {\rm RA}(f,b,m,l,L) , R_{0}(m)\leq 2^{2^{l-1}}E_{0}(m-2^{l-1}). Thus E_{0}(m)\leq 2^{m-2^{l-1}}E_{0}(2^{l-1})+2^{2^{l-1}}E_{0}(m-2^{l-1}). Hence, by induction, E_{0}(m)\leq 2^{m-2^{l-1}}\cdot 2^{2^{l-1}-1}2^{l-1}+2^{2^{l-1}}\cdot 2^{m-2^{l-1}-1}(m-2^{l-1})=2^{m-1}m. The theorem is proved. Lemma 2.6 Let E_{1}(m) be the maximum number of additions in running the algorithm {\rm EA}(f,a,m,L) . If m>1 , then \frac{E_{1}(m)}{2^{m}}\leq\frac{E_{1}(2^{l-1})}{2^{2^{l-1}}}+\frac{E_{1}(m-2^{l-1})}{2^{m-2^{l-1}}}+m-2^{l-1},\ l=\lceil\log_{2}m\rceil. Proof. Let R_{1}(m) be the maximum number of additions in running the algorithm {\rm RA}(f,b,m,l,L) . Then by Lines 6 and