On the Minimal Polynomial of the Product of Linear Recurring Sequences

The determination of the minimal polynomial, and thus of the linear complexity, of the product of two linear recurring sequences is a basic problem in the theory of stream ciphers in cryptology. We establish results on the minimal polynomial of such a product which yield, in particular, a general lower bound on the linear complexity of the product sequence. The problem is mainly of interest for finite fields, but our methods work for arbitrary fields.