Secrets of Linear Feedback Shift Registers

摘要

Summary A Linear Feedback Shift Register (LFSR) is a device that can generate a long, seemingly random, sequence of ones and zeroes. This is important in cryptography. We consider the sometimes unexpected periodic properties of LFSRs, how to understand them using linear algebra, and how to relate them to finite fields, another important topic in cryptography. Along the way, we resolve the puzzle of what it means for a polynomial to be primitive.