A Lanczos Algorithm in a Finite Field and its Application

Given a matrix in companion form over \(GF(2)\), whose characteristic polynomial is irreducible, a tridiagonal matrix, similar to the original one, is found, by constructing the similarity transformation. The theoretical basis is founded on the Lanczos tridiagonalization method, valid in the Complex domain. A variant of the Lanczos method, based on LU decomposition requirements, is modified to apply in the finite field \(GF(2)\). The work is derived from an application in VLSI design, where the matrices in companion form and in tridiagonal form represent two similar linear finite state machines, used for pseudo-random pattern generation and digital circuit testing. The construction of the similarity transformation between the matrices makes it possible to obtain directly the separate implementation of the two corresponding machines.