New results on the minimal polynomials of modified de Bruijn sequences

Modified de Bruijn sequences are generated by removing a single zero from the longest run of zeros of de Bruijn sequences. It is known that the minimal polynomial of a modified de Bruijn sequence of order n at least has an irreducible factor of degree n. Based on this observation, we give some new results on the minimal polynomial of a modified de Bruijn sequence in this paper. First, it is shown that the minimal polynomial of a modified de Bruijn sequence of order n cannot be the product of an irreducible polynomial of degree n and the irreducible polynomial of degree 2. Second, it is proved that the minimal polynomial of a modified de Bruijn sequence of order n cannot be the product of an irreducible polynomial of degree n and a primitive polynomial of degree k with n >= 8k. This is a generalization of the main result in the paper Kyureghyan (2008) [3] which only considered products of two primitive polynomials. Third, it is proved that the minimal polynomial of a modified de Bruijn sequence of order n cannot be a product of an irreducible polynomial f (x) of degree n and a polynomial of order t dividing 2(k) - 1 with gcd(ord(f (x)), t) = 1 and n >= 4k. As an application, for the cases n = 2p(e) and n = p1.p2 where p, P1, P2 are prime numbers and 2(Pi) - 1 is also a prime number for i = 1,2, a non-trivial lower bound is given for the linear complexity of a modified de Bruijn sequence of order n distinct from m-sequences, which could not be proved by the previous techniques. (C) 2019 Elsevier Inc. All rights reserved.