solving system of polynomial equations in finite field

[Dušan Orlović]

Hi all,
I have a question how to solve system in GF(4) using Grobner basis and elimination (I want to find just one solution).
The system (which is already in reduced form) is:

x^3+x+z
y+z

If we put z=1 then first equation x^3+x+1 has no root in GF(4). If z=0 we have solution y=0, x=0.
Is there an algorithm that can determine right values of z instead of trying all values?
Thanks,

[DuleOrlovic]

I forget to add few more equations to system ie. {x^4-x,y^4-y,z^4-z}
in reason to have solution in GF(4) and zero dimensional ideal, so I
answered my question.
But, I have another issue.
When I use quotient ring Q, J.groebner_basis() does not return
completely reduced basis.
Also, with quotient ring Q, J.variety() returns ValueError: Could not
detect ring.

Code:
K.<alpha>=GF(4)
R.<a,b,c>=PolynomialRing(K,3,order='lex')
Q.<x,y,z>=R.quotient(sage.rings.ideal.FieldIdeal(R))
R.inject_variables()
Q.inject_variables()
F=[a^3+a+c,b+c,a^4-a,b^4-b,c^4-c]
G=[x^3+x+z,y+z]
I=Ideal(F)
J=Ideal(G)
print I.groebner_basis()
print J.groebner_basis()
Defining a, b, c
Defining x, y, z
[a^2 + a + c^2 + c, a*c + c^2 + c, b + c, c^3 + c^2 + c]
[x^2 + x*z + x, x*z + z^2 + z, y + z, z^3 + z^2 + z]
J.variety()
Traceback (click to the left of this block for traceback)
...
ValueError: Could not detect ring.

[luisfe]

Computing with generic quotient rings I am afraid that will be slow
and that will yield to various errors. Specially as in this case,
where the ideal is not prime (you are looking for solutions in GF(4)).
Your code tries to compute the grobner basis of an ideal in a ring
that is not an integer domain...

I would work instead with the ideal

J=sage.rings.ideal.FieldIdeal(R) + Ideal([a^3+a+c, a+c])
sage: J
Ideal (a^4 + a, b^4 + b, c^4 + c, a^3 + a + c, a + c) of Multivariate
Polynomial Ring in a, b, c over Finite Field in alpha of size 2^2

of all the relevant equations and translate here the meaning of what
you want to do

sage: J.groebner_basis()
[a, b^4 + b, c]

sage: J.variety()
[{a: 0, b: 0, c: 0}, {a: 0, b: 1, c: 0}, {a: 0, b: alpha, c: 0}, {a:
0, b: alpha + 1, c: 0}]

[Roman Pearce]

On Oct 28, 4:20 am, luisfe <lftab...@yahoo.es> wrote:
> Computing with generic quotient rings I am afraid that will be slow
> and that will yield to various errors. Specially as in this case,
> where the ideal is not prime (you are looking for solutions in GF(4)).

Doesn't GF(4) construct a field with 4 elements? It shouldn't be Z/
4Z. You can overcome this problem by choosing an irreducible
polynomial of degree 2 modulo 2. I'm thinking x^2+x+1 :) Add it to
the set of polynomials and compute modulo 2, and you have your own
representation of the field.

[luisfe]

GF(4) is fine. What is not prime is the ideal (a^4+a, b^4+b, c^4+c)
used to impose that all the solutions searched are in the field of
four elements instead of the algebraically closed field of
characteristic 2.

Also, I have just realize that this mail is in sage-devel list.
Please, post any further comment in the sage-support mailing list.

[DuleOrlovic]

Thanks for comments.
Apologizing for misplaced mailing list.
BYE