Factoring polynomials over finite fields with Drinfeld modules

van der Heiden, G.

doi:10.1090/S0025-5718-03-01598-9

Factoring polynomials over finite fields with Drinfeld modules
HTML articles powered by AMS MathViewer

by G. J. van der Heiden;

Math. Comp. 73 (2004), 317-322

DOI: https://doi.org/10.1090/S0025-5718-03-01598-9

Published electronically: August 7, 2003

PDF | Request permission

Addendum: Math. Comp. 73 (2004), 2109-2109.

Abstract:

In the following, we describe a way of factoring polynomials in $\mathbb {F}_q[X]$ with Drinfeld modules. We furthermore analyse the complexity of the algorithm and compare it to the well-known Cantor-Zassenhaus algorithm.

References

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
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
Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
B. Heinrich Matzat, Introduction to Drinfeld modules, Drinfeld modules, modular schemes and applications (Alden-Biesen, 1996) World Sci. Publ., River Edge, NJ, 1997, pp. 3–16. MR 1630595
Irving Reiner, On the number of matrices with given characteristic polynomial, Illinois J. Math. 5 (1961), 324–329. MR 139621