Singular https://www.singular.uni-kl.de/forum/ |
|
Solving systems of polynomials over GF(2) https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1908 |
Page 1 of 1 |
Author: | ellisto [ Mon Feb 21, 2011 12:36 am ] |
Post subject: | Solving systems of polynomials over GF(2) |
Is there any way to solve systems of polynomials over GF(2) (or any small finite field) ? I found the example on solving systems of polynomials using solve.lib, but that only works over fields with characteristic 0, and the methods in primdec.lib only work over fields with either char=0 or over very large finite fields. Are there any methods in place for small finite fields? |
Author: | gorzel [ Tue Feb 22, 2011 4:20 pm ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
Use the command facstd and enable the option(redSB) which simplfies the result further. An example: Code: > ring r=2,(x,y,z),dp; > ideal I = xy-z2,x+y+z,z2+y; > facstd (I); // the result looks still complicated, since ... [1]: _[1]=y _[2]=x+y+z _[3]=z2+y [2]: _[1]=y+z+1 _[2]=x+y+z _[3]=z2+y > option(); // the option redSB is not enabled //options: redTail redThrough redefine loadLib usage prompt notWarnSB > option(redSB); / computed a reduced Groebner basis > facstd (I); // now the result is clear [1]: _[1]=z _[2]=y _[3]=x [2]: _[1]=y+z+1 _[2]=x+1 _[3]=z2+z+1 The first solution is the orgin (x,y,z) = (0,0,0), the second solution is defined in algebraic extension of degree 2 over F_2. |
Author: | ellisto [ Fri Mar 04, 2011 8:52 pm ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
Fantastic, thank you! |
Author: | ellisto [ Mon Mar 28, 2011 8:16 pm ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
Do you know how one could programmatically get the solutions? I mean, the method you showed gives a nice simplification that we can look at and can find the solution easily, but is there any way we could tell singular Code: solve(I) and have it print out the solutions, e.g. Code: [1]: x = 0; y = 0; z = 0; ... Again, such methods exist for fields of characteristic 0, but I cannot find anything about working over finite fields. |
Author: | gorzel [ Tue Mar 29, 2011 5:56 pm ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
ellisto wrote: Again, such methods exist for fields of characteristic 0, but I cannot find anything about working over finite fields. Which command does this provide in char = 0 ? There is one solution comes be generating LaTeX-output: Define and set int TeXwidth = 0; then ideals will be set as equation systems: Code: > ring r=2,(x,y,z),dp; > ideal I = xy-z2,x+y+z,z2+y; > option(redSB); > int TeXwidth =0; > option(redSB); > list L = facstd(I); > texobj("",L[1]); $$ \begin{array}{*{5}{c}cr} & & & & z & = & 0 \\ & & y & & & = & 0 \\ x & & & & & = & 0 \end{array}$$ > texobj("",L[2]); $$ \begin{array}{rcl} y+z & = & 1 \\ x & = & 1 \\ z^{2}+z & = & 1 \end{array} $$ Seems that I should commit an update of latex.lib, where I also have an command Code: // ** loaded /u/gorzelc/.../latex2e.lib 1.0 > texfacstd("",I); $\{ z=y=x=0 \} \cup \{ y+z+1=x+1=z^{2}+z+1=0 \}$ Comments are welcomed ---- Christian Gorzel |
Author: | ellisto [ Tue Mar 29, 2011 10:44 pm ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
Well, when one has an ideal, I, over a field of characteristic 0, one can use solve.lib and use the command Code: solve(I) and the solutions are listed individually, i.e. Code: [1]: 0 [2]: 1 [3]: 0 ... this is more what I was looking for; not just setting each polynomial in the ideal equal to zero, but solving for the variables. In the above example, clearly x=0, y=0, z=0 is a solution, so just setting each member of that ideal is fine, but for the case where x+1 is in the ideal, i don't want x+1=0, i want x=1. Better still if it would be possible to end up with an array of them like solve() provides. In short, I want singular to tell me the values of the variables when possible, not just give me the simplified system. (again, I do not know if this is possible, and I may be misusing singular (trying to have it output information easily usable by another program) ) Thanks again for your help! |
Author: | ellisto [ Tue Mar 29, 2011 10:50 pm ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
Basically I'd like to be able to do things like in the example of solving systems of polynomials (in the example, it's over complex numbers), except over GF(2) |
Author: | gorzel [ Wed Mar 30, 2011 3:57 pm ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
ellisto wrote: Basically I'd like to be able to do things like in the example of solving systems of polynomials (in the example, it's over complex numbers), except over GF(2) This is again numerical solvong. The problem over GF(2) is, that some coordinates of the solution are zeroes of polynomials which are irreducible over GF(2)[x]. Hence, in this case you can not write the solutions plain explicitely as x= ..., y = ..., z =....; instead you need implicit equations i.e. the minimal polynomials. See the example I gave at the beginning. In case that you want to ignore these solutions and you wishes only the have the 0-1-coordinates, then you can write a small proc. The following may be partial solution: Code: proc gf2solver(string fnm, ideal I) // writes the solutions in GF(2)^n to stdout resp. writes to file fnm { int i,j; option(redSB); list L = facstd(I); ideal J; string S; for(i=1;i<=size(L);i++) { if (deg(L[i])==1) // solutions in GF(2), no field extension is needed { J= L[i]; S = newline + S + "["+string(i)+"]" +newline; for (j=1;j<=ncols(J);j++) { S = S + string(J[j]-jet(J[j],0)) + " = "+ string(jet(J[j],0)) + ";" + newline; } S = S + newline; } else { "ignoring solution"; L[i]; } } if (fnm=="") {return(S);} else {write(fnm,S);} } It is yet incomplete as it has to be extended for the free variables: Code: > ring r=2,(x,y,z),dp;
> ideal I = xy-z2,x+y+z,z2+y; > facstd(I*(x+1)); [1]: _[1]=x+1 [2]: _[1]=z _[2]=y _[3]=x [3]: _[1]=x+y+z _[2]=z2+y _[3]=y2+y+1 > gf2solver("",I*(x+1)); ignoring solution _[1]=x+y+z _[2]=z2+y _[3]=y2+y+1 [1] x = 1; [2] z = 0; y = 0; x = 0; |
Author: | ellisto [ Thu Mar 31, 2011 4:35 am ] |
Post subject: | Re: Solving systems of polynomials over GF(2) |
Ok, yes, of course, that is clear. That does make much sense, as many times you cannot explicitly solve them. I think that from the example script you posted, I can get what I need: the explicit solutions when possible, and otherwise the implicit equations. Thanks so much for all of your help! |
Page 1 of 1 | All times are UTC + 1 hour [ DST ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |