Back to Search
Start Over
Fast multivariate multi-point evaluation revisited.
- Source :
-
Journal of Complexity . Feb2020, Vol. 56, pN.PAG-N.PAG. 1p. - Publication Year :
- 2020
-
Abstract
- In 2008, Kedlaya and Umans designed the first multivariate multi-point evaluation algorithm over finite fields with an asymptotic complexity that can be made arbitrarily close to linear. However, it remains a major challenge to make their algorithm efficient for practical input sizes. In this paper, we revisit and improve their algorithm, while keeping this ultimate goal in mind. In addition we sharpen the known complexity bounds for modular composition of univariate polynomials over finite fields. [ABSTRACT FROM AUTHOR]
- Subjects :
- *FINITE fields
*POLYNOMIALS
Subjects
Details
- Language :
- English
- ISSN :
- 0885064X
- Volume :
- 56
- Database :
- Academic Search Index
- Journal :
- Journal of Complexity
- Publication Type :
- Academic Journal
- Accession number :
- 139707605
- Full Text :
- https://doi.org/10.1016/j.jco.2019.04.001