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
Additional Information
- Jean Bourgain
- Affiliation: Institute for Advanced Study, Princeton, New Jersey 08540
- MR Author ID: 40280
- Email: bourgain@ias.edu
- Sergei V. Konyagin
- Affiliation: Steklov Mathematical Institute, 8, Gubkin Street, Moscow, 119991, Russia
- MR Author ID: 188475
- Email: konyagin@mi.ras.ru
- Igor E. Shparlinski
- Affiliation: Department of Pure Mathematics, University of New South Wales, Sydney, NSW 2052, Australia
- MR Author ID: 192194
- Email: igor.shparlinski@unsw.edu.au
- Received by editor(s): September 10, 2013
- Received by editor(s) in revised form: March 9, 2014
- Published electronically: April 10, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 84 (2015), 2969-2977
- MSC (2010): Primary 11L40, 11T06, 11Y16, 68Q25
- DOI: https://doi.org/10.1090/mcom/2946
- MathSciNet review: 3378857