Ask Your Question
2

Evaluate polynomial with imaginary number as input?

asked 2022-02-09 00:51:31 +0200

vroomerify gravatar image

updated 2022-02-09 00:51:39 +0200

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2022-02-09 00:53:51 +0200

tmonteil gravatar image

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
edit flag offensive delete link more

Comments

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

vroomerify gravatar imagevroomerify ( 2022-02-09 01:23:32 +0200 )edit

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 gravatar imagevroomerify ( 2022-02-09 01:28:19 +0200 )edit

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 gravatar imageMax Alekseyev ( 2022-02-09 15:55:15 +0200 )edit

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 gravatar imageMax Alekseyev ( 2022-02-09 16:13:53 +0200 )edit
0

answered 2022-02-09 16:28:05 +0200

Max Alekseyev gravatar image

updated 2022-02-09 16:32:02 +0200

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.

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

1 follower

Stats

Asked: 2022-02-09 00:46:33 +0200

Seen: 45 times

Last updated: Feb 09