Skip to Main content Skip to Navigation
Conference papers

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

Jingguo Bi 1, 2, * Qi Cheng 3 Maurice Rojas 4 
* Corresponding author
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
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
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-00922224
Contributor : Phong Q. Nguyen Connect in order to contact the contributor
Submitted on : Wednesday, December 25, 2013 - 9:29:54 AM
Last modification on : Friday, January 21, 2022 - 3:15:30 AM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

372