Description
When testing my own implementation of the Berlekamp-Massey algorithm against the one in Sage, I discovered a bug in Sage's implementation. Under certain circumstances when a minimal polynomial of degree n or less does not exist for a 2n length sequence, berlekamp_massey() will return a "valid" minimal polynomial. However, this polynomial does not produce the original sequence.
Example:
In the example below, the length-10 sequence over GF(2^3) allegedly has a minimal polynomial of degree 4. However, when constructing the corresponding LFSR and outputting the next 10 symbols, they are not equal to the input sequence (the last symbol differs).
F = GF(2^3, repr="int")
y = [4, 0, 2, 0, 7, 2, 0, 0, 2, 1]
y = [F.fetch_int(yi) for yi in y] # Convert to GF(2^3)
c = berlekamp_massey(y)
print("y =", y)
print("c(x) =", c)
# y [4, 0, 2, 0, 7, 2, 0, 0, 2, 1]
# c(x) = x^4 + 3*x^3 + 3
key = [3, 0, 0, 3]
key = [-F.fetch_int(k) for k in key]
fill = y[0:4]
print("key =", key)
print("fill =", fill)
# key = [3, 0, 0, 3]
# fill = [4, 0, 2, 0]
y2 = lfsr_sequence(key, fill, len(y))
print("y1 =", y)
print("y2 =", y2)
# y1 = [4, 0, 2, 0, 7, 2, 0, 0, 2, 1]
# y2 = [4, 0, 2, 0, 7, 2, 0, 0, 2, 0]
For reference, my implementation returns x^6 + 3x^5 + 6x^3 + x^2 + 2x + 1. Because degree 6 is larger than the maximum allowable of degree 5, I know there is no such minimal polynomial that produces y.
Component: cryptography
Keywords: berlekamp, massey
Issue created by migration from https://trac.sagemath.org/ticket/33537