Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2013

Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields

Abstract

We present a deterministic 2O(t)qt-2/t-1 +o(1) algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree

Dates and versions

hal-00922224 , version 1 (25-12-2013)

Identifiers

Cite

Jingguo Bi, Qi Cheng, Maurice Rojas. Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields. ISSAC '13 - 38th international symposium on International symposium on symbolic and algebraic computation, ACM, Jun 2013, Boston, United States. pp.61-68, ⟨10.1145/2465506.2465514⟩. ⟨hal-00922224⟩
380 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More