---
title: "Pseudo-Random Bit Sequences"
canonical: "https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/index-pseudo-random-bit-sequences.html"
source: "https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/index-pseudo-random-bit-sequences.md"
part: "Coding Theory"
chapter: "Pseudo-Random Bit Sequences"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Coding Theory", "source": "https://docs.magma-maths.org/v2.30-1/CodingTheory/index-coding-theory.md"}
prev: {"title": "Bibliography", "source": "https://docs.magma-maths.org/v2.30-1/CodingTheory/QuantumCodes/bibliography.md"}
next: {"title": "Introduction", "source": "https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/introduction.md"}
---

# Pseudo-Random Bit Sequences

- [Introduction](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/introduction.md)
- [Linear Feedback Shift Registers](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md)
  - [`LFSRSequence(C, S, t): RngUPolElt, SeqEnum, RngIntElt → SeqEnum`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md#function-lfsrsequence-rngupolelt-seqenum-rngintelt)
  - [`LFSRStep(C, S): RngUPolElt, SeqEnum → SeqEnum`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md#function-lfsrstep-rngupolelt-seqenum)
  - [`BerlekampMassey(S): SeqEnum → RngUPolElt, RngIntElt`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md#function-berlekampmassey-seqenum)
  - [`ConnectionPolynomial(S): SeqEnum → RngUPolElt, RngIntElt`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md#function-connectionpolynomial-seqenum)
  - [`CharacteristicPolynomial(S): SeqEnum → RngUPolElt, RngIntElt`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md#function-characteristicpolynomial-seqenum)
  - [Example: Connection Polynomial via Berlekamp-Massey](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md#example-ex-ad3ed3)
  - [`ShrinkingGenerator(C1, S1, C2, S2, t): RngUPolElt, SeqEnum, RngUPolElt, SeqEnum, RngIntElt → SeqEnum`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/lfsr.md#function-shrinkinggenerator-rngupolelt-seqenum-rngupolelt-seqenum-rngintelt)
- [Correlation Functions](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/correlation.md)
  - [`AutoCorrelation(S, t): SeqEnum, RngIntElt → RngIntElt`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/correlation.md#function-autocorrelation-seqenum-rngintelt)
  - [Example: Autocorrelation of an LFSR Sequence](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/correlation.md#example-ex-e9917a)
  - [`CrossCorrelation(S1, S2, t): SeqEnum, SeqEnum, RngIntElt → RngIntElt`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/correlation.md#function-crosscorrelation-seqenum-seqenum-rngintelt)
- [Decimation](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/misc.md)
  - [`Decimation(S, f, d): SeqEnum, RngIntElt, RngIntElt → SeqEnum`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/misc.md#function-decimation-seqenum-rngintelt-rngintelt)
  - [`Decimation(S, f, d, t): SeqEnum, RngIntElt, RngIntElt, RngIntElt → SeqEnum`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/misc.md#function-decimation-seqenum-rngintelt-rngintelt-rngintelt)
  - [Example: Decimating an LFSR Sequence](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/misc.md#example-ex-29a760)
- [Hash Functions](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/hash.md)
  - [`SHA1(S): SeqEnum → MonStgElt`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/hash.md#function-sha1-seqenum)
  - [`SHA1(s): MonStgElt → MonStgElt`](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/hash.md#function-sha1-monstgelt)
  - [Example: Digest of a String and of Its Bytes](https://docs.magma-maths.org/v2.30-1/CodingTheory/PseudoRandomBitSequences/hash.md#example-ex-d53a66)
