Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.
| Download
Image: ubuntu2204
Kernel: SageMath 10.1
In [4]:
from sage.all import * # Initialization n = 255 F = GF(n + 1, 'a', modulus='primitive') R = PolynomialRing(F, 's') k = 223 t = n - k alpha = F.gen() s = R.gen() generator_poly = prod([s - alpha**j for j in range(1, t + 1)]) # Convert received bytes to polynomial received_bytes = b'O\x04\xc0A\xd1\xceY\x05\xb44\xda\xf6\xe5F_V\xd1N\xf9\xc2\xe2\x01l\xc2\xbb\xf0w:\x01\x8bw\xaa\x00\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x0b\x0c\xab\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x8b\x1d\x1e\x1f !"#$%&\'()*\xa3,-./0123456789C;<=>?@ABCDEFGH#JKLMNOPQRSTUVW\x03YZ[\\]^_`abcdef+hijklmnopqrstuKwxyz{|}~\x7f\x80\x81\x82\x83\x84\xab\x86\x87\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f\x90\x91\x92\x93\x8b\x95\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f\xa0\xa1\xa2\xb3\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf\xb0\xb1\xb3\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf\xc0\xc1\xc2\xc3\xc4\xc5\xc6\xc7\xc8\xc9\xca\xcb\xcc\xcd\xce\xcf\xd0\xd1\xd2\xd3\xd4\xd5\xd6\xd7\xd8\xd9\xda\xdb\xdc\xdd\xde' received_poly = R(list(received_bytes)) # Compute syndromes syndromes = [received_poly(alpha**i) for i in range(1, t + 1)] # Berlekamp-Massey algorithm def berlekamp_massey(syndromes): L = R(1) # Current error locator polynomial B = R(1) # Previous version of L m = 1 b = F(1) # Coefficient used to adjust L for n in range(len(syndromes)): discrepancy = syndromes[n] for k in range(1, len(L.coefficients())): if n-k < 0: break discrepancy += L[k] * syndromes[n - k] if discrepancy != 0: T = L L = L - discrepancy * b * B.shift(m) if 2 * len(T.coefficients()) <= n + 1: B = T b = discrepancy.inverse() m = n + 1 - len(T.coefficients()) return L # Check for errors if not all(syndrome == 0 for syndrome in syndromes): # Apply Berlekamp-Massey algorithm to find error locator polynomial L = berlekamp_massey(syndromes) # Find the roots of the error locator polynomial (Chien Search) error_locations = [] for i in range(n): if L(alpha**i) == 0: error_locations.append(n - 1 - i) # Calculate error values using Forney's algorithm error_values = [] for loc in error_locations: X = alpha**(-loc) Y = received_poly(X) Z = L.derivative()(X) error_value = Y * X * Z.inverse() error_values.append(error_value) else: error_locations = [] error_values = [] # Output the error locations and values error_locations, error_values
([214, 29], [a + 1, a^5 + a^3 + a])
In [0]: