{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem set 2: Part A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = FiniteField(7)\n",
    "R.<x> = PolynomialRing(F)\n",
    "R"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1: [10 points] \n",
    "\n",
    "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)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pow_k_mod(f, k, g, R):\n",
    "    '''\n",
    "    Compute f^k mod g in time poly(deg(g), log k). \n",
    "    '''\n",
    "    if k == 0: return R.one()\n",
    "    if k == 1: return f % g\n",
    "\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# R.<x> = PolynomialRing(FiniteField(7))\n",
    "# pow_k_mod(x, 912302183, x^2 + 3*x + 4, R) == 4*x + 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2: [10 points]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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$. \n",
    "\n",
    "For $d = 1,\\ldots, 6$, compute $\\frac{P_{7,d}}{7^d}$ to get a sense of what fraction of polynomials are irreducible. \n",
    "\n",
    "(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.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3: [10 points]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are two irreducible polynomials in $\\mathbb{F}_7$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R.<x> = PolynomialRing(FiniteField(7))\n",
    "f = (x^2 + 6*x+ 3)\n",
    "g = (x^2 + x + 6)\n",
    "print(f.is_irreducible())\n",
    "print(g.is_irreducible())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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}$. \n",
    "\\begin{align*}\n",
    "R_1 & = \\frac{\\mathbb{F}_7[x]}{x^2 + 6x + 3}\\\\\n",
    "R_2 & = \\frac{\\mathbb{F}_7[y]}{y^2 + y + 6}\\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R1 = R.quotient_ring(f)\n",
    "R2 = R.quotient_ring(g)\n",
    "x = R1.gens()[0]\n",
    "y = R2.gens()[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "phi = R1.hom([3*y + 2], R2)\n",
    "# The first argument ([3y + 2]) is an array where you specify the image for each generator, \n",
    "# and the second argument (R2) is what the homomorphism is into. \n",
    "phi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# phi = R1.hom([y + 1], R2) # throws a ValueError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was a fair bit of set-up; here is the question. \n",
    "\n",
    "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)\n",
    "\n",
    "Can you argue formally that any homomorphism between two fields of the same size is always an isomorphism?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.4",
   "language": "sage",
   "name": "sagemath-9.4"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}