Ask Your Question
1

solution of a system of equations in algebraic closure of GF2

asked 2018-10-30 22:51:36 +0200

arpit gravatar image

How do I look for solutions of a system of equations in a particular field? For example, the following set of equations in variables ${a,b,c,d,e,f}$ $1 + a + c + e = 0, b + d + f = 0, 1 + a e + c e + a c = 0, b e + a f + c f + e d + b c + a d = 0, b f + f d + b d = 0$ have the solution $a=1,b=1,c=1,d=\omega,e=1,f=\omega^2$ where $\omega$ is the $3^{rd}$ root of unity. This lies in an extension of $\mathbb{GF}_2$, $\mathbb{GF}_4= \frac{\mathbb{GF}_2[u]}{u^2+u+1}$ where $\mathbb{GF}_2[u]$ is a polynomial ring with variable $u$ and one representation of $\mathbb{GF}_4$ is ${0,1,\omega,\omega^2}$.

I have a set of equations and I want to know whether there exist solutions of these equations in an extension of Galois field $\mathbb{GF}_2$ and what are they? Is there a way to check this in Sage?

edit retag flag offensive close merge delete
add a comment

1 Answer

Sort by ยป oldest newest most voted
2

answered 2018-10-30 23:34:18 +0200

tmonteil gravatar image

updated 2018-10-30 23:59:23 +0200

Here is what comes first in mind:

sage: R.<a,b,c,d,e,f> = GF(2)[]
sage: I = R.ideal([1+a+c+e, b+d+f, 1+a*e+c*e+a*c, b*e+a*f+c*f+e*d+b*c+a*d, b*f+f*d+b*d])
sage: I.variety()
ValueError: The dimension of the ideal is 2, but it should be 0

Unfortunately, even if we are in finite fields, Sage can only enumerate solutions of a system of dimension zero.

Let us, for example add the two equations a=1 and b=1:

sage: I = R.ideal([1+a+c+e, b+d+f, 1+a*e+c*e+a*c, b*e+a*f+c*f+e*d+b*c+a*d, b*f+f*d+b*d, a+1, b+1])
sage: I.variety()
[]

Which means that there are no solution in GF(2), but, as you mentionned, there are solutions in GF(4):

sage: I.variety(GF(4,'w'))
[{b: 1, c: 1, a: 1, f: w, d: w + 1, e: 1},
 {b: 1, c: 1, a: 1, f: w + 1, d: w, e: 1}]

If you want all solutions, instead of arbitrary equations a=1, you could add equations which are tautological in GF(4), namely, the equation given by the Frobenius:

sage: [x^4+x for x in R.gens()]
[a^4 + a, b^4 + b, c^4 + c, d^4 + d, e^4 + e, f^4 + f]

So, you can define:

sage: I = R.ideal([1+a+c+e, b+d+f, 1+a*e+c*e+a*c, b*e+a*f+c*f+e*d+b*c+a*d, b*f+f*d+b*d] + [x^4+x for x in R.gens()])
sage: I.variety(GF(4,'w'))
[{b: 0, c: w, a: w + 1, f: 0, d: 0, e: 0},
 {b: 0, c: w + 1, a: w, f: 0, d: 0, e: 0},
 {b: 0, c: 1, a: 1, f: 0, d: 0, e: 1},
 {b: 0, c: 0, a: w + 1, f: 0, d: 0, e: w},
 {b: 0, c: w + 1, a: 0, f: 0, d: 0, e: w},
 {b: 0, c: 0, a: w, f: 0, d: 0, e: w + 1},
 {b: 0, c: w, a: 0, f: 0, d: 0, e: w + 1},
 {b: w + 1, c: w + 1, a: w, f: 1, d: w, e: 0},
 {b: w, c: w, a: w + 1, f: 1, d: w + 1, e: 0},
 {b: w + 1, c: 1, a: 1, f: 1, d: w, e: 1},
 {b: w, c: 1, a: 1, f: 1, d: w + 1, e: 1},
 {b: w + 1, c: 0, a: w + 1, f: 1, d: w, e: w},
 {b: w, c: w + 1, a: 0, f: 1, d: w + 1, e: w},
 {b: w + 1, c: w, a: 0, f: 1, d: w, e: w + 1},
 {b: w, c: 0, a: w, f: 1, d: w + 1, e: w + 1},
 {b: w + 1, c: w, a: w + 1, f: w, d: 1, e: 0},
 {b: 1, c: w + 1, a: w, f: w, d: w + 1, e: 0},
 {b: w + 1, c: 1, a: 1, f: w, d: 1, e: 1},
 {b: 1, c: 1, a: 1, f: w, d: w + 1, e: 1},
 {b: w + 1, c: w + 1, a: 0, f: w, d: 1, e: w},
 {b: 1, c: 0, a: w + 1, f: w, d: w + 1, e: w},
 {b: w + 1, c: 0, a: w, f: w, d: 1, e: w + 1},
 {b: 1, c: w, a: 0, f: w, d: w + 1, e: w + 1},
 {b: w, c: w + 1, a: w, f: w + 1, d: 1, e: 0},
 {b: 1, c: w, a: w + 1, f: w + 1, d: w, e: 0},
 {b: w, c: 1, a: 1, f: w + 1, d: 1, e: 1},
 {b: 1, c: 1, a: 1, f: w + 1, d: w, e: 1},
 {b: w, c: 0, a: w + 1, f: w + 1, d: 1, e: w},
 {b: 1, c: w + 1, a: 0, f: w + 1, d: w, e: w},
 {b: w, c: w, a: 0, f: w + 1, d: 1, e: w + 1},
 {b: 1, c: 0, a: w, f: w + 1, d: w, e: w + 1}]

This can be done in any finite extension of GF(2) using the same trick, for example:

sage: n = 2^6
sage: I = R.ideal([1+a+c+e, b+d+f, 1+a*e+c*e+a*c, b*e+a*f+c*f+e*d+b*c+a*d, b*f+f*d+b*d] + [x^n+x for x in R.gens()])
sage: I.variety(GF(n,'w'))
[here you get a dictionary of 8191 solutions]

Now, if you want to go to the algebraic closure, you can not solve the dimension issue as before, so, if you have enough equations (e.g adding a+c and b^8+b), you can do:

sage: K = GF(2).algebraic_closure()
sage: I = R.ideal([1+a+c+e, b+d+f, 1+a*e+c*e+a*c, b*e+a*f+c*f+e*d+b*c+a*d, b*f+f*d+b*d, a+c, b^8+b])
sage: I.variety(K)
[{b: 0, c: 1, a: 1, f: 0, d: 0, e: 1},
 {b: z3^2 + z3, c: 1, a: 1, f: z6^2 + z6, d: z6^5 + z6^2, e: 1},
 {b: z3^2 + z3 + 1, c: 1, a: 1, f: z6^3, d: z6^5 + z6^3 + z6 + 1, e: 1},
 {b: 1, c: 1, a: 1, f: z2, d: z2 + 1, e: 1},
 {b: 1, c: 1, a: 1, f: z2 + 1, d: z2, e: 1},
 {b: z3, c: 1, a: 1, f: z6^4 + z6^2, d: z6^5 + 1, e: 1},
 {b: z3 + 1, c: 1, a: 1, f: z6^4 + z6^3 + z6 + 1, d: z6^5 + z6^3 + z6^2 + z6 + 1, e: 1},
 {b: z3, c: 1, a: 1, f: z6^5 + 1, d: z6^4 + z6^2, e: 1},
 {b: z3^2 + z3, c: 1, a: 1, f: z6^5 + z6^2, d: z6^2 + z6, e: 1},
 {b: z3^2, c: 1, a: 1, f: z6^5 + z6^2 + z6 + 1, d: z6^5 + z6^4, e: 1},
 {b: z3^2 + 1, c: 1, a: 1, f: z6^5 + z6^3 + 1, d: z6^5 + z6^4 + z6^3 + z6^2 + z6 + 1, e: 1},
 {b: z3^2 + z3 + 1, c: 1, a: 1, f: z6^5 + z6^3 + z6 + 1, d: z6^3, e: 1},
 {b: z3 + 1, c: 1, a: 1, f: z6^5 + z6^3 + z6^2 + z6 + 1, d: z6^4 + z6^3 + z6 + 1, e: 1},
 {b: z3^2, c: 1, a: 1, f: z6^5 + z6^4, d: z6^5 + z6^2 + z6 + 1, e: 1},
 {b: z3^2 + 1, c: 1, a: 1, f: z6^5 + z6^4 + z6^3 + z6^2 + z6 + 1, d: z6^5 + z6^3 + 1, e: 1}]
edit flag offensive delete link more

Comments

This is a very nice answer. Thanks very much. Can I check only the existence of a solution in the algebraic closure for example, without adding extra equations? I assume the answer to it is No as otherwise sage might have just solved it as this doesn't seem to be a problem whose solution's existence is much easier compared to the solution itself.

arpit gravatar imagearpit ( 2018-10-31 01:53:38 +0200 )edit
1

If you just want to know the existence of some solutions in the algebraic closure, you can look at the dimension of the ideal:

sage: I = R.ideal([1+a, a])
sage: I.dimension()
-1
sage: I = R.ideal([1+a])
sage: I.dimension()
5
tmonteil gravatar imagetmonteil ( 2018-10-31 10:38:15 +0200 )edit

Thank you. Also, you used the equations $x^n+x$ as tautological equations for arbitrary $\mathbb{GF}(n)$. I know that for $n=4$, one has $x^4+x$ but for higher powers (i.e. $\alpha$) of 2 in $n=2^\alpha$, the form of the polynomial should be different. https://en.wikipedia.org/wiki/Finite_... Is there a general form of this polynomial for an arbitrary $n$?

arpit gravatar imagearpit ( 2018-11-02 03:01:06 +0200 )edit
add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

subscribe to rss feed

Stats

Asked: 2018-10-30 22:51:36 +0200

Seen: 590 times

Last updated: Oct 30 '18

Related questions

separation of variables / parameterizing equations in sage math

Polynomial representation of GF(7)?

riemann roch basis

Finite field extension

Finding solution to nonlinear equations numerically in a range

Can I display a list of equations aligned like latex eqnarray?

simplify equations

How do I find a solution of a set of inequalities?

Elementary algebraic geometry?

How does one find solutions to a polynomial over a finite field?

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59