Details:
Title  Yet another practical implementation of polynomial factorization over finite fields  Author(s)  Masayuki Noro, Kazuhiro Yokoyama  Type  Article in Conference Proceedings  Abstract  Polynomial factorization plays a significant role in computational mathematics and its application to engineering, since it forms a fundamental part of algorithms for higher algebraic computations. Multivariate polynomial factorization over finite fields is very important for computations of mathematical object over positive characteristic fields, which will help mathematical studies in various area. For example, primary ideal decomposition over finite fields is very useful for study of pure mathematics (algebraic geometry over positive characteristic fields) and also for study of coding theory (design of algebraic geometric codes). To make primary decomposition efficient, practical method of multivariate polynomial factorization and its implementation are essential. (This is the authors' motivation for this study. )Since, multivariate factorization over finite fields can be reduced efficiently to bivariate factorization, we focus on bivariate factorization over small finite fields here, and we propose a practically efficient combination of two methods: one is the wellknown method by trial division and the other is a new polynomialtime method.As to polynomial factorization, many of computer algebra systems employ trialdivision type algorithms which are non polynomialtime but efficient in many cases. However, as polynomialtime algorithms work well in the worst cases, good combination with practical algorithms should be very useful to improve the performance of the computer algebra system, provided that we have their practical implementation and we know their good usages. Moreover, if we can incorporate those with certain knowledge on the input, (we may call these heuristics), their practicality shall be much improved. In this paper we propose a polynomialtime algorithm for bivariate factorization over finite fields, which can be implemented efficiently and in which some heuristics can be incorporated. The new algorithm is obtained by reviewing existing algorithms from the ideal theoretical point of view, and based on the change of ordering algorithm of zerodimensional Gröbner basis [6, 17].As to practical implementation of bivariate factorization, finding evaluation points and Hensel lifting are very important. When we factorize a polynomial over a small finite field, we often have to extend the ground field because of shortage of evaluation points. However, if the extension field is small enough, a primitive root representation of the field can reduce the cost of field operations over the extension field. Under this situation we implement Hensel lifting and trial division, and we examine its performance by various benchmark problems. We also implement the new polynomialtime algorithm and we show its advantage for hardtofactor polynomials.  ISBN  1581134843 
URL 
http://doi.acm.org/10.1145/780506.780532 
Language  English  Pages  200206  Publisher  ACM Press  Address  New York, NY, USA  Year  2002  Translation 
No  Refereed 
No  Conferencename  International Symposium on Symbolic and Algebraic Computation 
