[sage-support] Re: reducing ideal wrt another ideal
Ah! Thanks a lot for this "trick" of iteration! Day by day I am learning new tricks with sage :-) By the way after seeing your reply I saw a mathematical "typo" in my code: I should reduce I3 modulo I2 and not the other way round :-) Anyways, I have already taken of in my main program. Thanks a lot once again... -- VInay On Sep 28, 11:57 pm, john_perry_usm wrote: > Try this: > > sage: I3_red_I2 = R.ideal([p.reduce(I2gb) for p in I3gb]) > > regards > john perry > > On Sep 28, 12:24 am, Vinay Wagh wrote: > > > > > > > > > Suppose I have two ideals I & J in k[X_1,\cdots,x_n], where k is a > > field. How do I reduce an ideal I wrt ideal J. > > > e.g. Singular provides me a command > > > singular > reduce(I,std(J)); > > > Without moving back and forth to Singular, is it possible to implement > > this in sage? > > > I tried the following code: > > > sage: R. = PolynomialRing(QQ,3,order=TermOrder('wdeglex',[4,6,11])); > > sage: I = R.ideal(X^2-Y^3+Z^4, Y^5-Z^6+X^7, Z^13-X^12+Y^11); > > sage: I2 = I*I; > > sage: I3 = I2*I; > > sage: I2gb = I2.groebner_basis(); > > sage: I3gb = I3.groebner_basis(); > > sage: I2gb > > sage: I3_red_I2 = reduce(I3, I2gb); > > > The last command (redece) is giving me an error. I am not getting what > > wrong I am doing... > > > Thanks and regards > > > -- VInay Wagh -- 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
Re: [sage-support] Question about Patterson Algorithm Implementation
I have already sent, but I dont answer ... because I expect please only if anyelse can help me iff a time ... 2011/9/28 David Joyner > On Wed, Sep 28, 2011 at 6:12 PM, Juan Grados wrote: > > 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], ... > > > I would just email the author of the paper and ask him. > > > > 2011/9/28 David Joyner > >> > >> On Wed, Sep 28, 2011 at 5:58 PM, Juan Grados 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 > >> >> > >> >> in the end line > >> >> print sigma.roots(), > >> >> always give empty vector, here sigma.roots() should nonzero vector > >> >> 2011/9/28 Juan Grados > >> >>> > >> >>> 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. = GF(2) > >> >>> Phi. = 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 > >> >>>
Re: [sage-support] Question about Patterson Algorithm Implementation
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 > On Wed, Sep 28, 2011 at 5:58 PM, Juan Grados 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 > >> > >> in the end line > >> print sigma.roots(), > >> always give empty vector, here sigma.roots() should nonzero vector > >> 2011/9/28 Juan Grados > >>> > >>> 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. = GF(2) > >>> Phi. = 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'
Re: [sage-support] Question about Patterson Algorithm Implementation
help please! 2011/9/28 Juan Grados > in the end line > > print sigma.roots(), > > always give empty vector, here sigma.roots() should nonzero vector > > 2011/9/28 Juan Grados > >> 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. = GF(2) >> Phi. = 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 >> >> > 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. >>> >>>
[sage-support] Re: reducing ideal wrt another ideal
Try this: sage: I3_red_I2 = R.ideal([p.reduce(I2gb) for p in I3gb]) regards john perry On Sep 28, 12:24 am, Vinay Wagh wrote: > Suppose I have two ideals I & J in k[X_1,\cdots,x_n], where k is a > field. How do I reduce an ideal I wrt ideal J. > > e.g. Singular provides me a command > > singular > reduce(I,std(J)); > > Without moving back and forth to Singular, is it possible to implement > this in sage? > > I tried the following code: > > sage: R. = PolynomialRing(QQ,3,order=TermOrder('wdeglex',[4,6,11])); > sage: I = R.ideal(X^2-Y^3+Z^4, Y^5-Z^6+X^7, Z^13-X^12+Y^11); > sage: I2 = I*I; > sage: I3 = I2*I; > sage: I2gb = I2.groebner_basis(); > sage: I3gb = I3.groebner_basis(); > sage: I2gb > sage: I3_red_I2 = reduce(I3, I2gb); > > The last command (redece) is giving me an error. I am not getting what > wrong I am doing... > > Thanks and regards > > -- VInay Wagh -- 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
[sage-support] Re: error: C preprocessor "/lib/cpp" fails sanity check (installing sage-4.7.1 from source)
I succesfully compiled from sources sage-4.7.1 on Pardus 2011.1 x86_64 using only this repository http://packages.pardus.org.tr/pardus/2011.1/stable/x86_64/pisi-index.xml.xz and these upgrades FreeImage-devel is upgraded from 3.15.0-7-p11-x86_64 to 3.15.0-10-p11- x86_64 FreeImage is upgraded from 3.15.0-7-p11-x86_64 to 3.15.0-10-p11- x86_64 from here http://packages.pardus.org.tr/pardus/2011.1/devel/x86_64/ The sources of sage-4.7.1 can be found here http://www.sagemath.org/download-source.html Just unpack, cd to the directory of sage-4.7.1 and (without root permissions) type make. It lasted approximately 5 hours on my computer. More information: http://www.sagemath.org/doc/installation/source.html#install-from-source-code -- 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
[sage-support] Re: inverse function
On Sep 28, 12:49 pm, Minh Nguyen wrote: > Hi, > > On Thu, Sep 29, 2011 at 2:17 AM, globaljavaprogrammer > > wrote: > > how can I use sage to compute the inverse of a function like f(x) = (x > > +1)^2? > > sage: f = (x + 1)^2 But assuming he meant the function inverse, not the multiplicative inverse... This is in general a very hard problem, of course. But one can do some cases. Yours: sage: f = (x+1)^2 sage: var('y') y sage: solve(f==y,x) [x == -sqrt(y) - 1, x == sqrt(y) - 1] or others: sage: h = 2^(x+5) sage: solve(h==y,x) [x == -(5*log(2) - log(y))/log(2)] But we don't give the elliptic function inverses to crazy things. sage: g = x^5+x+1 sage: solve(g==y,x) [0 == x^5 + x - y + 1] The underlying functionality for this is provided by Maxima. So if they can't solve it, we can't either. - kcrisman -- 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
Re: [sage-support] inverse function
Hi, On Thu, Sep 29, 2011 at 2:17 AM, globaljavaprogrammer wrote: > how can I use sage to compute the inverse of a function like f(x) = (x > +1)^2? sage: f = (x + 1)^2 sage: g = 1 / f sage: h = f^(-1) sage: f*g 1 sage: g*f 1 sage: f*h 1 sage: h*f 1 -- Regards Minh Van Nguyen -- 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
[sage-support] inverse function
how can I use sage to compute the inverse of a function like f(x) = (x +1)^2? -- 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
[sage-support] Re: Diagonalizing (symmetric) matrices with entries in a rational function field
On Sep 28, 2:48 pm, flyingsquirrel wrote: > I have a symmetric matrix that I want to diagonalize, such as > > x y z > y 0 xy > z xy xyz > > x, y, z being variables, and the base field is CC (complex numbers). I > typed in the following: > > R.=CC[] > m=matrix(R,[[x,y,z],[y,0,x*y],[z,x*y,x*y*z]]) > m.eigenvalues() > > and I get an error message (NotImplementedError). How do I diagonalize > this matrix? sage: var('x y z') (x, y, z) sage: m=matrix([[x,y,z],[y,0,x*y],[z,x*y,x*y*z]]) sage: e=m.eigenvalues() works but gives very long answer (Compare Wolfram alpha which also gives long answer) (v=m.eigenvectors() takes ~ 5min) Andrzej Chrzeszczyk -- 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
[sage-support] Diagonalizing (symmetric) matrices with entries in a rational function field
I have a symmetric matrix that I want to diagonalize, such as x y z y 0 xy z xy xyz x, y, z being variables, and the base field is CC (complex numbers). I typed in the following: R.=CC[] m=matrix(R,[[x,y,z],[y,0,x*y],[z,x*y,x*y*z]]) m.eigenvalues() and I get an error message (NotImplementedError). How do I diagonalize this matrix? -- 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
Re: [sage-support] Question about Patterson Algorithm Implementation
in the end line print sigma.roots(), always give empty vector, here sigma.roots() should nonzero vector 2011/9/28 Juan Grados > 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. = GF(2) > Phi. = 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 > > > 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 th
Re: [sage-support] Question about Patterson Algorithm Implementation
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. = GF(2) Phi. = 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 > > 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/
Re: [sage-support] Question about Patterson Algorithm Implementation
> 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
[sage-support] Question About Primitive Element
Hi How I will get a primite element ... F = GF(2) PRF. = PolynomialRing(F); print PRF Phi = PRF.quotient(z^4+z+1); Phi.primitive_element() . ? -- - 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
[sage-support] Questión about primitive element
Hi How I will get a primite element ... F = GF(2) PRF. = PolynomialRing(F); print PRF Phi = PRF.quotient(z^4+z+1); Phi.primitive_element() . ? -- - 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