### Randomness and Register Synthesis of Algebraic Feedback Shift
Registers Based on Function Fields

Appeared in: SETA '04, Seoul, Korea, 2004.
Authors:

Andrew Klapper, 307 Marksbury Building, Dept. of Computer Science,
University of Kentucky, Lexington, KY, 40506-00633, klapper at cs.uky.edu.
www.cs.uky.edu/~klapper/andy.html

**Abstract**
We study algebraic feedback shift registers (AFSRs) based on quotients of
polynomial rings in several variables over a finite field. These registers are
natural generalizations of linear feedback shift registers. We describe
conditions under which such AFSRs produce sequences with various ideal randomness
properties. We also show that there is an efficient algorithm which, given a
prefix of a sequence, synthesizes a minimal such AFSR that outputs
the sequence.