# ERROR DETECTION AND CORRECTION:
# "received_poly = R(list(received_bytes))": it converts the received bytes into a polynomial in the polynomial ring 'R'.
# "syndromes = [received_poly(alpha^i) for i in range(1, t+1)]": computes the syndromes by evaluating the received polynomial at successive powers of "alpha". If all syndromes are zero, there are no errors.
# If there are non-zero syndromes:
# "syndrome_poly = R(syndromes[::-1])": this forms the syndrome polynomial by reversing the list of syndromes.
# "_, L, E = syndrome_poly.xgcd(generator_poly)": it uses the Extended Euclidean Algorithm to find the error locator polynomial "L" and the error value polynomial "E".
# "L = L / L.leading_coefficient("), "E = E / E.leading_coefficient()": these normalize the polynomials "L" and "E".

# FINDING ERRORS:
# "error_positions": thid determines the positions of the errors by finding the roots of the error locator polynomial "L".
# "error_values": this calculates the values of the errors using Forney's formula and the error evaluator polynomial "E".

# CORRECTING ERRORS:
# Loops over the error positions and values, correcting the errors in the received polynomial.

# EXTRACTING ORIGINAL MESSAGE:
# "original_message = received_poly.list()[0:k]": this one extracts the original message from the corrected polynomial by taking the first "k" coefficients.

n = 255
F.<alpha> = GF(n+1, 'a', modulus='primitive')
assert alpha.multiplicative_order() == n
R.<s> = F['s']

# example of searching for roots in this polynomial ring
# print((s**2 * (s-1)).roots())
# consult ?s.roots for more help

k = 223
t = n - k
generator_poly = prod([s - alpha**j for j in range(1, t+1)])
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))

syndromes = [received_poly(alpha^i) for i in range(1, t+1)]
if max(syndromes) == 0:
    print("No errors detected.")
else:
    syndrome_poly = R(syndromes[::-1])
    _, L, E = syndrome_poly.xgcd(generator_poly)

    L = L / L.leading_coefficient()
    E = E / E.leading_coefficient()

    error_positions = [n - i.log(alpha) for i in L.roots(multiplicities=False)]

    error_values = [E(alpha^(-pos)) / L.derivative()(alpha^(-pos)) for pos in error_positions]

    for pos, val in zip(error_positions, error_values):
        received_poly += R([0]*(n-pos-1) + [val] + [0]*pos)

    original_message = received_poly.list()[0:k]

    print(f"Error positions: {error_positions}")
    print(f"Error values: {error_values}")
    print(f"Original message: {original_message}")