|
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.
References
- 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
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 after
28 years from publication.
|
