On Rueppel's Linear Complexity Conjecture

2023/04/30 by Graham H. Norton, Norton, Graham H.
Computer Science · Engineering · #Coding theory and cryptography #FOS: Computer and information sciences #Symbolic Computation (cs.SC) #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2305.00405

openalex publication_date 2023/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Rueppel's conjecture on the linear complexity of the first n terms of the sequence (1,1,0,1,0³,1,0⁷,1,0¹⁵,…) was first proved by Dai using the Euclidean algorithm. We have previously shown that we can attach a homogeneous (annihilator) ideal of F[x,z] to the first n terms of a sequence over a field F and construct a pair of generating forms for it. This approach gives another proof of Rueppel's conjecture. We also prove additional properties of these forms and deduce the outputs of the LFSR synthesis algorithm applied to the first n terms. Further, dehomogenising the leading generators yields the minimal polynomials of Dai.

Related

• On Sequences with a Perfect Linear Complexity Profile
• Word Linear Complexity of sequences and Local Inversion of maps over finite fields
• Padded polynomials, their cousins, and geometric complexity theory
• Polynomial Complexity of Inversion of sequences and Local Inversion of Maps
• A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture