Character sums and deterministic polynomial root finding in finite fields

DOI10.1090/MCOM/2946MaRDI QIDQ5501155zbMATH OpenOpenAlexWikidataFDO

Authors Jean Bourgain, Sergei Konyagin, Igor E. Shparlinski

Publication date 13 August 2015

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.4803

zbMATH Keywords

character sumsfinite fieldmultiplicative energyroot finding

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Exponential sums (11T23) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

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

Recommendations

• Deterministic root finding in finite fields
• scientific article; zbMATH DE number 4065121
• Deterministic root finding over finite fields using Graeffe transforms
• Subgroup Refinement Algorithms for Root Finding in GF(q)
• A geometric approach to root finding in GT(q/sup m/)

Cites work

• Accelerating the CM method
• Character sums over unions of intervals
• Computing Frobenius maps and factoring polynomials
• Computing Hilbert class polynomials with the Chinese remainder theorem
• Factoring into coprimes in essentially linear time
• Factoring Polynomials Over Large Finite Fields
• Fast polynomial factorization and modular composition
• scientific article; zbMATH DE number 699709 (Why is no real title available?)
• scientific article; zbMATH DE number 1361739 (Why is no real title available?)
• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• Modern computer algebra
• On a question of Davenport and Lewis and new character sum bounds in finite fields
• On Character Sums and Primitive Roots^†
• On the deterministic complexity of factoring polynomials over finite fields
• On the hidden shifted power problem
• Subquadratic-time factoring of polynomials over finite fields
• Sum-Product Theorems and Applications
• The distribution of quadratic residues and non‐residues

Cited in

(13)

• Characterization and enumeration of good punctured polynomials over finite fields
• Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes
• Congruences with intervals and arbitrary sets
• Integer sampling matrices with small entries ensuring vector recovery
• Sergei Vladimirovich Konyagin turns 60
• Double character sums with intervals and arbitrary sets
• scientific article; zbMATH DE number 7559413 (Why is no real title available?)
• Recovery of sparse integer vectors from linear measurements
• Supersingular j-invariants and the class number of ℚ(−p)
• Homomorphic polynomial public key encapsulation over two hidden rings for quantum-safe key encapsulation
• Algebraic algorithms for variants of subset sum
• Estimates for trilinear and quadrilinear character sums
• On the distribution of quadratic residues

This page was built for publication: Character sums and deterministic polynomial root finding in finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501155)