|
Constructing irreducible polynomials over finite fields
Authors:
San Ling, Enver Ozdemir and Chaoping Xing
Journal:
Math. Comp. 81 (2012), 1663-1668
MSC (2010):
Primary 11Y99, 11T06, 11R11, 11Y11
Posted:
November 15, 2011
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We describe a new method for constructing irreducible polynomials modulo a prime number  . The method mainly relies on Chebotarev's density theorem.
- 1.
L. Adleman and H. Lenstra, Finding irreducible polynomials over finite fields, Proc. 18th Annual ACM Symp. on Theory of Computing, 350-355.
- 2.
Algebraic number theory, Proceedings of an instructional
conference organized by the London Mathematical Society (a NATO Advanced
Study Institute) with the support of the Inter national Mathematical Union.
Edited by J. W. S. Cassels and A. Fröhlich, Academic Press, London,
1967. MR
0215665 (35 #6500)
- 3.
Henri
Cohen, A course in computational algebraic number theory,
Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin,
1993. MR
1228206 (94i:11105)
- 4.
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
(85j:11144), http://dx.doi.org/10.1007/BFb0099440
- 5.
David
A. Cox, Primes of the form
𝑥²+𝑛𝑦², A Wiley-Interscience
Publication, John Wiley & Sons Inc., New York, 1989. Fermat, class
field theory and complex multiplication. MR 1028322
(90m:11016)
- 6.
Andreas
Enge, The complexity of class polynomial
computation via floating point approximations, Math. Comp. 78 (2009), no. 266, 1089–1107. MR 2476572
(2010h:11097), http://dx.doi.org/10.1090/S0025-5718-08-02200-X
- 7.
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
(91f:11090), http://dx.doi.org/10.1090/S0894-0347-1989-1002631-0
- 8.
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.
- 9.
Erich
Kaltofen and Victor
Shoup, Subquadratic-time factoring of
polynomials over finite fields, Math. Comp.
67 (1998), no. 223, 1179–1197. MR 1459389
(99m:68097), http://dx.doi.org/10.1090/S0025-5718-98-00944-2
- 10.
H. Lenstra, The Chebotarev Density Theorem, Algebra Lecture Notes: http://websites.math.leidenuniv.nl/algebra/Lenstra-Chebotarev.pdf
- 11.
Michael
O. Rabin, Probabilistic algorithms in finite fields, SIAM J.
Comput. 9 (1980), no. 2, 273–280. MR 568814
(81g:12002), http://dx.doi.org/10.1137/0209024
- 12.
Victor
Shoup, New algorithms for finding irreducible
polynomials over finite fields, Math. Comp.
54 (1990), no. 189, 435–447. MR 993933
(90j:11135), http://dx.doi.org/10.1090/S0025-5718-1990-0993933-0
- 13.
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
(2009b:11101)
- 14.
William
C. Waterhouse, Abelian varieties over finite fields, Ann. Sci.
École Norm. Sup. (4) 2 (1969), 521–560. MR 0265369
(42 #279)
- 15.
Mark
Watkins, Class numbers of imaginary quadratic
fields, Math. Comp. 73
(2004), no. 246, 907–938
(electronic). MR
2031415 (2005a:11175), http://dx.doi.org/10.1090/S0025-5718-03-01517-5
- 1.
- L. Adleman and H. Lenstra, Finding irreducible polynomials over finite fields, Proc. 18th Annual ACM Symp. on Theory of Computing, 350-355.
- 2.
- J. W. S. Casseles and A. Fröhlich, Algebraic Number Theory, Academic Press, London and New York, 1967. MR 0215665 (35:6500)
- 3.
- H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 2000. MR 1228206 (94i:11105)
- 4.
- H. Cohen, H. W. Lenstra , Heuristics on class groups of number fields, Number Theory, Noordwijkerhout 1983, Lecture Notes in Math. 1068, Springer-Verlag, 1984, 33-62. MR 756082 (85j:11144)
- 5.
- David A. Cox, Primes of the form
 - Fermat, class field theory, and complex multiplication, John Wiley & Sons, New York, 1989. MR 1028322 (90m:11016)
- 6.
- Andreas Enge, The complexity of class polynomial computation via floating point approximations. Mathematics of Computation 78 (266), 2009, pp. 1089-1107. MR 2476572 (2010h:11097)
- 7.
- J. Hafner and K. McCurley, A rigorous subexponential algorithm for computation of class groups, Journal of American Math. Soc. 2 (1989), 837-850. MR 1002631 (91f:11090)
- 8.
- 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.
- 9.
- E. Kaltofen, V. Shoup, Subquadratic-time factoring of polynomials over finite fields. Math. Comput., 67(223):1179-1197, 1998. MR 1459389 (99m:68097)
- 10.
- H. Lenstra, The Chebotarev Density Theorem, Algebra Lecture Notes: http://websites.math.leidenuniv.nl/algebra/Lenstra-Chebotarev.pdf
- 11.
- Rabin, M., Probabilistic algorithms in finite fields, SIAM Journal of Computing, vol. 9, no. 2, 273-280. MR 568814 (81g:12002)
- 12.
- V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Mathematics of Computation 54:435-447, 1990. MR 993933 (90j:11135)
- 13.
- L. C. Washington, Elliptic Curves: Number Theory and Cryptography, 2nd edition. Chapman & Hall/CRC 2008. MR 2404461 (2009b:11101)
- 14.
- W. W. Waterhouse, Abelian varieties over finite fields, Ann. Scient. Ec. Norm. Sup., (4), 1969, 521-560. MR 0265369 (42:279)
- 15.
- M. Watkins, Class numbers of imaginary quadratic fields, Mathematics of Computation, Volume 73, Number 246, 907-938. MR 2031415 (2005a:11175)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2010):
11Y99,
11T06,
11R11,
11Y11
Retrieve articles in all journals
with MSC (2010):
11Y99,
11T06,
11R11,
11Y11
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
Email:
xingcp@ntu.edu.sg
DOI:
http://dx.doi.org/10.1090/S0025-5718-2011-02567-6
PII:
S 0025-5718(2011)02567-6
Keywords:
Finite fields,
Hilbert class polynomials
Received by editor(s):
March 5, 2011
Received by editor(s) in revised form:
April 11, 2011
Posted:
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.
Article copyright:
© Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
|
