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

Jingguo Bi (1, 2) , Qi Cheng (3) , Maurice Rojas (4)

1 Institute for Advanced Study [Tsinghua]
2 CRYPT - Cryptanalyse
3 Computer Science Department- University of Oklahoma
4 Departement of Mathematics

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

Domaines: Cryptographie et sécurité [cs.CR]

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⟩