A New Sparse Gaussian Elimination Algorithm and the Niederreiter Linear System for Trinomials over F
2 |
| |
Authors: | Fatima K Abu Salem |
| |
Affiliation: | (1) Computer Science Department, American University of Beirut, P. O. Box 11-0236, Riad El Solh, Beirut, 1107 2020, Lebanon |
| |
Abstract: | An important factorization algorithm for polynomials over finite fields was developed by Niederreiter. The factorization problem
is reduced to solving a linear system over the finite field in question, and the solutions are used to produce the complete
factorization of the polynomial into irreducibles. One charactersistic feature of the linear system arising in the Niederreiter
algorithm is the fact that, if the polynomial to be factorized is sparse, then so is the Niederreiter matrix associated with
it. In this paper, we investigate the special case of factoring trinomials over the binary field. We develop a new algorithm
for solving the linear system using sparse Gaussian elmination with the Markowitz ordering strategy. Implementing the new
algorithm to solve the Niederreiter linear system for trinomials over F2 suggests that, the system is not only initially sparse, but also preserves its sparsity throughout the Gaussian elimination
phase. When used with other methods for extracting the irreducible factors using a basis for the solution set, the resulting
algorithm provides a more memory efficient and sometimes faster sequential alternative for achieving high degree trinomial
factorizations over F2. |
| |
Keywords: | 11T06 15-04 68-04 68W05 68W30 68W40 |
本文献已被 SpringerLink 等数据库收录! |
|