Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields
HTML articles powered by AMS MathViewer
- by Greg Stein PDF
- Math. Comp. 70 (2001), 1237-1251 Request permission
Abstract:
We examine the problem of factoring the $r$th cyclotomic polynomial, $\Phi _r(x),$ over $\mathbb {F}_p$, $r$ and $p$ distinct primes. Given the traces of the roots of $\Phi _r(x)$ we construct the coefficients of $\Phi _r(x)$ in time $O(r^4)$. We demonstrate a deterministic algorithm for factoring $\Phi _r(x)$ in time $O((r^{1/2+\epsilon }\log p)^9)$ when $\Phi _r(x)$ has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of $\Phi _r(x)$ in time $O(r^6)$.References
- L. D. Baumert, W. H. Mills, and Robert L. Ward, Uniform cyclotomy, J. Number Theory 14 (1982), no. 1, 67–82. MR 644901, DOI 10.1016/0022-314X(82)90058-0
- Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1625181
- Dario Bini and Victor Y. Pan, Polynomial and matrix computations. Vol. 1, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1994. Fundamental algorithms. MR 1289412, DOI 10.1007/978-1-4612-0265-3
- David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
- 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
- L.E. Dickson, Cyclotomy, higher congruences, and Waring’s problem, Amer. J. Math., [57], (1935), pp. 391-424.
- S. A. Evdokimov, Factorization of a solvable polynomial over finite fields and the generalized Riemann hypothesis, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 176 (1989), no. Teor. Slozhn. Vychisl. 4, 104–117, 153 (Russian, with English summary); English transl., J. Soviet Math. 59 (1992), no. 3, 842–849. MR 1023599, DOI 10.1007/BF01104107
- Carl Friedrich Gauss, Disquisitiones arithmeticae, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. MR 837656
- Ming-Deh A. Huang, Generalized Riemann hypothesis and factoring polynomials over finite fields, J. Algorithms 12 (1991), no. 3, 464–481. MR 1114921, DOI 10.1016/0196-6774(91)90014-P
- Dieter Jungnickel, Finite fields, Bibliographisches Institut, Mannheim, 1993. Structure and arithmetics. MR 1238714
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
- Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, 1st ed., Cambridge University Press, Cambridge, 1994. MR 1294139, DOI 10.1017/CBO9781139172769
- Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- G. B. Mathews, Theory of numbers, Chelsea Publishing Co., New York, 1961. 2nd ed. MR 0126402
- Gerald Myerson, Period polynomials and Gauss sums for finite fields, Acta Arith. 39 (1981), no. 3, 251–264. MR 640913, DOI 10.4064/aa-39-3-251-264
- Harald Niederreiter and Rainer Göttfert, On a new factorization algorithm for polynomials over finite fields, Math. Comp. 64 (1995), no. 209, 347–353. MR 1265019, DOI 10.1090/S0025-5718-1995-1265019-6
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
- 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
- Greg Stein, Factoring cyclotomic polynomials over large finite fields, Finite fields and applications (Glasgow, 1995) London Math. Soc. Lecture Note Ser., vol. 233, Cambridge Univ. Press, Cambridge, 1996, pp. 349–354. MR 1433158, DOI 10.1017/CBO9780511525988.026
- Greg Stein, Traces of roots of unity over prime fields, Finite fields: theory, applications, and algorithms (Waterloo, ON, 1997) Contemp. Math., vol. 225, Amer. Math. Soc., Providence, RI, 1999, pp. 113–121. MR 1650596, DOI 10.1090/conm/225/03213
- Thomas Storer, Cyclotomy and difference sets, Lectures in Advanced Mathematics, No. 2, Markham Publishing Co., Chicago, Ill., 1967. MR 0217033
Additional Information
- Greg Stein
- Affiliation: The City University of New York, 300 Jay Street, Brooklyn, New York 11201
- Email: gregstein@member.ams.org
- Received by editor(s): December 1, 1998
- Received by editor(s) in revised form: June 22, 1999
- Published electronically: March 24, 2000
- Additional Notes: Supported in part by PSC-CUNY Research Foundation Grant 69666-00 29
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp. 70 (2001), 1237-1251
- MSC (2000): Primary 11T06, 11T24, 11T22; Secondary 12Y05, 13P05
- DOI: https://doi.org/10.1090/S0025-5718-00-01233-3
- MathSciNet review: 1709159