Hi everybody,
I am implement Patterson Algorithm for Goppa code,
I am "copying" lines from paper How SAGE helps to implement Goppa
Codes and McEliece PKCSs [attach], and my test is a random vector .
the error are in Line 77,
I expect get roots from \sigma (locator polynomial), but
implementation have a fail before.
thanks by your attention.
'''
Patterson Implementation:
The following algorithm are in [Ict2011]
REFERENCES:
.. [Ict2011] How SAGE helps to implement Goppa Codes and McEliece
PKCSs
'''
def encode(u):
return u*G_Goppa
def split1(p):
# split polynomial p over F into even part po
# and odd part p1 such that p(z) = p2 (z) + z p2 (z)
Phi1 = p.parent()
p0 = Phi1([sqrt(c) for c in p.list()[0::2]])
p1 = Phi1([sqrt(c) for c in p.list()[1::2]])
return (p0,p1)
m = 4
N = 2^m - 1;
F.<x> = GF(2)
Phi.<x> = GF(2^m);
PR = PolynomialRing(Phi,'z');
print 'PR is',PR;
codelocators = [x^i for i in range(N)]
print(codelocators)
X = PolynomialRing(F,repr('z')).gen()
#defining Goppa Polynomial
g = X^2+X+x^3
print 'goppa polinomial=',g
#verifing if g is irreducible over F
if g.is_irreducible():
print 'g(z) =',g,'is irreducible'
#verifing g(codelocators[i])<>0
for i in range(N):
if g(codelocators[i])==Phi(0):
print 'alarm: g(alpha_'+str(i)+')=0'
#creating Parity Check Matrix
H_gRS = matrix([[codelocators[j]^(i) for j in range(N)] for i in
range(m)])
H_Goppa = matrix(F,m*H_gRS.nrows(),H_gRS.ncols());
for i in range(H_gRS.nrows()):
for j in range(H_gRS.ncols()):
be = bin(eval(H_gRS[i,j].int_repr()))[2:]
be = '0'*(m-len(be))+be
be = list(be)
H_Goppa[m*i:m*(i+1),j]=vector(map(int,be))
#creating Generator Matrix
Krnl = H_Goppa.right_kernel()
G_Goppa = Krnl.basis_matrix()
print 'H_Goppa=',H_Goppa
print 'G_Goppa=',G_Goppa
#code dimension
k = G_Goppa.nrows()
#################TEST##################
#creating a random vector 'u' to test decode
u = vector(F,[randint(0,1) for _ in range(k)])
print 'u=',u
#coding random vector 'u' with G_Goppa
c = encode(u)
#creating error vector
e = vector(F,H_gRS.ncols())
e[5]=1;
y = vector(F,H_gRS.ncols())
#vector to test decode
y = c+e;
#creating syndrome polynomial
s = H_gRS*y.transpose()
sP = PR([s[_,0] for _ in range(s.nrows())])
#steps to Patterson Algorithm from paper
g0g1 = split1(g);
w = (g0g1[0])._mul_(((g0g1[1])).__invert__())
T0T1 = split1((sP).__invert__()._add_(X)) # here ERROR
R = T0T1[0]+((w)*(T0T1[1]))
print 'R=',R
(d1,u,v) =xgcd(1,R)
print 'egcd',(d1,u,v)
a = g*u
b = g*v
#creating locator polynomial
sigma = (a^2+X*(b^2))
print 'sigma',sigma
#verifing roots
for i in range(N):
if((sigma((x^i))) == 0): # an error occured
print 'error'
print N-i
--
---------------------------------------------------------------------
Juan del Carmen Grados Vásquez
Laboratório Nacional de Computação Científica
Tel: +55 24 2233-6260
(http://www.lncc.br/)
http://juaninf.blogspot.com
---------------------------------------------------------------------
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
