ISSN:
1432-0622
Keywords:
Factorization of polynomials over finite fields
;
Differential equations over rational function fields
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract We present a new deterministic factorization algorithm for polynomials over a finite prime fieldF p . As in other factorization algorithms for polynomials over finite fields such as the Berlekamp algorithm, the key step is the “linearization” of the factorization problem, i.e., the reduction of the problem to a system of linear equations. The theoretical justification for our algorithm is based on a study of the differential equationy (p −1)+y p =0 of orderp−1 in the rational function fieldF p(x). In the casep=2 the new algorithm is more efficient than the Berlekamp algorithm since there is no set-up cost for the coefficient matrix of the system of linear equations.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01386831
Permalink