Hi David,
Yes I understand, but now I think that have a logic problem in algorithm, but I don't know where ... i "copying lines" from [Ict2011], ... 2011/9/28 David Joyner <wdjoy...@gmail.com> > On Wed, Sep 28, 2011 at 5:58 PM, Juan Grados <juan...@gmail.com> wrote: > > help please! > > > They did seem to solve your problem, didn't they? > Do you not understand the English? Do you simply disagree? > If you don't understand the English, please find someone who can translate. > > Did you find another error after fixing the problem they told about? > > Please be very clear exactly what it is you are having a problem > understanding in this thread. > > > > > > 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 > > > -- --------------------------------------------------------------------- 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
