Engineering / Mathematics — Polynomial Algorithms
Computing Minimal Polynomials of Sequences
The Berlekamp-Massey algorithm and its Euclidean equivalent for finding the shortest linear recurrence.
Executive summary
Berlekamp-Massey finds the minimal polynomial of a linearly generated sequence from twice as many terms as its degree, in quadratic time.
It is equivalent to a halted extended Euclidean run, and the two formulations are used interchangeably.
Learning objectives
- State the problem and the term requirement.
- Describe both algorithmic formulations.
- Identify the applications.
01The problem
Minimal recurrence problem
Given s₀, ..., s_{2d−1}, find the monic polynomial of least degree at most d annihilating the sequence.
Term requirement
2d terms are necessary and sufficient to determine a minimal polynomial of degree at most d.
The count is exactly the rational function reconstruction condition. A recurrence of order d has d unknown coefficients, and each term beyond the first d gives one equation — so d equations require 2d terms.
02Two formulations
Berlekamp-Massey
Processes terms one at a time, maintaining a current candidate recurrence and correcting it whenever a discrepancy appears. Naturally incremental.
Euclidean
Runs extended Euclid on X^{2d} and the sequence polynomial, halting when the remainder degree drops below d. Conceptually cleaner.
Euclidean formulation
2d sequence termsthe minimal polynomial of the sequence- Form the polynomial S(X) = s₀ + s₁X + ... + s_{2d−1}X^{2d−1}.
- Run extended Euclid on the pair (X^{2d}, S).
- Halt at the first remainder of degree less than d.
- The accumulated coefficient at that point is the reversed minimal polynomial.
- Reverse and normalise to monic.
O(d²) field operationsThe equivalence of the two is a standard result. Berlekamp–Massey is preferred where terms arrive incrementally; the Euclidean form is preferred where the theory matters, because its correctness follows from rational function reconstruction rather than requiring a separate argument.
03Applications
- Reed-Solomon decoding
Error locator polynomialSyndromes are linearly generated by it - Block Wiedemann
Sparse linear system solvingMatrix-power projections give the sequence - Minimal polynomial of an element
Algebra computationRandom projection of powers - LFSR cryptanalysis
Recovering the registerOutput stream is the sequence
The fourth application is the reason linear feedback shift registers are never used alone as stream ciphers. Berlekamp–Massey recovers a register of length d from 2d output bits in quadratic time, so the keystream is trivially predictable after a short observation.
04Frequently asked questions
Are the two formulations really the same algorithm?
They compute the same result with the same complexity, and the correspondence between their intermediate states is explicit. Berlekamp-Massey is the incremental view of the Euclidean recursion.
Can the minimal polynomial be found faster than quadratically?
Yes, with fast polynomial arithmetic. The half-gcd approach gives O(d log² d), which matters for large degrees in sparse linear algebra applications.
What if the sequence is not linearly generated?
The algorithm returns a polynomial annihilating the supplied terms, whose degree will be close to half the number of terms. That large degree is the signal that no short recurrence exists.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 428-435.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.