Constructing irreducible polynomials over finite fields
HTML articles powered by AMS MathViewer
- by San Ling, Enver Ozdemir and Chaoping Xing PDF
- Math. Comp. 81 (2012), 1663-1668 Request permission
Abstract:
We describe a new method for constructing irreducible polynomials modulo a prime number $p$. The method mainly relies on Chebotarev’s density theorem.References
- L. Adleman and H. Lenstra, Finding irreducible polynomials over finite fields, Proc. 18th Annual ACM Symp. on Theory of Computing, 350-355.
- J. W. S. Cassels and A. Fröhlich (eds.), Algebraic number theory, Academic Press, London; Thompson Book Co., Inc., Washington, D.C., 1967. MR 0215665
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- H. Cohen and H. W. Lenstra Jr., Heuristics on class groups of number fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983) Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33–62. MR 756082, DOI 10.1007/BFb0099440
- David A. Cox, Primes of the form $x^2 + ny^2$, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR 1028322
- Andreas Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572, DOI 10.1090/S0025-5718-08-02200-X
- James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
- L. S. Heath, N. A. Comman, New algorithms for generating Conway polynomials over finite fields, SODA 99, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms.
- 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
- H. Lenstra, The Chebotarev Density Theorem, Algebra Lecture Notes: http://websites.math.leidenuniv.nl/algebra/Lenstra-Chebotarev.pdf
- Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
- Victor Shoup, New algorithms for finding irreducible polynomials over finite fields, Math. Comp. 54 (1990), no. 189, 435–447. MR 993933, DOI 10.1090/S0025-5718-1990-0993933-0
- Lawrence C. Washington, Elliptic curves, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. Number theory and cryptography. MR 2404461, DOI 10.1201/9781420071474
- William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 265369
- Mark Watkins, Class numbers of imaginary quadratic fields, Math. Comp. 73 (2004), no. 246, 907–938. MR 2031415, DOI 10.1090/S0025-5718-03-01517-5
Additional Information
- San Ling
- Affiliation: Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore
- Email: lingsan@ntu.edu.sg
- Enver Ozdemir
- Affiliation: Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore
- Email: eozdemir@ntu.edu.sg
- Chaoping Xing
- Affiliation: Division of Mathematical Sciences, School of Physical & Mathematical Sciences, Nanyang Technological University, Singapore
- MR Author ID: 264368
- Email: xingcp@ntu.edu.sg
- Received by editor(s): March 5, 2011
- Received by editor(s) in revised form: April 11, 2011
- Published electronically: November 15, 2011
- Additional Notes: The research was partially supported by the Singapore National Research Foundation Competitive Research Program grant NRF-CRP2-2007-03 and the Singapore Ministry of Education under Research Grant T208B2206.
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 81 (2012), 1663-1668
- MSC (2010): Primary 11Y99, 11T06, 11R11, 11Y11
- DOI: https://doi.org/10.1090/S0025-5718-2011-02567-6
- MathSciNet review: 2904596