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
Liste complète des métadonnées

https://hal.inria.fr/hal-00922224
Contributor : Phong Q. Nguyen <>
Submitted on : Wednesday, December 25, 2013 - 9:29:54 AM
Last modification on : Thursday, April 11, 2019 - 2:34:03 PM

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

474