3835.sagews

x = PolynomialRing(GF(2), 'x').gen()
fx = x^6+x^4+x^3+x+1
F = GF(64, 'a', modulus=fx)
a=F.gen()

F.is_field()

True

fx.is_primitive()

True

x = PolynomialRing(GF(2), 'x').gen()
F = GF(64, 'a')
a = F.gen()

C1 = [mod(2^j, 63) for j in range(6)]
print C1

[1, 2, 4, 8, 16, 32]

C3 = [mod(3*2^j, 63) for j in range(6)]
print C3

[3, 6, 12, 24, 48, 33]

C5 = [mod(5*2^j, 63) for j in range(6)]
print C5

[5, 10, 20, 40, 17, 34]

C7 = [mod(7*2^j, 63) for j in range(6)]
print C7

[7, 14, 28, 56, 49, 35]

C9 = [mod(9*2^j, 63) for j in range(6)]
print C9

[9, 18, 36, 9, 18, 36]

C11 = [mod(11*2^j, 63) for j in range(6)]
print C11

[11, 22, 44, 25, 50, 37]

C13 = [mod(13*2^j, 63) for j in range(6)]
print C13

[13, 26, 52, 41, 19, 38]

C15 = [mod(15*2^j, 63) for j in range(6)]
print C15

[15, 30, 60, 57, 51, 39]

C21 = [mod(21*2^j, 63) for j in range(6)]
print C21

[21, 42, 21, 42, 21, 42]

C23 = [mod(23*2^j, 63) for j in range(6)]
print C23

[23, 46, 29, 58, 53, 43]

C27 = [mod(27*2^j, 63) for j in range(6)]
print C27

[27, 54, 45, 27, 54, 45]

C31 = [mod(31*2^j, 63) for j in range(6)]
print C31

[31, 62, 61, 59, 55, 47]

f1 = prod( x-a^j for j in C1)
f3 = prod( x-a^j for j in C3)
f5 = prod( x-a^j for j in C5)
f7 = prod( x-a^j for j in C7)
f9 = prod( x-a^j for j in C9)
g = f1*f3*f5*f7*f9
print f1, "\n", f3, "\n", f5, "\n", f7, "\n", f9, "\n", g

x^6 + x^4 + x^3 + x + 1 x^6 + x^5 + x^4 + x^2 + 1 x^6 + x + 1 x^6 + x^3 + 1 x^6 + x^2 + 1 x^30 + x^29 + x^27 + x^26 + x^22 + x^21 + x^19 + x^18 + x^16 + x^15 + x^14 + x^9 + x^8 + x^6 + x^5 + x^2 + 1

M = 12*[1]+12*[0]+12*[1]
N = sum( M[i]*x^i for i in range(len(M)))
print M, "\n", N

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] x^35 + x^34 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^27 + x^26 + x^25 + x^24 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

def encode(N):
    return N*x^35 + (N*x^35)%g

encode(N)

x^70 + x^69 + x^68 + x^67 + x^66 + x^65 + x^64 + x^63 + x^62 + x^61 + x^60 + x^59 + x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^40 + x^39 + x^38 + x^37 + x^36 + x^35 + x^25 + x^24 + x^22 + x^21 + x^20 + x^17 + x^13 + x^10 + x^9 + x^8 + x^6 + 1

N1 = x^70 + x^69 + x^68 + x^67 + x^66 + x^65 + x^64 + x^63 + x^62 + x^61 + x^60 + x^59 + x^46 + x^45 + x^44 + x^43 + x^42 + x^41 + x^39 + x^38 + x^37 + x^36 + x^35 + x^25 + x^24 + x^22 + x^21 + x^20 + x^18 + x^17 + x^13 + x^10 + x^9 + x^8 + x^6 + 1

s = sum( N1(a^j)*x^(j-1) for j in [1,2,3,4,5,6,7,8,9] )
print s

x^8 + (a^5 + a^4 + a^2 + a + 1)*x^7 + (a^5 + a^4 + a)*x^6 + (a^5 + a^4 + a^2 + a + 1)*x^5 + (a^3 + a^2 + 1)*x^4 + a^4*x^3 + a^4*x^2 + a^2*x + a

def qr(f, g):
    return (f- f%g)/g, f%g

q1, r1 = qr (x^9,s)
print q1, "\n", r1

x + a^5 + a^4 + a^2 + a + 1 (a^5 + 1)*x^7 + (a^5 + a)*x^6 + (a^4 + a^3 + a^2 + a)*x^5 + (a^5 + a^3 + a^2 + a + 1)*x^4 + (a^5 + a^4 + a^3 + 1)*x^3 + (a^5 + a^3 + a^2 + 1)*x^2 + (a^5 + a^4 + a + 1)*x + a^5 + a^4 + a^2 + 1

q2, r2 = qr (s, r1)
print q2, "\n", r2

(a^5 + a^4 + a^3 + a^2 + a + 1)*x + a^3 + a^2 + 1 a^5 + a^2 + a + 1

b1 = q1
b2 = 1 + b1*q2
print b2

(a^5 + a^3 + a + 1)*x^9

zeros = [b for b in F if b2(b)==0]
print zeros

[a^5 + a^4 + a^3, a^5 + a + 1]

error_locators = [discrete_log(b^(-1), a) for b in zeros]
print error_locators

[40, 18]

H = matrix([C1,C3,C5,C7,C9])
print H

[ 1 2 4 8 16 32] [ 3 6 12 24 48 33] [ 5 10 20 40 17 34] [ 7 14 28 56 49 35] [ 9 18 36 9 18 36]

def syndrome(v):
    return H*vector(v)

P=[0,1,1,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,1,0,1,1,1,1,0,0]
len(P)

63

Px = sum( P[i]*x^i for i in range(len(P)))
print Px

x^60 + x^59 + x^58 + x^57 + x^55 + x^53 + x^52 + x^51 + x^50 + x^47 + x^46 + x^41 + x^40 + x^39 + x^35 + x^34 + x^33 + x^29 + x^28 + x^27 + x^26 + x^24 + x^23 + x^18 + x^11 + x^7 + x^4 + x^3 + x^2 + x

q1, r1 = qr (x^9,s)
print q1, "\n", r1

(a^4 + a^2 + a + 1)*x + a^4 + a^2 + 1 (a^5 + a^3 + a^2 + a + 1)*x^7 + (a + 1)*x^6 + (a^4 + a^3 + a^2 + a + 1)*x^5 + (a^5 + a^3 + a^2 + a)*x^4 + (a^5 + a + 1)*x^3 + (a^5 + a^4 + a^3 + a^2)*x^2 + a^5*x + a^5 + a^4 + a^2 + 1

q2, r2 = qr (s, r1)
print q2, "\n", r2

(a^5 + a^4)*x + a^3 + a^2 + a (a^3 + a^2)*x^6 + (a^5 + a^2 + a)*x^5 + (a^3 + a + 1)*x^4 + (a^5 + a^2 + a)*x^3 + (a^4 + a^3 + a^2 + a + 1)*x^2 + (a + 1)*x + a^4 + a + 1

q3, r3 = qr (r1,r2)
print q3, "\n", r3

(a^3 + a + 1)*x + a^4 + a (a^4 + a^3)*x^5 + a^3*x^4 + (a^3 + a^2 + a)*x^3 + (a^5 + a^4 + a^2 + 1)*x^2 + (a^3 + a^2 + 1)*x + a^4 + a^2

q4, r4 = qr (r2,r3)
print q4, "\n", r4

(a^5 + a^3 + a^2 + 1)*x + a^4 + a^2 + 1 (a^4 + a)*x^4 + (a^5 + a^3 + a)*x^3 + (a^5 + a^4 + 1)*x^2 + (a^3 + a^2 + 1)*x + a^5

q5, r5 = qr (r3,r4)
print q5, "\n", r5

(a^5 + a + 1)*x + a^4 + a^3 + a^2 + 1 (a^3 + 1)*x^3 + (a^5 + a^4)*x

q6, r6 = qr (r4,r5)
print q6, "\n", r6

a*x + a^5 + a^4 + a + 1 (a^3 + a)*x^2 + a^5

q7, r7 = qr (r5,r6)
print q7, "\n", r7

(a^4 + a^3 + a)*x (a^5 + a^3 + 1)*x

q8, r8 = qr (r6,r7)
print q8, "\n", r8

(a^5 + a^4 + a^3 + a^2 + a)*x a^5

q9, r9 = qr (r7,r8)
print q9, "\n", r9

(a^5 + a^4 + a^2 + a)*x 0

b1 = q1
b2 = 1 + b1*q2
b3 = b1 + b2*q3
b4 = b2 + b3*q4
b5 = b3 + b4*q5
b6 = b4 + b5*q6
b7 = b5 + b6*q7
b8 = b6 + b7*q8
b9 = b7 + b8*q9 
print b4

a^4*x^4 + (a^5 + a^4 + a^3 + 1)*x^3 + (a^4 + a)*x^2 + (a^5 + a + 1)*x + a^5 + a

zeros = [b for b in F if b4(b)==0]
print zeros

[a^2]

error_locators = [discrete_log(b^(-1), a) for b in zeros]
print error_locators

[61]