[sage-support] Re: Solve system of non linear equations
I take it you mean polynomial equations: sage: AA.x,y = AffineSpace(GF(2),2) sage: S = AA.subscheme(x^2+y^2) sage: S.point_set().points() [(0, 0), (1, 1)] On Saturday, December 8, 2012 6:14:19 AM UTC, Santanu wrote: I have a system of non linear equations over GF(2). How to solve them in Sage? -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Re: Solve system of non linear equations
Or compute a Gröbner basis:
sage: P.x,y = BooleanPolynomialRing()
sage: Ideal(x^2 + y^2).groebner_basis()
[x + y]
sage: Ideal(x^2 + y^2).variety()
[{y: 0, x: 0}, {y: 1, x: 1}]
On Saturday 08 Dec 2012, Volker Braun wrote:
I take it you mean polynomial equations:
sage: AA.x,y = AffineSpace(GF(2),2)
sage: S = AA.subscheme(x^2+y^2)
sage: S.point_set().points()
[(0, 0), (1, 1)]
On Saturday, December 8, 2012 6:14:19 AM UTC, Santanu wrote:
I have a system of non linear equations over GF(2). How to solve
them in Sage?
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinralbre...@jabber.ccc.de
--
You received this message because you are subscribed to the Google Groups
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Re: Solve system of non linear equations
Thank you. But when I try to solve
f1=x1 + x2 + x4 + x10 + x31 + x43 + x56 ,
f2=x2 + x3 + x5 + x11 + x32 +x44 + x57,
it becomes very slow. Is there any faster approach like
F4 algorithm available in Sage?
On 8 December 2012 17:25, Martin Albrecht martinralbre...@googlemail.comwrote:
Or compute a Gröbner basis:
sage: P.x,y = BooleanPolynomialRing()
sage: Ideal(x^2 + y^2).groebner_basis()
[x + y]
sage: Ideal(x^2 + y^2).variety()
[{y: 0, x: 0}, {y: 1, x: 1}]
On Saturday 08 Dec 2012, Volker Braun wrote:
I take it you mean polynomial equations:
sage: AA.x,y = AffineSpace(GF(2),2)
sage: S = AA.subscheme(x^2+y^2)
sage: S.point_set().points()
[(0, 0), (1, 1)]
On Saturday, December 8, 2012 6:14:19 AM UTC, Santanu wrote:
I have a system of non linear equations over GF(2). How to solve
them in Sage?
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinralbre...@jabber.ccc.de
--
You received this message because you are subscribed to the Google Groups
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
--
You received this message because you are subscribed to the Google Groups
sage-support group.
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.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] solving Diophantine equations in Sage
Hello, is there a way to solve Diophantine equations in Sage? If not a general method, perhaps at least some special cases. There is some interest in solving such equations in Maxima -- I am daydreaming about porting whatever implementation Sage has. Is there a generally-accepted more-or-less best method these days? (Whether it is implemented in Sage or not.) There is this web page, http://www.alpertron.com.ar/METHODS.HTM, which describes a method, and this one, http://www.alpertron.com.ar/JQUAD.HTM, which has a calculator. Would anyone care to comment on the suitability of either one as the basis for an implementation? Pointers to any other resources would be interesting. best Robert Dodier -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] solving Diophantine equations in Sage
Hello. There is no general method : see this page http://mathworld.wolfram.com/DiophantineEquation.html Best regards. C. 2012/12/8 Robert Dodier robert.dod...@gmail.com Hello, is there a way to solve Diophantine equations in Sage? If not a general method, perhaps at least some special cases. There is some interest in solving such equations in Maxima -- I am daydreaming about porting whatever implementation Sage has. Is there a generally-accepted more-or-less best method these days? (Whether it is implemented in Sage or not.) There is this web page, http://www.alpertron.com.ar/METHODS.HTM, which describes a method, and this one, http://www.alpertron.com.ar/JQUAD.HTM, which has a calculator. Would anyone care to comment on the suitability of either one as the basis for an implementation? Pointers to any other resources would be interesting. best Robert Dodier -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Re: Solve system of non linear equations
On Saturday, December 8, 2012 11:07:31 AM UTC-6, Santanu wrote: Thank you. But when I try to solve f1=x1 + x2 + x4 + x10 + x31 + x43 + x56 , f2=x2 + x3 + x5 + x11 + x32 +x44 + x57, it becomes very slow. Is there any faster approach like F4 algorithm available in Sage? F4 is not yet available in Sage; as far as I know, we're waiting for upstream (Singular) to implement it. They've been working on it very hard for quite some time, because they're trying to do it right, and it's not as easy as one might think. Last I heard, they had both F4 and an F5-like algorithm with respectable performance in an internal development branch, but they had to integrate it with the regular Singular branch. It's been a huge effort to do this, since memory management other tricky issues come into play. Daniel Cabarcas wrote an open-source implementation of F4 for his Master's Thesis, which you might be able to find online. Bjarke Roune Michael Stillman described an open-source F5-like algorithm at ISSAC 2012, and gave an address where you can download it in the paper. All that said, when I look at your system, I wonder if something's wrong with the formatting, because it looks to me as if it's either linear or univariate. Is that the case? regards john perry -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] Re: solving Diophantine equations in Sage
Solving a linear diophantine equation is an application of the Smith form. A quadratic diophantine equation can be solved with the Hasse-Minkowski theorem, though thats is definitely more advanced (http://en.wikipedia.org/wiki/Hasse%E2%80%93Minkowski_theorem) If its not one of these cases then you are pretty much out of luck ;-) On Saturday, December 8, 2012 5:46:00 PM UTC, Robert Dodier wrote: Hello, is there a way to solve Diophantine equations in Sage? -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
[sage-support] Re: solving Diophantine equations in Sage
On 2012-12-08, Volker Braun vbraun.n...@gmail.com wrote: Solving a linear diophantine equation is an application of the Smith form. A quadratic diophantine equation can be solved with the Hasse-Minkowski theorem, though thats is definitely more advanced Thanks for the info. Are there implementations of these approaches in Sage or any upstream project? (e.g. PARI/GP, Singular, I don't know.) best, Robert Dodier -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: Re: [sage-support] Re: Solve system of non linear equations
We are talking about the Boolean polynomial ring here, right? So an F4 style algorithm is used by default (subject to some heuristics). To emphasise you'd have to construct your ring using the BooleanPolynomialRing constructor. On Saturday 08 Dec 2012, john_perry_usm wrote: On Saturday, December 8, 2012 11:07:31 AM UTC-6, Santanu wrote: Thank you. But when I try to solve f1=x1 + x2 + x4 + x10 + x31 + x43 + x56 , f2=x2 + x3 + x5 + x11 + x32 +x44 + x57, it becomes very slow. Is there any faster approach like F4 algorithm available in Sage? F4 is not yet available in Sage; as far as I know, we're waiting for upstream (Singular) to implement it. They've been working on it very hard for quite some time, because they're trying to do it right, and it's not as easy as one might think. Last I heard, they had both F4 and an F5-like algorithm with respectable performance in an internal development branch, but they had to integrate it with the regular Singular branch. It's been a huge effort to do this, since memory management other tricky issues come into play. Daniel Cabarcas wrote an open-source implementation of F4 for his Master's Thesis, which you might be able to find online. Bjarke Roune Michael Stillman described an open-source F5-like algorithm at ISSAC 2012, and gave an address where you can download it in the paper. All that said, when I look at your system, I wonder if something's wrong with the formatting, because it looks to me as if it's either linear or univariate. Is that the case? regards john perry Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=getsearch=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Re: solving Diophantine equations in Sage
On Dec 8, 2012, at 7:27 PM, Volker Braun vbraun.n...@gmail.com wrote: Solving a linear diophantine equation is an application of the Smith form. A quadratic diophantine equation can be solved with the Hasse-Minkowski theorem, though thats is definitely more advanced (http://en.wikipedia.org/wiki/Hasse%E2%80%93Minkowski_theorem) If its not one of these cases then you are pretty much out of luck ;-) I know basically nothing about Diophantine equations, but they have come up in my research a few times. Is there some sort of database of which equations have been solved (or not). I'm thinking something along the lines of the OEIS that would allow you to search for an equation to find out what could be said about it. I couldn't find any such thing on google, but it seems nearly inconceivable to me that such a thing wouldn't exist. Or are number theorists just born knowing this stuff. :-) -Ivan -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Re: solving Diophantine equations in Sage
On Saturday, December 8, 2012 7:03:48 PM UTC, Ivan Andrus wrote: Or are number theorists just born knowing this stuff. :-) Beats me, I'm just a physicist dabbling in computer programming ;-) -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Re: solving Diophantine equations in Sage
On Dec 8, 2012 10:27 AM, Volker Braun vbraun.n...@gmail.com wrote: Solving a linear diophantine equation is an application of the Smith form. A quadratic diophantine equation can be solved with the Hasse-Minkowski theorem, though thats is definitely more advanced ( http://en.wikipedia.org/wiki/Hasse%E2%80%93Minkowski_theorem) If its not one of these cases then you are pretty much out of luck ;-) Elliptic curves (cubic plane curves) are another major case with a developed theory. This stuff basically *is* number theory... and as such, Sage and Magma are pretty powerful for this, far ahead of anything else... On Saturday, December 8, 2012 5:46:00 PM UTC, Robert Dodier wrote: Hello, is there a way to solve Diophantine equations in Sage? -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en. -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] solving Diophantine equations in Sage
On Sat, Dec 08, 2012 at 05:46:00PM +, Robert Dodier wrote: Hello, is there a way to solve Diophantine equations in Sage? If not a general method, perhaps at least some special cases. There is some interest in solving such equations in Maxima -- I am daydreaming about porting whatever implementation Sage has. Is there a generally-accepted more-or-less best method these days? (Whether it is implemented in Sage or not.) There is this web page, http://www.alpertron.com.ar/METHODS.HTM, which describes a method, and this one, http://www.alpertron.com.ar/JQUAD.HTM, which has a calculator. Would anyone care to comment on the suitability of either one as the basis for an implementation? Pointers to any other resources would be interesting. best Robert Dodier pari/gp which is included in sage can solve the special case of Thue equations. In pari console: th=thueinit(x^5-2,1);\\x^5-2*y^5, ,1 is for unconditional result t=thue(th,65)\\x^5-2*y^5=65 %7 = [[1, -2]] If you want to work from sage the above example is: sage: AA.x=QQ[] sage: th=gp.thueinit(x^5-2,1) sage: gp.thue(th,65) [[1, -2]] -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
Re: [sage-support] Solve system of non linear equations
On Sat, Dec 08, 2012 at 11:44:19AM +0530, Santanu Sarkar wrote: Dear all, I have a system of non linear equations over GF(2). How to solve them in Sage? If you need to solve large nonlinear systems over GF(2) and don't insist on using sage I suspect a better choice is to convert them to conjunctive normal form (CNF) and then use state of the art SAT solver like lingeling/cryptominisat. There are sage programs for converting ANF to CNF, don't know if they are in vanilla sage. -- You received this message because you are subscribed to the Google Groups sage-support group. 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. Visit this group at http://groups.google.com/group/sage-support?hl=en.
