ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 02 Mar 2020 15:27:09 +0100Iterate over multivariate polynomials over finite fieldshttps://ask.sagemath.org/question/50136/iterate-over-multivariate-polynomials-over-finite-fields/Say we have a finite field, e.g. $F_4$, and consider the $n$-ary polynomials $R=F_4[x_1,\dots,x_n]$ over this field.
I want to iterate over all these polynomials in $R$. Since the polynomials are over a finite field there are only finitely many different polynomials (considered as functions $F_4^n \to F_4$). How can I do this?
For $n=1$ I could do
R.<x> = PolynomialRing(GF(4))
S.<a> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
Then I could iterate over $S$ and simply lift all the elements from $S$ back to $R$, i.e. s.lift(). The same thing however does not work for several polynomials:
R.<x,y> = PolynomialRing(GF(4))
S.<a,b> = R.quo(sage.rings.ideal.FieldIdeal(R))
S.is_finite()
yields the error
> AttributeError: 'super' object has no attribute 'is_finite'
As an alternative I could manually generate all multivariate polynomials with exponents less than the order of the field. However, this seems quite tedious and like a very "un-sage"/not algebraic way.philipp7Mon, 02 Mar 2020 15:27:09 +0100https://ask.sagemath.org/question/50136/Solving system of polynomial equation over finite fieldhttps://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.blishkoSun, 23 Jun 2013 11:16:01 +0200https://ask.sagemath.org/question/10270/