Solving systems of polynomials over GF(2)

ellisto · Mon Feb 21, 2011 12:36 am

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?

Re: Solving systems of polynomials over GF(2)

gorzel · Tue Feb 22, 2011 4:20 pm

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.

Re: Solving systems of polynomials over GF(2)

ellisto · Fri Mar 04, 2011 8:52 pm

Fantastic, thank you!

Re: Solving systems of polynomials over GF(2)

ellisto · Mon Mar 28, 2011 8:16 pm

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.

Re: Solving systems of polynomials over GF(2)

gorzel · Tue Mar 29, 2011 5:56 pm

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

Re: Solving systems of polynomials over GF(2)

ellisto · Tue Mar 29, 2011 10:44 pm

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!

Re: Solving systems of polynomials over GF(2)

ellisto · Tue Mar 29, 2011 10:50 pm

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)

Re: Solving systems of polynomials over GF(2)

gorzel · Wed Mar 30, 2011 3:57 pm

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;

Re: Solving systems of polynomials over GF(2)

ellisto · Thu Mar 31, 2011 4:35 am

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!