Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

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
DOI: https://doi.org/10.1090/mcom/2946
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
Email: bourgain@ias.edu

Sergei V. Konyagin
Affiliation: Steklov Mathematical Institute, 8, Gubkin Street, Moscow, 119991, Russia
Email: konyagin@mi.ras.ru

Igor E. Shparlinski
Affiliation: Department of Pure Mathematics, University of New South Wales, Sydney, NSW 2052, Australia
Email: igor.shparlinski@unsw.edu.au

DOI: https://doi.org/10.1090/mcom/2946
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