Character sums and deterministic polynomial root finding in finite fields

Bourgain, Jean; Konyagin, Sergei; Shparlinski, Igor

doi:10.1090/mcom/2946

Character sums and deterministic polynomial root finding in finite fields
HTML articles powered by AMS MathViewer

by Jean Bourgain, Sergei V. Konyagin and Igor E. Shparlinski PDF

Math. Comp. 84 (2015), 2969-2977 Request permission

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

E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X
Daniel J. Bernstein, Factoring into coprimes in essentially linear time, J. Algorithms 54 (2005), no. 1, 1–30. MR 2108417, DOI 10.1016/j.jalgor.2004.04.009
Jean Bourgain, Sum-product theorems and applications, Additive number theory, Springer, New York, 2010, pp. 9–38. MR 2744741, DOI 10.1007/978-0-387-68361-4_{2}
Jean Bourgain, Moubariz Z. Garaev, Sergei V. Konyagin, and Igor E. Shparlinski, On the hidden shifted power problem, SIAM J. Comput. 41 (2012), no. 6, 1524–1557. MR 3023803, DOI 10.1137/110850414
D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 93504, DOI 10.1112/S0025579300001157
D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179–192. MR 132732, DOI 10.1112/plms/s3-12.1.179
Mei-Chu Chang, On a question of Davenport and Lewis and new character sum bounds in finite fields, Duke Math. J. 145 (2008), no. 3, 409–442. MR 2462111, DOI 10.1215/00127094-2008-056
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 3rd ed., Cambridge University Press, Cambridge, 2013. MR 3087522, DOI 10.1017/CBO9781139856065
Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214, DOI 10.1090/coll/053
Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
Kiran S. Kedlaya and Christopher Umans, Fast polynomial factorization and modular composition, SIAM J. Comput. 40 (2011), no. 6, 1767–1802. MR 2863194, DOI 10.1137/08073408X
Hugh L. Montgomery, Ten lectures on the interface between analytic number theory and harmonic analysis, CBMS Regional Conference Series in Mathematics, vol. 84, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1994. MR 1297543, DOI 10.1090/cbms/084
X. Shao, Character sums over unions of intervals, Forum Math., (to appear).
Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276, DOI 10.1016/0020-0190(90)90195-4
Igor E. Shparlinski, Finite fields: theory and computation, Mathematics and its Applications, vol. 477, Kluwer Academic Publishers, Dordrecht, 1999. The meeting point of number theory, computer science, coding theory and cryptography. MR 1745660, DOI 10.1007/978-94-015-9239-0
Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501–538. MR 2728992, DOI 10.1090/S0025-5718-2010-02373-7
Andrew V. Sutherland, Accelerating the CM method, LMS J. Comput. Math. 15 (2012), 172–204. MR 2970725, DOI 10.1112/S1461157012001015