in the end line print sigma.roots(),
always give empty vector, here sigma.roots() should nonzero vector 2011/9/28 Juan Grados <juan...@gmail.com> > 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 > --------------------------------------------------------------------- > > -- --------------------------------------------------------------------- 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
