Linear feedback shift registers are the most commonly used mechanism in built-in test architectures for digital combinational or fully scanned circuits and systems. The goal in pseudo-exhaustive TPG is to minimize the required test length with low hardware overhead. Existing approaches are based on primitive characteristic polynomials. The hardware overhead (seeds) is minimal in this case, but the candidate polynomials are few. Our experiments show that these methods often fail to produce pseudoexhaustive tests. There are no approaches that allow a small number of seeds in order to obtain pseudoexhaustive test sets within a prescribed bound. Our method allows consideration of still more candidate polynomials, that are not primitive, but offer a very small number of seeds. Experimental results on the ISCAS'85 benchmarks show that the method often succeeds with a very low number of seeds when all previous methods fail.