ch3_arithmetic/4_polynomial_arithmetic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "79eafa81-30a6-468d-bb04-5cb7436049b9",
   "metadata": {},
   "source": [
    "## Exercise 25. \n",
    "\n",
    "Compare both expansions of P7 from $Z[x]$ in example 18 and from from $Z_6[x]$ in example 19 , and consider the definition of $Z_6$ as given in example 11. Can you see how the definition of P7 over $Z$ projects to the definition over $Z_6$ if you consider the residue classes of $Z_6$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "e309133a-a1f2-4592-874a-85983ba459ba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P7: x^3 - 4*x^2 - 11*x + 30\n",
      "P7_6: x^3 + 2*x^2 + x\n"
     ]
    }
   ],
   "source": [
    "Zx = ZZ['x']\n",
    "P7 = Zx([30, -11, -4, 1])\n",
    "print(f\"P7: {P7}\")\n",
    "P7_6 = Z6x(P7)\n",
    "print(f\"P7_6: {P7_6}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "946e25dc-13be-492b-986e-20c63659e20a",
   "metadata": {},
   "source": [
    "## Exercise 26. \n",
    "\n",
    "Compare the sum P + Q and the product P · Q from the previous two examples 22 and 23, and consider the definition of $Z_6$ as given in example 11. How can we derive the computations in $Z_6[x]$ from the computations in $Z[x]$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "id": "e7a02ef5-f3ee-4984-bc2d-c9c01ba98376",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PplusQ: x^3 + 3*x^2 - 4*x + 7\n",
      "Z6PplusQ: x^3 + 3*x^2 + 2*x + 1\n",
      "PtimesQ: 5*x^5 - 14*x^4 + 10*x^3 + 21*x^2 - 20*x + 10\n",
      "Z6PplusQ: 5*x^5 + 4*x^4 + 4*x^3 + 3*x^2 + 4*x + 4\n"
     ]
    }
   ],
   "source": [
    "P = Zx([2,-4,5])\n",
    "Q = Zx([5,0,-2,1])\n",
    "PplusQ = P + Q\n",
    "PtimesQ = P * Q\n",
    "assert(Z6x(PplusQ) == Z6x(P) + Z6x(Q))\n",
    "assert(Z6x(PtimesQ) == Z6x(P) * Z6x(Q))\n",
    "print(f\"PplusQ: {PplusQ}\")\n",
    "print(f\"Z6PplusQ: {Z6x(PplusQ)}\")\n",
    "print(f\"PtimesQ: {PtimesQ}\")\n",
    "print(f\"Z6PplusQ: {Z6x(PtimesQ)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9906c326-d6da-4e61-a696-b9428edaddb6",
   "metadata": {},
   "source": [
    "## Exercise 27.4\n",
    "\n",
    "Consider the polynomial expressions A(x) := $−3x^4 + 4x^3 + 2x^2 + 4$ and B(x) = $x^2 − 4x + 2$. Compute the Euclidean Division of A by B in the following types:\n",
    "1. $A,B \\in Z[x]$\n",
    "2. $A,B \\in Z6[x]$\n",
    "3. $A,B \\in Z5[x]$\n",
    "\n",
    "Now consider the result in Z[x] and in Z6[x]. How can we compute the result in Z6[x] from the result in Z[x]?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "id": "8efb152c-3ec8-4c4a-b6f1-5261b73c5393",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ax: -3*x^4 + 4*x^3 + 2*x^2 + 4 == x^2 - 4*x + 2 * -3*x^2 - 8*x - 24 + -80*x + 52\n",
      "A6x: 3*x^4 + 4*x^3 + 2*x^2 + 4 == x^2 + 2*x + 2 * 3*x^2 + 4*x + 4*x + 4\n",
      "A5x: 2*x^4 + 4*x^3 + 2*x^2 + 4 == x^2 + x + 2 * 2*x^2 + 2*x + 1 + 2\n"
     ]
    }
   ],
   "source": [
    "A_coeff = [4, 0, 2 , 4, -3]\n",
    "B_coeff = [2, -4 , 1]\n",
    "\n",
    "A, B = ZZ['x'], ZZ['x']\n",
    "Ax, Bx = A(A_coeff), B(B_coeff)\n",
    "q, r = Ax.quo_rem(Bx)\n",
    "assert(Ax == Bx * q + r)\n",
    "print(f\"Ax: {Ax} == {Bx} * {q} + {r}\")\n",
    "\n",
    "A6, B6 = Integers(6)['x'], Integers(6)['x']\n",
    "A6x, B6x = A6(A_coeff), B6(B_coeff)\n",
    "q, r = A6x.quo_rem(B6x)\n",
    "assert(A6x == B6x * q + r)\n",
    "print(f\"A6x: {A6x} == {B6x} * {q} + {r}\")\n",
    "\n",
    "A5, B5 = Integers(5)['x'], Integers(5)['x']\n",
    "A5x, B5x = A5(A_coeff), B5(B_coeff)\n",
    "q, r = A5x.quo_rem(B5x)\n",
    "assert(A5x == B5x * q + r)\n",
    "print(f\"A5x: {A5x} == {B5x} * {q} + {r}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b020f50a-61c6-4567-843a-5d2d7274bf4b",
   "metadata": {},
   "source": [
    "## Exercise 28.\n",
    "\n",
    "Show that the polynomial B(x) = $2x^4 −3x +4 \\in Z_5[x]$ is a factor of the polynomial A(x) = $x^7 +4x^6 +4x^5 +x^3 +2x^2 +2x+3 \\in Z5[x]$, that is, show that B|A. What is A div B?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "id": "0613ca81-5021-4c88-adf6-d11a67a7df99",
   "metadata": {},
   "outputs": [],
   "source": [
    "A_coeff = [3, 2, 2 , 1, 0, 4, 4, 1]\n",
    "B_coeff = [4, -3 , 0, 0, 2]\n",
    "\n",
    "A5x, B5x = A5(A_coeff), B5(B_coeff)\n",
    "q, r = A5x.quo_rem(B5x)\n",
    "\n",
    "assert(r == 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "beec8430-b1e3-4a5e-8560-443f444fb0c6",
   "metadata": {},
   "source": [
    "## Exercise 29. \n",
    "\n",
    "Show that if the sum of the multiplicity of all roots of a polynomial $P \\in R[x]$ of degree deg(P) = m is less than m, the polynomial must have a prime factor F of degree deg(F)>1.\n",
    "\n",
    "**solution:**\n",
    "\n",
    "$P = (x^{e_0} - x_0)^{a_0} \\cdot .. \\cdot (x^{e_n} - x_n)^{a_n} \\rightarrow$ deg(P) = $\\sum_0^{i\\in n} e_i \\cdot a_i = m$\n",
    "\n",
    "if m = a then e = [1] else if m > a then e > [1]\n",
    "\n",
    "[tip](https://github.com/ret2basic/moonmath/tree/master/arithmetics#exercise-29-): define $Q(x)$ irreducible polynomial which degree(Q) > 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99514777-beda-4e2c-82e3-44b71ace288a",
   "metadata": {},
   "source": [
    "## Exercise 30. \n",
    "\n",
    "Consider the polynomial $P = x^7 +3x^6 +3x^5 + x^4 − x^3 − 3x^2 − 3x −1 \\in Z6[x]$. Compute the set of all roots of R0(P) and then compute the prime factorization of P."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 252,
   "id": "76095534-b57c-4fbb-bc47-75b20a478e5f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Roots: [1, 5]\n"
     ]
    }
   ],
   "source": [
    "coeffs = [-1, -3, -3, -1, 1, 3, 3, 1]\n",
    "P = Z6x(coeffs)\n",
    "roots = P.roots(multiplicities=False)\n",
    "print(f\"Roots: {roots}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6bd85634-4f9d-4f56-99c8-1917907ab41a",
   "metadata": {},
   "source": [
    "[tip](https://github.com/ret2basic/moonmath/tree/master/arithmetics#exercise-30-): code to calulate factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "id": "d9115a1d-f9d6-44f6-a44d-60fee2416fdf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Factors: [(x + 5, 1), (x + 1, 4), (x^2 + 1, 1)]\n"
     ]
    }
   ],
   "source": [
    "factors = []\n",
    "Q = P\n",
    "for r in roots:\n",
    "  R = Z6x([-r, 1])\n",
    "  count = 1\n",
    "  while True:\n",
    "    Q = Q // R\n",
    "    if r not in Q.roots(multiplicities=False):\n",
    "      break\n",
    "    count += 1\n",
    "  factors.append((R, count))\n",
    "\n",
    "if Q != Z6x(1):\n",
    "  factors.append((Q, 1))\n",
    "\n",
    "print(\"Factors:\", factors)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8c7a19c-228c-4409-b5ca-675661efe60d",
   "metadata": {},
   "source": [
    "## Exercise 31. \n",
    "\n",
    "Consider modular 5 arithmetic from example 16, and the set $S = {(0, 0), (1, 1), (2, 2), (3, 2)}$. Find a polynomial $P \\in Z_5[x] \\textrm{ such that } P(x_i) = y_i \\forall (x_i,y_i) \\in S$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 248,
   "id": "738a0e00-8811-458a-b7ed-26bce87336a4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4*x^3 + 3*x^2 + 4*x"
      ]
     },
     "execution_count": 248,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = [(0,0), (1, 1), (2,2),(3,2)]\n",
    "Z5x = Integers(5)['x']\n",
    "Z5x.lagrange_polynomial(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "baa2179d-5f08-4268-984c-5a710092dd96",
   "metadata": {},
   "source": [
    "## Exercise 32. \n",
    "\n",
    "Consider the set S from the previous example. Why is it not possible to apply algorithm 4 to construct a polynomial $P \\in Z_6[x] \\textrm{ such that } P(x_i) = y_i \\forall (x_i,y_i) \\in S$?\n",
    "\n",
    "**solution:**\n",
    "\n",
    "Since $6 \\notin \\mathbb{P}$ it can be assure that $x^{-1}$ has an inverse an thus the algorithm can not be applied."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8daf85fd-fddc-4e3b-91ee-123d8334460c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.3",
   "language": "sage",
   "name": "sagemath-10.3"
  },
  "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.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}