Character sums and deterministic polynomial root finding in finite fields

Jean Bourgain; Sergei V. Konyagin; Igor E. Shparlinski

doi:10.1090/mcom/2946

Character sums and deterministic polynomial root finding in finite fields

Jean Bourgain, Sergei V. Konyagin, Igor E. Shparlinski

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

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.

Original language	English
Pages (from-to)	2969-2977
Number of pages	9
Journal	Mathematics of Computation
Volume	84
Issue number	296
DOIs	https://doi.org/10.1090/mcom/2946
Publication status	Published - 2015
Externally published	Yes

Keywords

Character sums
Finite field
Multiplicative energy
Root finding

Access to Document

10.1090/mcom/2946

Cite this

@article{fe312063e3b5416ba92fc63c0af52439,

title = "Character sums and deterministic polynomial root finding in finite fields",

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.",

keywords = "Character sums, Finite field, Multiplicative energy, Root finding",

author = "Jean Bourgain and Konyagin, {Sergei V.} and Shparlinski, {Igor E.}",

year = "2015",

doi = "10.1090/mcom/2946",

language = "English",

volume = "84",

pages = "2969--2977",

journal = "Mathematics of Computation",

issn = "0025-5718",

publisher = "American Mathematical Society",

number = "296",

}

TY - JOUR

T1 - Character sums and deterministic polynomial root finding in finite fields

AU - Bourgain, Jean

AU - Konyagin, Sergei V.

AU - Shparlinski, Igor E.

PY - 2015

Y1 - 2015

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

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

KW - Character sums

KW - Finite field

KW - Multiplicative energy

KW - Root finding

UR - http://www.scopus.com/inward/record.url?scp=85000774349&partnerID=8YFLogxK

U2 - 10.1090/mcom/2946

DO - 10.1090/mcom/2946

M3 - Article

AN - SCOPUS:85000774349

SN - 0025-5718

VL - 84

SP - 2969

EP - 2977

JO - Mathematics of Computation

JF - Mathematics of Computation

IS - 296

ER -

Character sums and deterministic polynomial root finding in finite fields

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this