Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Character sums and deterministic polynomial root finding in finite fields

Authors: Jean Bourgain, Sergei V. Konyagin and Igor E. Shparlinski
Journal: Math. Comp. 84 (2015), 2969-2977
MSC (2010): Primary 11L40, 11T06, 11Y16, 68Q25
Published electronically: April 10, 2015
MathSciNet review: 3378857
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11L40, 11T06, 11Y16, 68Q25

Retrieve articles in all journals with MSC (2010): 11L40, 11T06, 11Y16, 68Q25

Additional Information

Jean Bourgain
Affiliation: Institute for Advanced Study, Princeton, New Jersey 08540

Sergei V. Konyagin
Affiliation: Steklov Mathematical Institute, 8, Gubkin Street, Moscow, 119991, Russia

Igor E. Shparlinski
Affiliation: Department of Pure Mathematics, University of New South Wales, Sydney, NSW 2052, Australia

Keywords: Finite field, root finding, character sums, multiplicative energy
Received by editor(s): September 10, 2013
Received by editor(s) in revised form: March 9, 2014
Published electronically: April 10, 2015
Article copyright: © Copyright 2015 American Mathematical Society