Hi thanks for your answers, I used _inverter_, _mul_, _add_ etc, because apparently the implementation work fine but only "apparently", i think that the essencial problem is with _invert_ method, but now I used inverse_mod , but I dont where are the error, I implemented Berlekamp Algorithm too, from [Ict2011], its inside worksheet, this work fine, but Patterson Algorithm no,
please help me with this implementation ''' ALGORITHM: The following two algorithms are in [Ict2011] REFERENCES: .. [Ict2011] How SAGE helps to implement Goppa Codes and McEliece PKCSs URL : http://www.google.com/url?sa=t&source=web&cd=2&ved=0CCUQFjAB&url=http%3A%2F%2Fwww.weblearn.hs-bremen.de%2Frisse%2Fpapers%2FICIT11%2FRisse526ICIT11.pdf&ei=Q-yCTpK5C82cgQfj3803&usg=AFQjCNGEZ7SuMf1WKPrdkxvJMfiSaSqO1w&sig2=3RM25hfPNHCveQvdjTn4Iw ''' def encode(u): return u*G_Goppa; #this is the Berlekamp def decode(y,m,N,H_gRS): tt = var('z') s = H_gRS*y.transpose(); if s==matrix(Phi,H_gRS.nrows(),1): return y; b = PR([s[_,0] for _ in range(s.nrows())]); # bigN = m; sigma = vector(PolynomialRing(Phi,tt),bigN+2); omega = vector(PolynomialRing(Phi,tt),bigN+2); delta = vector(PolynomialRing(Phi,tt),bigN+2); sigma[-1+1] = PR(0); sigma[0+1] = PR(1); flag = 2*bigN; # exponent flags rational 1/z omega[-1+1] = z**flag; omega[0+1] = PR(0); # init mu and delta mu = -1; delta[-1+1] = 1; for i in range(bigN): delta[i+1] = (sigma[i+1]*b).coeffs()[i]; sigma[i+1+1] = sigma[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*sigma[mu+1](z); if (omega[mu+1].degree()==flag): omega[i+1+1] = omega[i+1](z)-(delta[i+1]/delta[mu+1])*z**(i-mu-1); else: omega[i+1+1] =omega[i+1](z)-z**(i-mu)*(delta[i+1]/delta[mu+1])*omega[mu+1](z); ord = max(sigma[i+1].degree(),1+omega[i+1].degree()); if (delta[i+1]<>0)and(2*ord<=i): mu = i; ELP = sigma[bigN+1]; # ErrorLocatorPolynomial n = G_Goppa.nrows(); ee = vector(F,[0 for _ in range(n)]); for i in range(N): if (ELP(x**i)==Phi(0)): # an error occured print 'error position',N-i return 0; def split(p): # split polynomial p over F into even part po # and odd part p1 such that p(z) = p2 (z) + z p2 (z) Phi = p.parent() p0 = Phi([sqrt(c) for c in p.list()[0::2]]); p1 = Phi([sqrt(c) for c in p.list()[1::2]]); return (p0,p1); m = 4 F.<x> = GF(2) Phi.<x> = GF(2^m); PR = PolynomialRing(Phi,'z'); print 'PR is',PR; N = 2^m - 1; codelocators = [x^i for i in range(N)] print(codelocators) X = PolynomialRing(Phi,repr('z')).gen(); g = X^2+X+x^3; # goppa polynomial print 'goppa polinomial',g if g.is_irreducible(): print 'g(z) =',g,'is irreducible'; for i in range(N): if g(codelocators[i])==Phi(0): print 'alarm: g(alpha_'+str(i)+')=0'; H_gRS = matrix([[codelocators[j]^(i) for j in range(N)] for i in range(m)]); H_gRS = H_gRS*diagonal_matrix([ 1/g(codelocators[i]) for i in range(N)]); print H_gRS 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)); Krnl = H_Goppa.right_kernel(); G_Goppa = Krnl.basis_matrix(); print H_Goppa k = G_Goppa.nrows() u = vector(F,[randint(0,1) for _ in range(k)]); c = encode(u); e = vector(F,H_gRS.ncols()); # e = zero vector e[3]=1 y = vector(F,H_gRS.ncols()); y = c + e print 'berlekamp algorithm' decode(y,m,N,H_gRS) print 'patterson algorithm' #adicionando error s = H_gRS*y.transpose(); sP = PR([s[_,0] for _ in range(s.nrows())]); print 'g=',g g0g1 = split(g); w = g0g1[0]*(((g0g1[1]).inverse_mod(g))) print 'w=',w T0T1 = split(sP.inverse_mod(g) + X); R = T0T1[0]+(w)*(T0T1[1]) print 'R',R (d1,u,v) = xgcd(1,R); # where d = gcd(1,R) = 1 a = g*u; b = g*v; sigma = (a^2+X*(b^2)); print sigma.roots() 2011/9/28 D. S. McNeil <dsm...@gmail.com> > > This is definitely not a bug. The definition of the _add_ method > > absolutely demands that both inputs have exactly the same parent. In > > the above instance, the left hand input (=1) has parent ZZ, and the > > right hand input (=SR(2)) has parent the symbolic ring. > > Yeah, I know that-- it's the violation of that assumption which > ultimately crashed the OP's code, after all. > > I guess I've inherited the bias from Python that users shouldn't be > able to segfault the interpreter from pure Python code. > Anything Cythonic probably falls into the Sage equivalent of the > "ctypes exception" class, and I guess you can get the same crash with > any non-typechecking cpdef'd object, but it still feels wrong. > > Meh. > > > Doug > > -- > To post to this group, send email to sage-support@googlegroups.com > To unsubscribe from this group, send email to > sage-support+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-support > URL: http://www.sagemath.org > -- --------------------------------------------------------------------- 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 sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
