Character sums and deterministic polynomial root finding in finite fields

DOI10.1090/mcom/2946zbMath1400.11153arXiv1308.4803OpenAlexW2964020107WikidataQ101166315 ScholiaQ101166315MaRDI QIDQ5501155

Sergei V. Konyagin, Jean Bourgain, 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

finite fieldcharacter sumsroot findingmultiplicative energy

Mathematics Subject Classification ID

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

Related Items (10)

Congruences with intervals and arbitrary sets ⋮ Homomorphic polynomial public key encapsulation over two hidden rings for quantum-safe key encapsulation ⋮ Integer sampling matrices with small entries ensuring vector recovery ⋮ Algebraic algorithms for variants of subset sum ⋮ Sergei Vladimirovich Konyagin turns 60 ⋮ Double character sums with intervals and arbitrary sets ⋮ Recovery of sparse integer vectors from linear measurements ⋮ Deterministic polynomial factoring over finite fields: a uniform approach via \(\mathcal{P}\)-schemes ⋮ Unnamed Item ⋮ Supersingular j-invariants and the class number of ℚ(−p)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Character sums over unions of intervals
• On the deterministic complexity of factoring polynomials over finite fields
• On a question of Davenport and Lewis and new character sum bounds in finite fields
• Computing Frobenius maps and factoring polynomials
• Modern Computer Algebra
• Sum-Product Theorems and Applications
• Computing Hilbert class polynomials with the Chinese remainder theorem
• Fast Polynomial Factorization and Modular Composition
• The distribution of quadratic residues and non‐residues
• On Character Sums and Primitive Roots^†
• Subquadratic-time factoring of polynomials over finite fields
• Factoring into coprimes in essentially linear time
• On the Hidden Shifted Power Problem
• Accelerating the CM method
• Factoring Polynomials Over Large Finite Fields

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