Fast multivariate multi-point evaluation revisited

Joris van der Hoeven; Grégoire Lecerf

doi:10.1016/j.jco.2019.04.001

Fast multivariate multi-point evaluation revisited

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	101405
Journal	Journal of Complexity
Volume	56
DOIs	https://doi.org/10.1016/j.jco.2019.04.001
Publication status	Published - 1 Feb 2020

Keywords

Algorithm
Complexity bound
Kedlaya–Umans algorithm
Modular composition
Multi-point evaluation
Power projection

Access to Document

10.1016/j.jco.2019.04.001

Cite this

@article{8a32d8c714954e0092f3da4198e668b4,

title = "Fast multivariate multi-point evaluation revisited",

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.",

keywords = "Algorithm, Complexity bound, Kedlaya–Umans algorithm, Modular composition, Multi-point evaluation, Power projection",

author = "\{van der Hoeven\}, Joris and Gr{\'e}goire Lecerf",

note = "Publisher Copyright: {\textcopyright} 2019",

year = "2020",

month = feb,

day = "1",

doi = "10.1016/j.jco.2019.04.001",

language = "English",

volume = "56",

journal = "Journal of Complexity",

issn = "0885-064X",

}

TY - JOUR

T1 - Fast multivariate multi-point evaluation revisited

AU - van der Hoeven, Joris

AU - Lecerf, Grégoire

PY - 2020/2/1

Y1 - 2020/2/1

N2 - 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.

AB - 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.

KW - Algorithm

KW - Complexity bound

KW - Kedlaya–Umans algorithm

KW - Modular composition

KW - Multi-point evaluation

KW - Power projection

U2 - 10.1016/j.jco.2019.04.001

DO - 10.1016/j.jco.2019.04.001

M3 - Article

AN - SCOPUS:85068829133

SN - 0885-064X

VL - 56

JO - Journal of Complexity

JF - Journal of Complexity

M1 - 101405

ER -

Fast multivariate multi-point evaluation revisited

Abstract

Keywords

Access to Document

Fingerprint

Cite this