Constructing irreducible polynomials over finite fields

Ling, San; Ozdemir, Enver; Xing, Chaoping

doi:10.1090/S0025-5718-2011-02567-6

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