Computer Science/Discrete Mathematics Seminar II
Pseudo-Random Number Generation by Algebraic Means (continued)
In the first talk I reviewed the basic properties of linear feedback shift registers and their analysis using generating functions and trace functions. I then defined feedback with carry shift registers (FCSRs) and began their analysis by N-adic numbers. This week, after reviewing the definitions, I will continue the analysis of FCSRs, looking at questions of periodicity, randomness properties, and the FCSR synthesis problem (the analog of the Berlekamp-Massey algorithm). We will also derive an analog of the trace representation. The last hour of the talk will focus on a broad generalization of both LFSRs and FCSRs, sequence generators based on completions of algebraic rings at arbitrary elements. Topics I will touch on are basic properties and analysis, special cases with tractable analysis and good properties, and in particular distribution properties and the register synthesis problem. The talk should be largely self contained and understandable if the first talk was missed.