Pseudo-Random Bit Sequences

• Introduction
• Linear Feedback Shift Registers
  • LFSRSequence(C, S, t): RngUPolElt, SeqEnum, RngIntElt → SeqEnum
  • LFSRStep(C, S): RngUPolElt, SeqEnum → SeqEnum
  • BerlekampMassey(S): SeqEnum → RngUPolElt, RngIntElt
  • ConnectionPolynomial(S): SeqEnum → RngUPolElt, RngIntElt
  • CharacteristicPolynomial(S): SeqEnum → RngUPolElt, RngIntElt
  • Example: Connection Polynomial via Berlekamp-Massey
  • ShrinkingGenerator(C1, S1, C2, S2, t): RngUPolElt, SeqEnum, RngUPolElt, SeqEnum, RngIntElt → SeqEnum
• Correlation Functions
  • AutoCorrelation(S, t): SeqEnum, RngIntElt → RngIntElt
  • Example: Autocorrelation of an LFSR Sequence
  • CrossCorrelation(S1, S2, t): SeqEnum, SeqEnum, RngIntElt → RngIntElt
• Decimation
  • Decimation(S, f, d): SeqEnum, RngIntElt, RngIntElt → SeqEnum
  • Decimation(S, f, d, t): SeqEnum, RngIntElt, RngIntElt, RngIntElt → SeqEnum
  • Example: Decimating an LFSR Sequence
• Hash Functions
  • SHA1(S): SeqEnum → MonStgElt
  • SHA1(s): MonStgElt → MonStgElt
  • Example: Digest of a String and of Its Bytes