We'll work with the field $\mathbb{F}_7$ for this problem set. Here is how you can create your finite field, and the polynomial ring you wish to work with.

In [ ]:

```
F = FiniteField(7)
R.<x> = PolynomialRing(F)
R
```

Complete the following code that is to compute $f^k \bmod g$ efficiently. That is, the running time of the algorithm should be $\operatorname{poly}(\deg(f), \deg(g), \log k)$.

In [ ]:

```
def pow_k_mod(f, k, g, R):
'''
Compute f^k mod g in time poly(deg(g), log k).
'''
if k == 0: return R.one()
if k == 1: return f % g
pass
```

In [ ]:

```
# R.<x> = PolynomialRing(FiniteField(7))
# pow_k_mod(x, 912302183, x^2 + 3*x + 4, R) == 4*x + 3
```

Let $P_{7,d}$ denote the number of monic (leading coefficient $1$) irreducible polynomials in $\mathbb{F}_7[x]$ of degree $d = 1,2,\ldots, 6$.

For $d = 1,\ldots, 6$, compute $\frac{P_{7,d}}{7^d}$ to get a sense of what fraction of polynomials are irreducible.

(Sage can do things like `factor(x^2 + 2*x + 1)`

, but you might have to be patient if you are feeding a really large degree polynomial.)

Here are two irreducible polynomials in $\mathbb{F}_7$.

In [ ]:

```
R.<x> = PolynomialRing(FiniteField(7))
f = (x^2 + 6*x+ 3)
g = (x^2 + x + 6)
print(f.is_irreducible())
print(g.is_irreducible())
```

We have already seen that quotienting by an irreducible polynomial gives us a field. Here are two different constructions of the field $F_{7^2}$. \begin{align*} R_1 & = \frac{\mathbb{F}_7[x]}{x^2 + 6x + 3}\\ R_2 & = \frac{\mathbb{F}_7[y]}{y^2 + y + 6}\\ \end{align*}

In [ ]:

```
R1 = R.quotient_ring(f)
R2 = R.quotient_ring(g)
x = R1.gens()[0]
y = R2.gens()[0]
```

Sage gives us an option of building a homomorphism from one ring to another. We can do that by specifying the map on just the generators. For instance, consider the homomorphism from $R_1$ to $R_2$ that sends $x$ in $R_1$ to $3y + 2$ in $R_2$ (and yes, this turns out to be a valid homomorphism), we can do that as follows:

In [ ]:

```
phi = R1.hom([3*y + 2], R2)
# The first argument ([3y + 2]) is an array where you specify the image for each generator,
# and the second argument (R2) is what the homomorphism is into.
phi
```

On the other hand, if you specify a map that is *not* a valid homomorphism, Sage will throw a `ValueError`

saying that it could not extend it to a valid homorphism.

In [ ]:

```
# phi = R1.hom([y + 1], R2) # throws a ValueError
```

That was a fair bit of set-up; here is the question.

Find all valid homomorphisms from $R_1$ to $R_2$ (that is, all valid images of $x \in R_1$ that extend to a homomorphism). (You may want to lookup the `try-catch`

syntax in `python`

to handle `ValueError`

s)

Can you argue formally that any homomorphism between two fields of the same size is always an isomorphism?