Faster polynomial multiplication over finite fields using cyclotomic coefficient rings (Q2274408): Difference between revisions

The main result of the paper is an algorithm for multiplication in \(\mathbb{F}_p [X]\) whose complexity in the deterministic multitape Turing model is better than that of the published algorithms. For positive real \(x\), let \(\log^* x\) denote the least non-negative integer \(k\) such that \(\log (\ldots \log (x)) \le 1\) (\(k\) iterations). For a positive integer \(n\) one puts \(\lg n =\max (0, \lceil \log_2 n \rceil)\). The best current bound for the number of bit operations required to multiply two \(n\)-bits integers is \(O\left(n\lg n K_\mathbb{Z}^{\log^* n} \right)\), where \(K_\mathbb{Z}=4\). Theorem 1.1 of the paper under review asserts that the multiplication of polynomials in \(\mathbb{F}_p [X]\) of degree less than \(n\) can be achieved in \(O\left(n\lg p \lg (n\lg p) 4^{\max (0, \log^* n -\log^* p)} K_\mathbb{Z}^{\log^* p}\right)\) bit operations, uniformly for all positive \(n\) and all primes \(p\). This bound is obtained by converting the initial multiplication in \(\mathbb{F}_p [X]\) to a bivariate multiplication problem in \(\mathbb{F}_p [Y,Z]/(\Phi_\alpha (Y), Z^m-1)\), with \(\alpha\), \(m\) coprime integers (not necessarily prime) such that \(\alpha m=N>n\), and \(\Phi_\alpha\) a cyclotomic polynomial. The bulk of the work is to show how to choose \(\alpha\), \(m\), and \(N\) such that all the following conditions hold: \(N\) is not much larger than \(n\); \(\deg (\Phi_\alpha)\) is not much smaller than \(n\); the ring \(\mathbb{F}_p [Y]/(\Phi_\alpha)\) contains a primitive \(m\)th root of unity; \(m\) is a product of many integers that are exponentially smaller than \(n\); \(\alpha\) is exponentially smaller than \(n\). The resulting algorithm is of theoretical interest rather than a practical one. Possible variations on the main result in different complexity models or for various polynomial rings are also mentioned. Despite its technicality, the paper is a nice reading, thanks to detailed explanations for all choices made for the implementation of the ideas.