help please! 2011/9/28 Juan Grados <juan...@gmail.com>
> 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 > --------------------------------------------------------------------- > > -- --------------------------------------------------------------------- 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
