Character sums and deterministic polynomial root finding in finite fields
- 10 April 2015
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 84 (296) , 2969-2977
Abstract
We obtain a new bound of certain double multiplicative character sums. We use this bound together with some other previously obtained results to obtain new algorithms for finding roots of polynomials modulo a prime p p .Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Accelerating the CM methodLMS Journal of Computation and Mathematics, 2012
- On the Hidden Shifted Power ProblemSIAM Journal on Computing, 2012
- Fast Polynomial Factorization and Modular CompositionSIAM Journal on Computing, 2011
- On a question of Davenport and Lewis and new character sum bounds in finite fieldsDuke Mathematical Journal, 2008
- Factoring into coprimes in essentially linear timeJournal of Algorithms, 2005
- Subquadratic-time factoring of polynomials over finite fieldsMathematics of Computation, 1998
- Computing Frobenius maps and factoring polynomialscomputational complexity, 1992
- On the deterministic complexity of factoring polynomials over finite fieldsInformation Processing Letters, 1990
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970
- The distribution of quadratic residues and non‐residuesMathematika, 1957