Berlekamp–Massey algorithm
E167281
The Berlekamp–Massey algorithm is a key algorithm in coding theory and cryptography used to efficiently determine the shortest linear feedback shift register that generates a given binary sequence.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Berlekamp–Massey algorithm canonical | 10 |
| Berlekamp–Massey recursion | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T1451895 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Berlekamp–Massey algorithm Context triple: [Elwyn R. Berlekamp, notableWork, Berlekamp–Massey algorithm]
-
A.
Berlekamp’s algorithm for factoring polynomials over finite fields
Berlekamp’s algorithm for factoring polynomials over finite fields is a foundational deterministic method in computational algebra that efficiently decomposes polynomials into irreducible factors over finite fields and underpins many modern algorithms in coding theory and cryptography.
-
B.
Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
-
C.
Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
-
D.
Knuth–Morris–Pratt algorithm
The Knuth–Morris–Pratt algorithm is a classic linear-time string-searching algorithm that efficiently finds occurrences of a pattern within a text by precomputing a prefix function to avoid redundant comparisons.
-
E.
Thompson's algorithm
Thompson's algorithm is a classic computer science method for converting regular expressions into nondeterministic finite automata (NFAs), widely used in pattern matching and lexical analysis.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Berlekamp–Massey algorithm Target entity description: The Berlekamp–Massey algorithm is a key algorithm in coding theory and cryptography used to efficiently determine the shortest linear feedback shift register that generates a given binary sequence.
-
A.
Berlekamp’s algorithm for factoring polynomials over finite fields
Berlekamp’s algorithm for factoring polynomials over finite fields is a foundational deterministic method in computational algebra that efficiently decomposes polynomials into irreducible factors over finite fields and underpins many modern algorithms in coding theory and cryptography.
-
B.
Blum–Blum–Shub pseudorandom number generator
The Blum–Blum–Shub pseudorandom number generator is a cryptographically secure generator based on the hardness of factoring large composite numbers, widely studied in theoretical computer science and cryptography.
-
C.
Blum–Micali pseudorandom number generator
The Blum–Micali pseudorandom number generator is a foundational cryptographic algorithm that produces provably secure pseudorandom bits based on number-theoretic hardness assumptions.
-
D.
Knuth–Morris–Pratt algorithm
The Knuth–Morris–Pratt algorithm is a classic linear-time string-searching algorithm that efficiently finds occurrences of a pattern within a text by precomputing a prefix function to avoid redundant comparisons.
-
E.
Thompson's algorithm
Thompson's algorithm is a classic computer science method for converting regular expressions into nondeterministic finite automata (NFAs), widely used in pattern matching and lexical analysis.
- F. None of above. chosen
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm
ⓘ
coding theory algorithm ⓘ cryptography algorithm ⓘ |
| alternativeForm |
Berlekamp–Massey recursion
ⓘ
linked to:
Berlekamp–Massey algorithm
|
| appliedIn |
CDMA code sequence design
ⓘ
PRNG evaluation ⓘ sequence analysis in communications ⓘ spread-spectrum systems ⓘ stream cipher design ⓘ |
| assumes | sequence generated by a linear recurrence ⓘ |
| basedOn | discrepancy computation ⓘ |
| canBeExtendedTo | sequences over arbitrary finite fields ⓘ |
| computes |
connection polynomial of minimal LFSR
ⓘ
shortest linear feedback shift register ⓘ |
| describedIn | coding theory literature ⓘ |
| field |
coding theory
ⓘ
cryptography ⓘ |
| generalizationOf | methods for solving linear recurrences from sequences ⓘ |
| hasStep |
compute discrepancy at each sequence position
ⓘ
conditionally adjust LFSR length ⓘ iteratively update connection polynomial ⓘ |
| hasTimeComplexity | O(n^2) ⓘ |
| input |
binary sequence
ⓘ
finite sequence over a finite field ⓘ |
| minimizes | length of LFSR consistent with observed sequence ⓘ |
| namedAfter |
Elwyn Berlekamp
ⓘ
linked to:
Elwyn R. Berlekamp
James Massey ⓘ |
| originatedFrom | work on BCH codes ⓘ |
| output |
linear complexity of the sequence
ⓘ
minimal LFSR that generates the sequence ⓘ |
| property |
deterministic
ⓘ
exact ⓘ |
| relatedTo |
Berlekamp algorithm
ⓘ
Euclidean algorithm for polynomials ⓘ key stream sequence ⓘ linear complexity profile ⓘ linear feedback shift register ⓘ linear recurrence relation ⓘ |
| usedFor |
analysis of pseudorandom sequences
ⓘ
computing linear complexity of sequences ⓘ cryptanalysis of stream ciphers ⓘ error-correcting code design ⓘ synthesis of linear feedback shift registers ⓘ |
| usedIn | decoding of some cyclic codes ⓘ |
| worksOver |
GF(2)
ⓘ
finite fields ⓘ |
| yearIntroducedApprox | 1969 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Berlekamp–Massey algorithm Description of subject: The Berlekamp–Massey algorithm is a key algorithm in coding theory and cryptography used to efficiently determine the shortest linear feedback shift register that generates a given binary sequence.
Referenced by (11)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject linked to:
Elwyn
Berlekamp’s algorithm for factoring polynomials over finite fields
→
relatedTo
→
Berlekamp–Massey algorithm
ⓘ
linked to: Berlekamp–Massey algorithm