On Linear Complexity of Finite Sequences : Coding Theory and Applications to Cryptography

ePrint Report: On Linear Complexity of Finite Sequences : Coding Theory and Applications to Cryptography

Edoardo Persichetti, Tovohery Randrianarisoa

We define two metrics on vector spaces over a finite field using the linear complexity of finite sequences. We then develop coding theory notions for these metrics and study their properties. We give a Singleton-like bound as well as constructions of subspaces achieving this bound. We also provide an asymptotic Gilbert-Varshamov-like bound for random subspaces. We show how to reduce the …

applications coding complexity cryptography eprint report theory