ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 23 Jun 2013 14:05:37 -0500Solving system of polynomial equation over finite fieldhttp://ask.sagemath.org/question/10270/solving-system-of-polynomial-equation-over-finite-field/Hello,
I am working in multivariate polynomial rings over small finite fields (with less then 15, or currently less than 10 elements). I have an algorithm, that outputs a system of equations. I need to find out if the system has a solution and if so, to find one. I am using calculation of groebner basis for this. But since my system typically has 20 or more variables and quite complicated polynomials, it seems that SINGULAR has problem to find the basis in reasonable time. Is there a way to speed up the calculation? For example, since I work in finite field, I can try all possible values for some variable. This simplifies the system and in some cases it seems to really help SINGULAR. But I can do that for only a very few variables.
Currently I work in PolynomialRing and before the grobner basis algorithm, I reduce my polynomials by FieldIdeal (x_0^n - x_0, ..., x_m^n - x_m) of the polynomial ring and add this equations to the system, to force the solution in the finite field.
I tried to work in the quotient ring from the start, but it looks like it slowed down my whole algorithm and also slowed down the computation of the groebner basis (which is a little suprising for me).
I found that for GF(2) PolyBoRi is optimized for the kind of work I need, but I am not restricted to GF(2). Is there something similar for other finite fields?
I would appreciate any tips how to speed up the whole process. Thank you.Sun, 23 Jun 2013 04:16:01 -0500http://ask.sagemath.org/question/10270/solving-system-of-polynomial-equation-over-finite-field/Answer by Volker Braun for <p>Hello,</p>
<p>I am working in multivariate polynomial rings over small finite fields (with less then 15, or currently less than 10 elements). I have an algorithm, that outputs a system of equations. I need to find out if the system has a solution and if so, to find one. I am using calculation of groebner basis for this. But since my system typically has 20 or more variables and quite complicated polynomials, it seems that SINGULAR has problem to find the basis in reasonable time. Is there a way to speed up the calculation? For example, since I work in finite field, I can try all possible values for some variable. This simplifies the system and in some cases it seems to really help SINGULAR. But I can do that for only a very few variables.</p>
<p>Currently I work in PolynomialRing and before the grobner basis algorithm, I reduce my polynomials by FieldIdeal (x_0^n - x_0, ..., x_m^n - x_m) of the polynomial ring and add this equations to the system, to force the solution in the finite field.
I tried to work in the quotient ring from the start, but it looks like it slowed down my whole algorithm and also slowed down the computation of the groebner basis (which is a little suprising for me).
I found that for GF(2) PolyBoRi is optimized for the kind of work I need, but I am not restricted to GF(2). Is there something similar for other finite fields?</p>
<p>I would appreciate any tips how to speed up the whole process. Thank you.</p>
http://ask.sagemath.org/question/10270/solving-system-of-polynomial-equation-over-finite-field/?answer=15126#post-id-15126There isn't really a magic bullet that solves this. If your equations have some additional structure then you can definitely use that to your advantage, but it really depends on what you have. The first thing to try would be different monomial orders, e.g. lexicographic with the "easy to solve for" variables at the top.Sun, 23 Jun 2013 14:05:37 -0500http://ask.sagemath.org/question/10270/solving-system-of-polynomial-equation-over-finite-field/?answer=15126#post-id-15126