Evaluate polynomial with imaginary number as input?

asked 3 years ago

vroomerify
21 ●4

updated 0 years ago

FrédéricC

5426 ●4 ●44 ●121

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?

add a comment

2 Answers

Sort by » oldest newest most voted

answered 3 years ago

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

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

link

Comments

Thank you! Can you explain what you mean by "vanishes"?

vroomerify ( 3 years ago )

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?

vroomerify ( 3 years ago )

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$ .

Max Alekseyev ( 3 years ago )

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

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

Max Alekseyev ( 3 years ago )

add a comment

answered 3 years ago

Max Alekseyev

6922 ●9 ●52 ●161

updated 3 years ago

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.

link

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

Evaluate polynomial with imaginary number as input?

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Evaluate polynomial with imaginary number as input? savecancel

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Evaluate polynomial with imaginary number as input?