Ask Your Question
1

Substitution in polynomial defined over finite field

asked 2020-04-22 13:07:20 +0100

Alex Karenin gravatar image

updated 2020-04-23 04:28:58 +0100

slelievre gravatar image

I am new to Sage. While attempting to substitute finite field element into polynomial over finite field, instead of variable i get positive characteristic not allowed in symbolic computations error. How am i supposed to substitute in this case? Sage notebook 8.5. Not working code:

x, y = var('x'), var('y')
fx = PolynomialRing(GF(32), x)(x^2 + x)
fx.substitute(x == 1)

Thanks in advance for answer.

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
1

answered 2020-04-22 18:18:46 +0100

dan_fulea gravatar image

Here is a minimal code to define (1) the "polynomial function" $x\to x^2$ as an expression, then substitute for $x$ an element of a finite field, (2) the python function $x\to x^2$, then compute it in an element of a finite field, (3) define the polynomial $x+x^2\in Bbb Z[x]$ as a polynomial with coefficients in $\Bbb Z$, then evaluate it in an element of a finite field, (4) fix a finite field $F$, define the polynomial $x+x^2\in F[x]$, and evaluate it in an element of $F$.

F.<a> = GF(32)
print( f"F = {F}" )
oneF = F(1)

# (1)
var('x');
f = x + x^2
# f(oneF) fails, since f is an expression, but the following works...
val = f.polynomial(F)(oneF)
print( f"# (1) f.polynomial(F)(oneF) gives the value {val}" )

# (2) 
def f(x):
    return x + x^2
val = f(oneF)
print( f"# (2) The python function x -> x^2 gives the value {val}" )

# (3)
R.<x> = PolynomialRing(ZZ)
f = x + x^2
val = f(oneF)
print( f"# (3) the polynomial x + x^2 in ZZ[x] gives the value {val}" )

# (4)
RF.<x> = PolynomialRing(F)
f = x + x^2
val = f(oneF)
print( f"# (4) the polynomial x + x^2 in F[x] gives the value {val}" )

(The polynomials over $\Bbb Z$ work in this case, since there is a coercion to finite fields, but polynomials over $\Bbb Q$ do not have it.)

The above prints give:

# (1) f.polynomial(F)(oneF) gives the value 0
# (2) The python function x -> x^2 gives the value 0
# (3) the polynomial x + x^2 in ZZ[x] gives the value 0
# (4) the polynomial x + x^2 in F[x] gives the value 0

We can also try the same with the value $b = a^4$, where $a$ is the generator of the field $F$.

b = a^4

# (1)
var('x');
f = x + x^2
val = f.polynomial(F)(b)
print( f"# (1) f.polynomial(F)(b) gives in b the value {val}" )

# (2) 
def f(x): return x + x^2
print( f"# (2) The python function x -> x^2 gives in b the value {f(b)}" )

# (3)
R.<x> = PolynomialRing(ZZ)
f = x + x^2
print( f"# (3) the polynomial x + x^2 in ZZ[x] gives in b the value {f(b)}" )

# (4)
RF.<x> = PolynomialRing(F)
f = x + x^2
print( f"# (4) the polynomial x + x^2 in F[x] gives in b the value {f(b)}" )

And indeed:

# (1) f.polynomial(F)(b) gives in b the value a^4 + a^3 + a^2 + 1
# (2) The python function x -> x^2 gives in b the value a^4 + a^3 + a^2 + 1
# (3) the polynomial x + x^2 in ZZ[x] gives in b the value a^4 + a^3 + a^2 + 1
# (4) the polynomial x + x^2 in F[x] gives in b the value a^4 + a^3 + a^2 + 1
sage: a^4 + a^8                                                                                                               
a^4 + a^3 + a^2 + 1
edit flag offensive delete link more
1

answered 2020-04-22 13:14:20 +0100

vdelecroix gravatar image

updated 2020-04-22 13:16:50 +0100

As

sage: R = PolynomialRing(GF(32), 'x')
sage: x = R.gen()
sage: fx = x^2 + x
sage: fx.substitute(x=1)
0

Note that - symbolic variables (declared with var) are better not mixed with polynomial rings - the arguments syntax for substitute is via kewords. In other words x=1 and not x==1. In the case of symbolic functions the second syntax is allowed because x==1 is a symbolic expression itself. Compare

sage: x = SR.var('x')
sage: x == 1   # result is an expression
x == 1
sage: R = PolynomialRing(GF(32), 'x')
sage: x = R.gen()
sage: x == 1    # result is a boolean
False
edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2020-04-22 13:07:20 +0100

Seen: 1,234 times

Last updated: Apr 23 '20