[sage-devel] Re: www.sagenb.com's SSL certificate updated
On Jun 10, 1:32 am, mabshoff [EMAIL PROTECTED] wrote: During the last discussion about the certificate somebody mentioned some provider that gave free certificates to OS projects. William did contact that provider, but never heard back from them, so if anybody has any suggestions please let us know. Cheers, Michael Funny, I was thinking the other day about the certificate issue on Sage, having just had to sign one myself. There would be no harm in contacting Verisign, Thawte or any of the other properly supported CA's and asking them if they would do a freebie, Show them your sponsers page, say they would be added etc. The problem with the cheap CA's (GoDaddy etc) is the browsers don't support them, so people will get a warning anyway. In that case, you might as well sign it yourself as Micky Mouse and not bother asking them for a free one for OS projects. Universities would be in a pretty good position to act as CAs for students and staff and might well get Firefox to support them if they did a job well. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: www.sagenb.com's SSL certificate updated
On Mon, Jun 9, 2008 at 11:10 PM, Dr. David Kirkby [EMAIL PROTECTED] wrote: On Jun 10, 1:32 am, mabshoff [EMAIL PROTECTED] wrote: During the last discussion about the certificate somebody mentioned some provider that gave free certificates to OS projects. William did contact that provider, but never heard back from them, so if anybody has any suggestions please let us know. Cheers, Michael Funny, I was thinking the other day about the certificate issue on Sage, having just had to sign one myself. There would be no harm in contacting Verisign, Thawte or any of the other properly supported CA's and asking them if they would do a freebie, Show them your sponsers page, say they would be added etc. Great idea! Could you please do this? The problem with the cheap CA's (GoDaddy etc) is the browsers don't support them, so people will get a warning anyway. In that case, you might as well sign it yourself as Micky Mouse and not bother asking them for a free one for OS projects. GoDaddy claims to give away free certs. I contacted them twice via their web form, but they ignored me. I purchased the sagenb.org domain from them. Universities would be in a pretty good position to act as CAs for students and staff and might well get Firefox to support them if they did a job well. It only works for that university though, I guess... -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Fwd: modular composition M4RI
Paul Zimmerman wrote at #3376: Thank you very much Michael and Martin. It seems indeed you had some fun optimizing m4ri! Looking at the discussion, especially when I saw Gray code, I wondered whether the techniques we used to multiply polynomials over GF(2) might be useful too. See http://hal.inria.fr/inria-00188261/en. My initial interest was modular composition: Brent and Kung's 1978 Algo 2.1 enables one to perform a fast modular composition using fast matrix multiplication. In turn, modular composition enables to improve polynomial factorisation or irreducibility tests. Do you know if Sage implements modular composition, i.e, f(g) mod h over GF(p)[x]? Since I don't know the answer, I'm forwarding it to [sage-devel]. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: Fwd: modular composition M4RI
I don't know if SAGE implements this, either modular composition or decomposition. Bill. On 10 Jun, 13:02, Martin Albrecht [EMAIL PROTECTED] wrote: Paul Zimmerman wrote at #3376: Thank you very much Michael and Martin. It seems indeed you had some fun optimizing m4ri! Looking at the discussion, especially when I saw Gray code, I wondered whether the techniques we used to multiply polynomials over GF(2) might be useful too. See http://hal.inria.fr/inria-00188261/en. My initial interest was modular composition: Brent and Kung's 1978 Algo 2.1 enables one to perform a fast modular composition using fast matrix multiplication. In turn, modular composition enables to improve polynomial factorisation or irreducibility tests. Do you know if Sage implements modular composition, i.e, f(g) mod h over GF(p)[x]? Since I don't know the answer, I'm forwarding it to [sage-devel]. Cheers, Martin -- name: Martin Albrecht _pgp:http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x8EF0DC99 _www:http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] elliptic curve division polynomials
The following should be of interest to David Harvey, David Kohel, Chris Wuthrich and WIlliam Stein (at least!). Following from my reviewing of Chris's #3377 (torsion subgroups of elliptic curves over number fields) where I found a bug (see #3383) in William's new full_division_polynomial() code (see #3109): The bug was caused by some horrendous Grobner basis reduction in a 2-variable polynomial ring over a number field. I was able to eliminate it by reworking William's full_division_polynomial() to work in the genuine function field of the curve. Thus, if K is the base_ring of the curve I construct in order the polynomial ring K[x], then its field of fractions K(x), then -- via the polynomial ring K(x)[Y] -- the field K(x)(y) where y^2=polynomial in x is the equation of the curve. (I am currently assuming that the curve is in short Weierstrass form as WIlliam did, though that wilkl be fixed in due course). Elements g of that field have two components g[0] and g[1], both rational functions in x, representing g[0]+y*g[1]. It is possible though slightly awkward to evaluate such a function g at a point P. What works is lift(g).subs(Y=P[1]).subs(x=P[0]) Now full_division_polynomial(m) returns an element g of that field, which if m is odd happens to be a polynomial in x (no denominator, no y term, i.e. g[1]==0) and if m is even happens to be y times a poly on x (no denominator and g[0]==0). Using that I reworked multiplication_by_m() as necessary and hence division_points(). doctests all pass, and the example which previously failed in #3383 now passes. Problem 1: Over Q, multiplication_by_m(10) takes ages -- over 3 minutes! -- even with the x_only=True option. The time is almost all spent in dividing one element of QQ(x) by another. That is just a simple division of two rational functions (polynomials of degrees 99 and 100 with no common factor) -- possibly the time is taken computing their gcd? I know that ZZ[x] operations are faster than QQ[x] but it would be very ugly to try to detect this special case since the code is otherwise generic and works over any field (char. not 2 or 3 until we stop using short W. equations). Problem/question 2: looking at the code in ell_generic.py I find that there are now *3* different implementations of division polys of various kinds. (1) E.division_pol = E.torsion_pol is by David Kohel (2005-04-25) and returns a polynomial in x alone, with a factor of the 2-division poly in x when m is even. (2) E.full_division_pol is William's new code (which can be asked to call the preceding when m is odd) which returns a polynomial in x and y, i.e. in the 2-variable poly ring over K, which happens to be of the form p(x) or y*p(x) where p is a poly in x alone (but belonging to K[x,y]). (3) There is code which is all commented out due to David Harvey (2006-09-24) consisting of 3 functions pseudo_torsion_polynomial(), multiple_x_numerator(() and multiple_x_denominator(). The first is the same as before for odd m but for even m just omits the factor of the 2-division poly. I like this implementation: it uses a cache, and also the user supplies their own 'x' which need not be an indeterminate. This is *very* useful since it is expensive to compute (say) the 10th division poly as a polynomial and then substitute avalue for x, it is much faster to evaluate as you go along. The last two give the numerator and denominator of the x-coordinate of m*P, i.e. of the first rational function returned by William's multiplication_by_m(). [By the way, it is easy to get the y-coordinate from the x-coordinate: if the x-coord is X(x) then the y-coord is c*y*X'(x) where c is a constant. I think the constant is m in this case (look at the invariant differential). Does anyone know why those three functions are commented out? William, why did you write your own new functions instead of using these? Can we try to clean all this up once and for all? Would you trust me to do this? John --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: Compilation BUG for sage packages on Ubuntu 8.04 i386
I humbly apologize for bothering you with such a trivial problem, the libc6-dev package was missing on my installation. Iztok On Jun 9, 6:58 pm, mabshoff [EMAIL PROTECTED] wrote: On Jun 9, 2:43 am, IzI [EMAIL PROTECTED] wrote: Hi, I would prefer to submit the bug as a Trac issue, but was not able to subscribe. Steps to reproduce the problem: 1.) download and install SAGE to a 32bit (P4) Ubuntu 8.04 2.) wgethttp://www.sagemath.org/packages/experimental/PIL-1.1.5.spkg 3.) ./sage -i PIL-1.1.5.spkg 4.) check the first compilation error, it should be something like: /usr/lib/gcc/i486-linux-gnu/4.2.3/include/limits.h:122:61: error: limits.h: No such file or directory Could you post the actual error? PIL is experimental and the website of PIL seems to be down at the moment. There is also a somewhat more current release, i.e. 1.1.6. The problem is that limits.h is again included inside limits.h, since I do not understand the details, here is something that probably describes the problem: http://www.mail-archive.com/[EMAIL PROTECTED]/msg23823.html I did not have the same problem on an 64bit Gentoo, and I somehow managed to solve it on my laptop (Celeron P3, and Ubuntu 8.04) by recompiling SAGE from source. Since it took 7 hours, I would not call this a solution, Well, compiling 5,000,000 lines of code does take a while on a P3 :) but I must admit, the compilation went without problems. Without seeing the logs of the builds it is next to impossible to debug this. Do not send the logs via email, but post links so that people who are interested in solving this can download them. That being said it is most likely a local config problem since it works on one Ubuntu 8.04 install and not the other, so it will be hard to track down. IzI Cheers, Michael --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: elliptic curve division polynomials
On Jun 10, 2008, at 10:34 AM, John Cremona wrote: Problem/question 2: looking at the code in ell_generic.py I find that there are now *3* different implementations of division polys of various kinds. (1) E.division_pol = E.torsion_pol is by David Kohel (2005-04-25) and returns a polynomial in x alone, with a factor of the 2-division poly in x when m is even. (2) E.full_division_pol is William's new code (which can be asked to call the preceding when m is odd) which returns a polynomial in x and y, i.e. in the 2-variable poly ring over K, which happens to be of the form p(x) or y*p(x) where p is a poly in x alone (but belonging to K[x,y]). (3) There is code which is all commented out due to David Harvey (2006-09-24) consisting of 3 functions pseudo_torsion_polynomial(), multiple_x_numerator(() and multiple_x_denominator(). The first is the same as before for odd m but for even m just omits the factor of the 2-division poly. I like this implementation: it uses a cache, and also the user supplies their own 'x' which need not be an indeterminate. This is *very* useful since it is expensive to compute (say) the 10th division poly as a polynomial and then substitute avalue for x, it is much faster to evaluate as you go along. The last two give the numerator and denominator of the x-coordinate of m*P, i.e. of the first rational function returned by William's multiplication_by_m(). [By the way, it is easy to get the y-coordinate from the x-coordinate: if the x-coord is X(x) then the y-coord is c*y*X'(x) where c is a constant. I think the constant is m in this case (look at the invariant differential). Does anyone know why those three functions are commented out? William, why did you write your own new functions instead of using these? Can we try to clean all this up once and for all? Would you trust me to do this? I can't remember why they are commented out. However I should mention that there is yet *another* implementation of something very similar, see sage.schemes.elliptic_curves.padics, the function _multiply_point(). david --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: www.sagenb.com's SSL certificate updated
On 10 Jun, 07:46, William Stein [EMAIL PROTECTED] wrote: There would be no harm in contacting Verisign, Thawte or any of the other properly supported CA's and asking them if they would do a freebie, Show them your sponsers page, say they would be added etc. Great idea! Could you please do this? There is no point in me trying to do this - other than to ask them if they will do it, and I suspect you would have far more chance of getting them to agree to it than what I do. The problem with the cheap CA's (GoDaddy etc) is the browsers don't support them, so people will get a warning anyway. In that case, you might as well sign it yourself as Micky Mouse and not bother asking them for a free one for OS projects. GoDaddy claims to give away free certs. I contacted them twice via their web form, but they ignored me. I purchased the sagenb.org domain from them. I think you are missing the point of the SSL certificate. 1) Without an SSL certificate, you can't run an SSL web site. However, if this is all you want, you can generate your own for free, in no time at all. http://www.tc.umn.edu/~brams006/selfsign.html You basically set yourself us as a Cetificate Authority (CA), calling yourself whatever you want (George Bush, President of the USA if you want). You then create a certificate for the the Sage site, as your name, which gets signed by George Bush. It does not matter if its expired or not. However, when someone tries to access your web site, the browser will give a warning, since it does not trust the certificate authority (George Bush). 2) The next reason to have an SSL certificate, is so some user accessing your web site, is assured you are who you say you are. So you have to pay (usually at least) a trusted body to verify who you are. One could use Verisign for this. You could use GoDaddy too. There is one big difference between the certificate signed by George Bush, and the one by Verisign. All browsers will have the public key of Verisign and will trust your site if Verisign have signed it. The browsers will not trust the site if someone claiming to be George Bush signed it. Although I believe IE accepts sites if GoDaddy trusts them, Firefox does not. Clearly GoDaddy have not satisfied the Firefox developers that GoDaddy does sufficient to verify the identity of the site. . Universities would be in a pretty good position to act as CAs for students and staff and might well get Firefox to support them if they did a job well. It only works for that university though, I guess... If the university done adequte checks to verify the identity of the people they issue certificates to, the uni could approach Mozilla and ask their root certificate be added to Firefox. Assuming Mozilla agree, users will not get any warning message, no matter where they are. The Mozilla policy is here http://www.mozilla.org/projects/security/certs/policy/ In firefox at least, you can see who is trusted by going to Edit- Preferences Click advanced, Click Ceriicates Then click View Certificates Authorities. For my version at leasat, you will see Verisign there, but not GoDaddy. Hence I doubt there is much point in having a GoDaddy SSL certificate. But I believe M$ trists GoDaddy, so the GoDaddy root certificate is there. --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: elliptic curve division polynomials
2008/6/10 David Harvey [EMAIL PROTECTED]: I can't remember why they are commented out. I'll try removing the comments and see what happens! However I should mention that there is yet *another* implementation of something very similar, see sage.schemes.elliptic_curves.padics, the function _multiply_point(). I'll leave that well alone, since although there is some trivial code duplication that function has a very specific purpose. John david --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: elliptic curve division polynomials
On Tue, Jun 10, 2008 at 7:34 AM, John Cremona [EMAIL PROTECTED] wrote: The following should be of interest to David Harvey, David Kohel, Chris Wuthrich and WIlliam Stein (at least!). Following from my reviewing of Chris's #3377 (torsion subgroups of elliptic curves over number fields) where I found a bug (see #3383) in William's new full_division_polynomial() code (see #3109): The bug was caused by some horrendous Grobner basis reduction in a 2-variable polynomial ring over a number field. Is this a bug in Grobner basis or in my code that happens to use it? I was able to eliminate it by reworking William's full_division_polynomial() to work in the genuine function field of the curve. Thus, if K is the base_ring of the curve I construct in order the polynomial ring K[x], then its field of fractions K(x), then -- via the polynomial ring K(x)[Y] -- the field K(x)(y) where y^2=polynomial in x is the equation of the curve. (I am currently assuming that the curve is in short Weierstrass form as WIlliam did, though that wilkl be fixed in due course). Elements g of that field have two components g[0] and g[1], both rational functions in x, representing g[0]+y*g[1]. It is possible though slightly awkward to evaluate such a function g at a point P. What works is lift(g).subs(Y=P[1]).subs(x=P[0]) Now full_division_polynomial(m) returns an element g of that field, which if m is odd happens to be a polynomial in x (no denominator, no y term, i.e. g[1]==0) and if m is even happens to be y times a poly on x (no denominator and g[0]==0). Using that I reworked multiplication_by_m() as necessary and hence division_points(). doctests all pass, and the example which previously failed in #3383 now passes. Problem 1: Over Q, multiplication_by_m(10) takes ages -- over 3 minutes! -- even with the x_only=True option. The time is almost all spent in dividing one element of QQ(x) by another. That is just a simple division of two rational functions (polynomials of degrees 99 and 100 with no common factor) -- possibly the time is taken computing their gcd? I know that ZZ[x] operations are faster than QQ[x] but it would be very ugly to try to detect this special case since the code is otherwise generic and works over any field (char. not 2 or 3 until we stop using short W. equations). It seems like you need to investigate this a bit further. If it is really gcd, then we could just improve QQ[x]'s gcd code (e.g., clear denoms and call something in ZZ[x] for now; I don't know.) Problem/question 2: looking at the code in ell_generic.py I find that there are now *3* different implementations of division polys of various kinds. (1) E.division_pol = E.torsion_pol is by David Kohel (2005-04-25) and returns a polynomial in x alone, with a factor of the 2-division poly in x when m is even. (2) E.full_division_pol is William's new code (which can be asked to call the preceding when m is odd) which returns a polynomial in x and y, i.e. in the 2-variable poly ring over K, which happens to be of the form p(x) or y*p(x) where p is a poly in x alone (but belonging to K[x,y]). (3) There is code which is all commented out due to David Harvey (2006-09-24) consisting of 3 functions pseudo_torsion_polynomial(), multiple_x_numerator(() and multiple_x_denominator(). The first is the same as before for odd m but for even m just omits the factor of the 2-division poly. I like this implementation: it uses a cache, and also the user supplies their own 'x' which need not be an indeterminate. This is *very* useful since it is expensive to compute (say) the 10th division poly as a polynomial and then substitute avalue for x, it is much faster to evaluate as you go along. The last two give the numerator and denominator of the x-coordinate of m*P, i.e. of the first rational function returned by William's multiplication_by_m(). [By the way, it is easy to get the y-coordinate from the x-coordinate: if the x-coord is X(x) then the y-coord is c*y*X'(x) where c is a constant. I think the constant is m in this case (look at the invariant differential). Does anyone know why those three functions are commented out? No (since David Harvey doesn't know). William, why did you write your own new functions instead of using these? Since I didn't know how to use them to do what I wanted. Can we try to clean all this up once and for all? Would you trust me to do this? Yes. Yes. william --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: elliptic curve division polynomials
2008/6/10 William Stein [EMAIL PROTECTED]: On Tue, Jun 10, 2008 at 7:34 AM, John Cremona [EMAIL PROTECTED] wrote: The following should be of interest to David Harvey, David Kohel, Chris Wuthrich and WIlliam Stein (at least!). Following from my reviewing of Chris's #3377 (torsion subgroups of elliptic curves over number fields) where I found a bug (see #3383) in William's new full_division_polynomial() code (see #3109): The bug was caused by some horrendous Grobner basis reduction in a 2-variable polynomial ring over a number field. Is this a bug in Grobner basis or in my code that happens to use it? The latter. You coerce things into a ring of the form K[X,Y]/I where I is an ideal, in order to reduce them modulo the defining equation of the curve (which is the generator of I). That leads to a reduce(0 function in quotient_ring_element.py being called on the elements with respect to that ideal, which in turn leads to code in t-y_buchberger.py where the Error is raised. Since I is a principal ideal it should not be too hard to find its G. basis? I was able to eliminate it by reworking William's full_division_polynomial() to work in the genuine function field of the curve. Thus, if K is the base_ring of the curve I construct in order the polynomial ring K[x], then its field of fractions K(x), then -- via the polynomial ring K(x)[Y] -- the field K(x)(y) where y^2=polynomial in x is the equation of the curve. (I am currently assuming that the curve is in short Weierstrass form as WIlliam did, though that wilkl be fixed in due course). Elements g of that field have two components g[0] and g[1], both rational functions in x, representing g[0]+y*g[1]. It is possible though slightly awkward to evaluate such a function g at a point P. What works is lift(g).subs(Y=P[1]).subs(x=P[0]) Now full_division_polynomial(m) returns an element g of that field, which if m is odd happens to be a polynomial in x (no denominator, no y term, i.e. g[1]==0) and if m is even happens to be y times a poly on x (no denominator and g[0]==0). Using that I reworked multiplication_by_m() as necessary and hence division_points(). doctests all pass, and the example which previously failed in #3383 now passes. Problem 1: Over Q, multiplication_by_m(10) takes ages -- over 3 minutes! -- even with the x_only=True option. The time is almost all spent in dividing one element of QQ(x) by another. That is just a simple division of two rational functions (polynomials of degrees 99 and 100 with no common factor) -- possibly the time is taken computing their gcd? I know that ZZ[x] operations are faster than QQ[x] but it would be very ugly to try to detect this special case since the code is otherwise generic and works over any field (char. not 2 or 3 until we stop using short W. equations). It seems like you need to investigate this a bit further. If it is really gcd, then we could just improve QQ[x]'s gcd code (e.g., clear denoms and call something in ZZ[x] for now; I don't know.) It is definitely the gcd. I was able to avoid the slowdown by constructing the element of the fraction field L not by x=n/d (where n and d are the numer- and denominator), nor by x=L(n,d) but by x = sage.rings.fraction_field_element.FractionFieldElement(L,n,d,reduce=False) which forces the gcd not to be taken. I am pretty sure that at this point in the code we know that the polynomials are coprime anyway, so I would vote for the constructor of the form L(n,d) to have a flag reduce whcih defaults to True but can be set to False for situations like that. Problem/question 2: looking at the code in ell_generic.py I find that there are now *3* different implementations of division polys of various kinds. (1) E.division_pol = E.torsion_pol is by David Kohel (2005-04-25) and returns a polynomial in x alone, with a factor of the 2-division poly in x when m is even. (2) E.full_division_pol is William's new code (which can be asked to call the preceding when m is odd) which returns a polynomial in x and y, i.e. in the 2-variable poly ring over K, which happens to be of the form p(x) or y*p(x) where p is a poly in x alone (but belonging to K[x,y]). (3) There is code which is all commented out due to David Harvey (2006-09-24) consisting of 3 functions pseudo_torsion_polynomial(), multiple_x_numerator(() and multiple_x_denominator(). The first is the same as before for odd m but for even m just omits the factor of the 2-division poly. I like this implementation: it uses a cache, and also the user supplies their own 'x' which need not be an indeterminate. This is *very* useful since it is expensive to compute (say) the 10th division poly as a polynomial and then substitute avalue for x, it is much faster to evaluate as you go along. The last two give the numerator and denominator of the x-coordinate of m*P, i.e. of the first rational function returned by William's
[sage-devel] Re: elliptic curve division polynomials
On Tue, Jun 10, 2008 at 9:59 AM, John Cremona [EMAIL PROTECTED] wrote: 2008/6/10 William Stein [EMAIL PROTECTED]: On Tue, Jun 10, 2008 at 7:34 AM, John Cremona [EMAIL PROTECTED] wrote: The following should be of interest to David Harvey, David Kohel, Chris Wuthrich and WIlliam Stein (at least!). Following from my reviewing of Chris's #3377 (torsion subgroups of elliptic curves over number fields) where I found a bug (see #3383) in William's new full_division_polynomial() code (see #3109): The bug was caused by some horrendous Grobner basis reduction in a 2-variable polynomial ring over a number field. Is this a bug in Grobner basis or in my code that happens to use it? The latter. You coerce things into a ring of the form K[X,Y]/I where I is an ideal, in order to reduce them modulo the defining equation of the curve (which is the generator of I). That leads to a reduce(0 function in quotient_ring_element.py being called on the elements with respect to that ideal, which in turn leads to code in t-y_buchberger.py where the Error is raised. Since I is a principal ideal it should not be too hard to find its G. basis? It seems to me that you just wrote the bug is in my code, but then when you described the bug it seems to be that it occurs in Martin Albrecht's Toy Buchburger implementation? I was able to eliminate it by reworking William's full_division_polynomial() to work in the genuine function field of the curve. Thus, if K is the base_ring of the curve I construct in order the polynomial ring K[x], then its field of fractions K(x), then -- via the polynomial ring K(x)[Y] -- the field K(x)(y) where y^2=polynomial in x is the equation of the curve. (I am currently assuming that the curve is in short Weierstrass form as WIlliam did, though that wilkl be fixed in due course). Elements g of that field have two components g[0] and g[1], both rational functions in x, representing g[0]+y*g[1]. It is possible though slightly awkward to evaluate such a function g at a point P. What works is lift(g).subs(Y=P[1]).subs(x=P[0]) Now full_division_polynomial(m) returns an element g of that field, which if m is odd happens to be a polynomial in x (no denominator, no y term, i.e. g[1]==0) and if m is even happens to be y times a poly on x (no denominator and g[0]==0). Using that I reworked multiplication_by_m() as necessary and hence division_points(). doctests all pass, and the example which previously failed in #3383 now passes. Problem 1: Over Q, multiplication_by_m(10) takes ages -- over 3 minutes! -- even with the x_only=True option. The time is almost all spent in dividing one element of QQ(x) by another. That is just a simple division of two rational functions (polynomials of degrees 99 and 100 with no common factor) -- possibly the time is taken computing their gcd? I know that ZZ[x] operations are faster than QQ[x] but it would be very ugly to try to detect this special case since the code is otherwise generic and works over any field (char. not 2 or 3 until we stop using short W. equations). It seems like you need to investigate this a bit further. If it is really gcd, then we could just improve QQ[x]'s gcd code (e.g., clear denoms and call something in ZZ[x] for now; I don't know.) It is definitely the gcd. I was able to avoid the slowdown by constructing the element of the fraction field L not by x=n/d (where n and d are the numer- and denominator), nor by x=L(n,d) but by x = sage.rings.fraction_field_element.FractionFieldElement(L,n,d,reduce=False) which forces the gcd not to be taken. I am pretty sure that at this point in the code we know that the polynomials are coprime anyway, so I would vote for the constructor of the form L(n,d) to have a flag reduce whcih defaults to True but can be set to False for situations like that. +1 Problem/question 2: looking at the code in ell_generic.py I find that there are now *3* different implementations of division polys of various kinds. (1) E.division_pol = E.torsion_pol is by David Kohel (2005-04-25) and returns a polynomial in x alone, with a factor of the 2-division poly in x when m is even. (2) E.full_division_pol is William's new code (which can be asked to call the preceding when m is odd) which returns a polynomial in x and y, i.e. in the 2-variable poly ring over K, which happens to be of the form p(x) or y*p(x) where p is a poly in x alone (but belonging to K[x,y]). (3) There is code which is all commented out due to David Harvey (2006-09-24) consisting of 3 functions pseudo_torsion_polynomial(), multiple_x_numerator(() and multiple_x_denominator(). The first is the same as before for odd m but for even m just omits the factor of the 2-division poly. I like this implementation: it uses a cache, and also the user supplies their own 'x' which need not be an indeterminate. This is *very* useful since it is expensive to compute (say)
[sage-devel] Re: Compilation BUG for sage packages on Ubuntu 8.04 i386
On Tue, Jun 10, 2008 at 7:41 AM, IzI [EMAIL PROTECTED] wrote: Hi Iztok, I humbly apologize for bothering you with such a trivial problem, the libc6-dev package was missing on my installation. No problem and don't worry about it since everybody around here has had something very similar go wrong :) Iztok Cheers, Michael SNIP --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: elliptic curve division polynomials
2008/6/10 William Stein [EMAIL PROTECTED]: On Tue, Jun 10, 2008 at 9:59 AM, John Cremona [EMAIL PROTECTED] wrote: 2008/6/10 William Stein [EMAIL PROTECTED]: On Tue, Jun 10, 2008 at 7:34 AM, John Cremona [EMAIL PROTECTED] wrote: The following should be of interest to David Harvey, David Kohel, Chris Wuthrich and WIlliam Stein (at least!). Following from my reviewing of Chris's #3377 (torsion subgroups of elliptic curves over number fields) where I found a bug (see #3383) in William's new full_division_polynomial() code (see #3109): The bug was caused by some horrendous Grobner basis reduction in a 2-variable polynomial ring over a number field. Is this a bug in Grobner basis or in my code that happens to use it? The latter. You coerce things into a ring of the form K[X,Y]/I where I is an ideal, in order to reduce them modulo the defining equation of the curve (which is the generator of I). That leads to a reduce(0 function in quotient_ring_element.py being called on the elements with respect to that ideal, which in turn leads to code in t-y_buchberger.py where the Error is raised. Since I is a principal ideal it should not be too hard to find its G. basis? It seems to me that you just wrote the bug is in my code, but then when you described the bug it seems to be that it occurs in Martin Albrecht's Toy Buchburger implementation? You are right, I should have said the former. I was able to eliminate it by reworking William's full_division_polynomial() to work in the genuine function field of the curve. Thus, if K is the base_ring of the curve I construct in order the polynomial ring K[x], then its field of fractions K(x), then -- via the polynomial ring K(x)[Y] -- the field K(x)(y) where y^2=polynomial in x is the equation of the curve. (I am currently assuming that the curve is in short Weierstrass form as WIlliam did, though that wilkl be fixed in due course). Elements g of that field have two components g[0] and g[1], both rational functions in x, representing g[0]+y*g[1]. It is possible though slightly awkward to evaluate such a function g at a point P. What works is lift(g).subs(Y=P[1]).subs(x=P[0]) Now full_division_polynomial(m) returns an element g of that field, which if m is odd happens to be a polynomial in x (no denominator, no y term, i.e. g[1]==0) and if m is even happens to be y times a poly on x (no denominator and g[0]==0). Using that I reworked multiplication_by_m() as necessary and hence division_points(). doctests all pass, and the example which previously failed in #3383 now passes. Problem 1: Over Q, multiplication_by_m(10) takes ages -- over 3 minutes! -- even with the x_only=True option. The time is almost all spent in dividing one element of QQ(x) by another. That is just a simple division of two rational functions (polynomials of degrees 99 and 100 with no common factor) -- possibly the time is taken computing their gcd? I know that ZZ[x] operations are faster than QQ[x] but it would be very ugly to try to detect this special case since the code is otherwise generic and works over any field (char. not 2 or 3 until we stop using short W. equations). It seems like you need to investigate this a bit further. If it is really gcd, then we could just improve QQ[x]'s gcd code (e.g., clear denoms and call something in ZZ[x] for now; I don't know.) It is definitely the gcd. I was able to avoid the slowdown by constructing the element of the fraction field L not by x=n/d (where n and d are the numer- and denominator), nor by x=L(n,d) but by x = sage.rings.fraction_field_element.FractionFieldElement(L,n,d,reduce=False) which forces the gcd not to be taken. I am pretty sure that at this point in the code we know that the polynomials are coprime anyway, so I would vote for the constructor of the form L(n,d) to have a flag reduce whcih defaults to True but can be set to False for situations like that. +1 Problem/question 2: looking at the code in ell_generic.py I find that there are now *3* different implementations of division polys of various kinds. (1) E.division_pol = E.torsion_pol is by David Kohel (2005-04-25) and returns a polynomial in x alone, with a factor of the 2-division poly in x when m is even. (2) E.full_division_pol is William's new code (which can be asked to call the preceding when m is odd) which returns a polynomial in x and y, i.e. in the 2-variable poly ring over K, which happens to be of the form p(x) or y*p(x) where p is a poly in x alone (but belonging to K[x,y]). (3) There is code which is all commented out due to David Harvey (2006-09-24) consisting of 3 functions pseudo_torsion_polynomial(), multiple_x_numerator(() and multiple_x_denominator(). The first is the same as before for odd m but for even m just omits the factor of the 2-division poly. I like this implementation: it uses a cache, and also the user supplies their own 'x'
[sage-devel] Re: [Sage Bug Report] sympy matix doesn't likes sage.integer
Riccardo Gori wrote: Hello, Hi Riccardo, I have also forwarded your email to sage-devel. In SAGE-3.0.2 with a Intel Mac OSX 10.5 I found the following bug: If I create a sympy matrix and if I try to access it it gives me an error. Step to reproduce: sage: import sympy sage: M = sympy.Matrix( (2,3) ) sage: sympy.pprint M[0] Traceback (most recent call last): File stdin, line 1, in module File /Users/riccardo/.sage/sage_notebook/worksheets/admin/3/code/299.py, line 7, in module M[Integer(1)] File /Applications/sage/local/lib/python2.5/site-packages/sympy/plotting/, line 1, in module File /Applications/sage/local/lib/python2.5/site-packages/sympy/matrices/matrices.py, line 150, in __getitem__ assert len(key) == 2 TypeError: object of type 'sage.rings.integer.Integer' has no len() sage: sympy.pprint M[int(0)] 2 This is most likely an integration issue and I assume that if you use Python ints the problem will go away. One aspect there is certainly that Sympy is not integrated into Sage's coercion model. Thank you Riccardo Cheers, Michael --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: [Sage Bug Report] sympy functions doesn't works well with numbers
Riccardo Gori wrote: Hello, Hi Riccardo, thanks for the bug report. I have forwarded it to sage-devel. Cheers, Michael In SAGE-3.0.2 with a Intel Mac OSX 10.5 I found the following bug: Trying to evaluate a sympy function gives a wrong result. With sympy in a python shell everything works well. To reproduce: sage: import sympy sage: sympy.sin(1.1) sin(1) sage: sympy.sin(float(1.2)) sin(1) sage: sympy.sin(1.3) sin(1.300044408920985) sage: sympy.sin(float(1.4)) sin(1.39991118215803) I didn't find a way to get a correct result even with float(). Thank you Riccardo --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] degrees() missing for y= PolynomialRing(QQ,3,'y').objgens()?
The following popped up at http://groups.google.com/group/sage-combinat-devel/t/3d048be6e156a877 sage: R1,x = PolynomialRing(ZZ,3,'x').objgens();R1 Multivariate Polynomial Ring in x0, x1, x2 over Integer Ring sage: p = 3*x[0]*x[1]*x[1]*x[2];p 3*x0*x1^2*x2 sage: p.degrees() (1, 2, 1) sage: R2,y = PolynomialRing(QQ,3,'y').objgens();R2 Multivariate Polynomial Ring in y0, y1, y2 over Rational Field sage: q = 3*y[0]*y[1]*y[1]*y[2];q 3*y0*y1^2*y2 sage: q.degrees() --- type 'exceptions.AttributeError'Traceback (most recent call last) /Users/kurtluoto/Documents/Research/Sagedev/ipython console in module() type 'exceptions.AttributeError': 'sage.rings.polynomial.multi_polynomial_libsingular' object has no attribute 'degrees' sage: Is the missing implementation of degrees() for the rational case an oversight or I am just feeling dumb this day? Cheers, Michael --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: [Sage Bug Report] sympy matix doesn't likes sage.integer
On Tue, Jun 10, 2008 at 2:04 PM, mabshoff [EMAIL PROTECTED] wrote: Riccardo Gori wrote: Hello, Hi Riccardo, I have also forwarded your email to sage-devel. In SAGE-3.0.2 with a Intel Mac OSX 10.5 I found the following bug: If I create a sympy matrix and if I try to access it it gives me an error. Step to reproduce: sage: import sympy sage: M = sympy.Matrix( (2,3) ) sage: sympy.pprint M[0] Traceback (most recent call last): File stdin, line 1, in module File /Users/riccardo/.sage/sage_notebook/worksheets/admin/3/code/299.py, line 7, in module M[Integer(1)] File /Applications/sage/local/lib/python2.5/site-packages/sympy/plotting/, line 1, in module File /Applications/sage/local/lib/python2.5/site-packages/sympy/matrices/matrices.py, line 150, in __getitem__ assert len(key) == 2 TypeError: object of type 'sage.rings.integer.Integer' has no len() sage: sympy.pprint M[int(0)] 2 This is most likely an integration issue and I assume that if you use Python ints the problem will go away. One aspect there is certainly that Sympy is not integrated into Sage's coercion model. This is a bug in Sympy: sage: import sympy sage: M = sympy.Matrix( (2,3) ) sage: M [2] [3] sage: M[0] TypeError Traceback (most recent call last) ... Sympy *should* call the __index__ method on the input object in __getitem__, but it doesn't. The __index__ method is supported by Sage integers, and was added (by Travis Oliphant) in Python 2.5 for exactly the above reason. I've cc'd this email to Ondrej Certik and hope he can post a bug report to the sympy bug tracker. -- William --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: [Sage Bug Report] sympy matix doesn't likes sage.integer
On Jun 10, 5:27 pm, William Stein [EMAIL PROTECTED] wrote: On Tue, Jun 10, 2008 at 2:04 PM, mabshoff [EMAIL PROTECTED] wrote: Riccardo Gori wrote: Hello, Hi Riccardo, I have also forwarded your email to sage-devel. In SAGE-3.0.2 with a Intel Mac OSX 10.5 I found the following bug: If I create a sympy matrix and if I try to access it it gives me an error. Step to reproduce: sage: import sympy sage: M = sympy.Matrix( (2,3) ) sage: sympy.pprint M[0] Traceback (most recent call last): File stdin, line 1, in module File /Users/riccardo/.sage/sage_notebook/worksheets/admin/3/code/299.py, line 7, in module M[Integer(1)] File /Applications/sage/local/lib/python2.5/site-packages/sympy/plotting/, line 1, in module File /Applications/sage/local/lib/python2.5/site-packages/sympy/matrices/matrices.py, line 150, in __getitem__ assert len(key) == 2 TypeError: object of type 'sage.rings.integer.Integer' has no len() sage: sympy.pprint M[int(0)] 2 This is most likely an integration issue and I assume that if you use Python ints the problem will go away. One aspect there is certainly that Sympy is not integrated into Sage's coercion model. Hi, This is a bug in Sympy: we do not ship the latest Sympy release and some very similar sounding issue was fixed in the last release, so maybe somebody should verify that it is still broken in the latest release and then file a bug report with Sympy. Otherwise we should upgrade Sympy in Sage to the latest release. sage: import sympy sage: M = sympy.Matrix( (2,3) ) sage: M [2] [3] sage: M[0] TypeError Traceback (most recent call last) ... Sympy *should* call the __index__ method on the input object in __getitem__, but it doesn't. The __index__ method is supported by Sage integers, and was added (by Travis Oliphant) in Python 2.5 for exactly the above reason. I've cc'd this email to Ondrej Certik and hope he can post a bug report to the sympy bug tracker. -- William Cheers, Michael --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
[sage-devel] Re: extending of notebook interface
On Wed, May 28, 2008 at 8:25 PM, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: OK. Source code seems reasonably readable. I'll start playing with the code, and see where I'll end up. Have you guys got anywhere? As was mentioned before, starting small is often a very good idea. William On 29 svi, 03:10, Timothy Clemans [EMAIL PROTECTED] wrote: Hi, Thanks for showing your interest in working on the Notebook. I'm one of the Notebook developers. I did some work on some an administrator portal over a week ago however I forgot about it, and it was deleted today when I was cleaning up my home directory. I had implemented an administration page with a frontend to banning individual users from logging in. I don't plan on writing new code until after the work I've already done on some other Notebook stuff has been merged into Sage, seehttp://groups.google.com/group/sage-devel/browse_thread/thread/624262 You could get started on Notebook development by reviewing one of those. E-mail Michael Abshoff at [EMAIL PROTECTED] for a TRAC account so you can add and contribute to tickets. We have a tutorial on doing general development athttp://sagemath.org/doc/html/prog/index.html. The Notebook source code is in sage/server/notebook, seehttp://www.sagemath.org/hg/sage-main/file/6a6766d05f3b/sage/server/no I recommend working on implementing your administration ideas as small projects. For example the user settings page in the Notebook now was originally just a change password page and then a more general page was created out of it, seehttp://trac.sagemath.org/sage_trac/ticket/3213. Then on top of that there is a patch up that implements better styling for that page and also a change auto-save interval control. Timothy On Wed, May 28, 2008 at 5:22 PM, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Hi, I would like to incorporate Sage in a web-application which, among other things, enables remote editing and executing of programs in various programming languages and mathematical/engineering tools, written by the group of researchers from our university. Specifically, we would like to extend the capabilities of notebook so that we can add/delete users and their data programatically while the Sage web server is running. Perhaps it would be also interesting to include user management in the Setting part of the notebook web interface? I have some experience in Python, but none in Twisted framework. Could you give me some hints where to look in Sage source? Do you already have some plans in this direction? Thanks for a great application. Ivica Nakic Assistant Professor of Mathematics University of Zagreb Croatia -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~-~--~~~---~--~~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~--~~~~--~~--~--~---
