DocumentCode :
1414299
Title :
Factoring polynomials using binary representations of finite fields
Author :
Ganz, Jürg
Author_Institution :
Union Bank of Switzerland, Zurich, Switzerland
Volume :
43
Issue :
1
fYear :
1997
fDate :
1/1/1997 12:00:00 AM
Firstpage :
147
Lastpage :
153
Abstract :
The factorization of polynomials over finite fields is considered. A new deterministic algorithm is proposed that solves the equal-degree factorization problem by combining Berlekamp´s (1970) trace algorithm iterative method with the concept of binary representations of finite fields. The interesting aspects of the new algorithm are its simple structure, the easy proof of its correctness, and its efficiency when an efficient realization of the mapping from the finite field to a binary representation is known. Some results about binary representations of finite fields are derived to show that the new factoring algorithm is also nonasymptotically efficient for every finite field. The only practical drawback may be the precomputation of some constants needed in the binary representation, but several suggestions are given to improve this when more about the finite field is known
Keywords :
deterministic algorithms; iterative methods; polynomials; binary representations; constants; deterministic algorithm; efficiency; equal-degree factorization problem; finite fields; mapping; nonasymptotically efficient algorithm; precomputation; trace algorithm; Concrete; Galois fields; Information processing; Polynomials; Signal processing;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/18.567667
Filename :
567667
Link To Document :
بازگشت