# Evaluate polynomial with imaginary number as input?

I am trying to evaluate the polynomial (19v^2 + 49v + 8) raised to the 67th power where v^3 + 2 = 0. All computations are done mod 67.

Here's my first attempt:

R.<v> = PolynomialRing(GF(67))
poly = (19 * (v^2) + 49*v + 8)
after_frobenius = poly^67
after_frobenius(sqrt(-2))


But this gives the error: "positive characteristic not allowed in symbolic computation".

I suspect, I need to define the PolynomialRing over an extension field where v^3 + 2 = 0. But, I'm not sure how to do that. Any ideas?

edit retag close merge delete

Sort by » oldest newest most voted

If you want to assume that v^3 + 2 vanishes, perhaps could you work in a quotient ring:

sage: I = R.ideal(v^3 + 2)
sage: I
Principal ideal (v^3 + 2) of Univariate Polynomial Ring in v over Finite Field of size 67
sage: S = R.quotient(I)
sage: S
Univariate Quotient Polynomial Ring in vbar over Finite Field of size 67 with modulus v^3 + 2


Then, you can send your poly in the quotient ring and compute its 67th power:

sage: P = S(poly)
sage: P
19*vbar^2 + 49*vbar + 8
sage: P^67
15*vbar^2 + 4*vbar + 8

more

Another question: What do you mean by "sending" poly to the quotient ring? poly is defined in the polynomial ring over Z/67Z. What happens when we "send" it?

We have $F := \mathbb Z/67\mathbb Z$, $R:=F[v]$, and $S:=F[v]/\langle v^3 + 2\rangle$. "Sending" means natural mapping $f:\ R\rightarrow S$ with $\bar v:=f(v)$. "Vanishes" means that something becomes zero, in this case $f(v^3+2)=0$ or $\bar v^3+2=0$ in $S$.

Btw, you can lift the result back to R by using .lift() method - like:

sage: (P^67).lift()
15*v^2 + 4*v + 8


Essentially you are trying to compute the image of Frobenius endomorphism on 19*v^2 + 49*v + 8 in the field $\mathrm{GF}(67^3) \cong \mathrm{GF}(67)[v]/\langle v^3+2 \rangle$. You can define it as

R.<v> = PolynomialRing(GF(67))
K.<w> = GF( 67^3, name='w', modulus=v^3 + 2 )
Frob = K.frobenius_endomorphism()
print(Frob)


to get

Frobenius endomorphism w |--> w^67 on Finite Field in w of size 67^3


Then it remains to compute Frob( 19*v^2 + 49*v + 8 ), which gives 15*w^2 + 4*w + 8.

more