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

Jingguo Bi 1, 2, * Qi Cheng 3 Maurice Rojas 4
* Auteur correspondant
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
Type de document :
Communication dans un congrès
Michael B. Monagan and Gene Cooperman and Mark Giesbrecht. ISSAC '13 - 38th international symposium on International symposium on symbolic and algebraic computation, Jun 2013, Boston, United States. ACM, pp.61-68, 2013, International Symposium on Symbolic and Algebraic Computation, ISSAC'13, Boston, MA, USA, June 26-29, 2013. 〈10.1145/2465506.2465514〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00922224
Contributeur : Phong Q. Nguyen <>
Soumis le : mercredi 25 décembre 2013 - 09:29:54
Dernière modification le : mardi 17 avril 2018 - 11:29:23

Lien texte intégral

Identifiants

Collections

Citation

Jingguo Bi, Qi Cheng, Maurice Rojas. Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields. Michael B. Monagan and Gene Cooperman and Mark Giesbrecht. ISSAC '13 - 38th international symposium on International symposium on symbolic and algebraic computation, Jun 2013, Boston, United States. ACM, pp.61-68, 2013, International Symposium on Symbolic and Algebraic Computation, ISSAC'13, Boston, MA, USA, June 26-29, 2013. 〈10.1145/2465506.2465514〉. 〈hal-00922224〉

Partager

Métriques

Consultations de la notice

284