Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

Stein, Greg

doi:10.1090/S0025-5718-00-01233-3

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