Function Field and Number Field Generalizations of Linear Feedback Shift Registers
Linear feedback shift registers are very fast generators of statistically random sequences. They are used in a vast array of applications, including cryptographic stream ciphers, error correcting codes, code division multiple access, radar ranging, and quasi-Monte Carlo integration. From a mathematical point of view, they are based on the algebra of polynomials and power series over finite fields. In recent years we have generalized this construction to build sequence generators based first on the algebra of N-adic numbers (the case N = 2 has been used in random number generators for quasi-Monte Carlo and as building blocks for stream ciphers), and more recently on more general completions of algebraic rings. The resulting generators are called algebraic feedback shift registers (AFSRs). In this talk we will review the basic definitions and properties of algebraic feedback shift registers. We will then examine the case when the underlying ring is an function field in some detail. In particular we will see how these sequence generators relate to an old conjecture of Golomb's. If time permits, we will touch on various other topics concerning AFSRs.