Products of linear recurring sequences with maximum complexity

Abstract

Conditions are derived which guarantee that products of linear recurring sequences attain maximum linear complexity. It is shown that the product of any number of maximum-length GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(q)</tex> sequences has maximum linear complexity, provided only the degrees of the corresponding minimal polynomials are distinct and greater than two. It is also shown that if the roots of any number of (not necessarily irreducible) minimal polynomials are simple and lie in extension fields of pairwise relatively prime degrees, then the product of the corresponding GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(q)</tex> sequences attains maximum linear complexity, provided only that no two roots of any minimal polynomial are linearly dependent over the groundfield GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(q)</tex> (which is automatically satisfied when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q = 2)</tex> . The results obtained for products are extended to arbitrary linear combinations of product sequences.