Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
Polynomials in number theory (11C08) Polynomials over finite fields (11T06) Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Polynomials and finite commutative rings (13M10) Numerical methods for wavelets (65T60) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40)
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.
- Even faster integer multiplication
- Fast multiplication of large numbers
- Fast multiplication of polynomials over fields of characteristic 2
- Faster integer multiplication
- Faster integer multiplication
- Faster integer multiplication using short lattice vectors
- Faster polynomial multiplication over finite fields
- scientific article; zbMATH DE number 3140885 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
- Modern computer algebra
- New algorithms for digital convolution
- On distinguishing prime numbers from composite numbers
- On fast multiplication of polynomials over arbitrary algebras
- On the deterministic complexity of factoring polynomials over finite fields
- On the number of divisors of a natural number having the form \(p-1\)
- Searching for Primitive Roots in Finite Fields
- The difference between consecutive primes. II
- On fast multiplication of polynomials over arbitrary algebras
- Fast multiplication of polynomials over fields of characteristic 2
- Counting invariant subspaces and decompositions of additive polynomials
- Asymptotics of 3-stack-sortable permutations
- Fast reduction of algebraic lattices over cyclotomic fields
- Amortized multi-point evaluation of multivariate polynomials
- Polynomial modular product verification and its implications
- Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields
- Directed evaluation
- Algorithms for simultaneous Hermite-Padé approximations
- Fast amortized multi-point evaluation
- Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals
- On the complexity exponent of polynomial system solving
- Integer multiplication in time \(O(n\log n)\)
- Fast algorithms for solving equations of degree \(\le 4\) in some finite fields
- Faster polynomial multiplication via discrete Fourier transforms
- Faster polynomial multiplication over finite fields
- A classification of algorithms for multiplying polynomials of small degree over finite fields
- A note on the paper ``Multiplication of polynomials modulo \(x^n\) by Murat Cenk and Ferruh Özbudak
- Polynomial multiplication over finite fields in time O(n n)
- Frobenius additive fast Fourier transform
- Derivation and analysis of fast bilinear algorithms for convolution
- Multiplication
- Multiplication of polynomials modulo \(x^n\)
- Orienteering with one endomorphism
- Polynomial constructions of Chudnovsky-type algorithms for multiplication in finite fields with linear bilinear complexity
- Univariate polynomial factorization over finite fields with large extension degree
- Symmetric encryption algorithms in a polynomial residue number system
- Amortized bivariate multi-point evaluation
- Arithmetic terms for sums of multinomial coefficients
- Explicit methods in number theory. Abstracts from the workshop held September 1--6, 2024
- Multiplication in finite fields with Chudnovsky-type algorithms over the projective line
- Optimizing the half-gcd algorithm
- Fast exact algorithms using Hadamard product of polynomials
This page was built for publication: Faster polynomial multiplication over finite fields using cyclotomic coefficient rings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274408)
