Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleImproving the algorithms of Berlekamp and Niederreiter for factoring polynomials over finite fields
Author(s) Giulio Genovese
TypeArticle in Journal
AbstractA new deterministic algorithm for factoring polynomials over finite fields is presented. This algorithm makes use of linear algebra methods and is an improvement of the Berlekamp algorithm, as well as that of Niederreiter, in the case of nontrivial algebraic extensions. The improvement is achieved by a new method of computing a basis of the so-called Berlekamp primitive subalgebra that makes use of an idea related to the field of Gröbner bases. Finally, some comparative running times show how this new deterministic algorithm performs better than other probabilistic algorithms in some practical cases.
KeywordsDeterministic algorithms, Finite fields, Polynomial factorization, Berlekamp, Niederreiter
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717106000691
LanguageEnglish
JournalJournal of Symbolic Computation
Volume42
Number12
Pages159 - 177
Year2007
NoteEffective Methods in Algebraic Geometry (MEGA 2005)
Edition0
Translation No
Refereed No
Webmaster