ff01.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8a370329-0f5a-4a50-b79c-59aeeb357806",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "# Finite Fields 01: $\\mathbb{F}_{2^2}$ over $\\mathbb{F}_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3acc0a4f-ec69-4006-8200-654e7ad57b27",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field of size 2"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F2 = GF(2)\n",
    "F2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "81197d2e-e13d-408a-8ada-2e5028dc6cf3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F2.list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "576e80d4-489a-4e29-a243-b19d86dd2e80",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F2.one() + F2.one()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ee1dcbd9-7b8f-4732-bb8f-d3f428e73913",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F2.one() + F2.zero()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7a752042-a1f1-4d2e-bacd-dc0aabcc48a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F2.one() * F2.one()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5ce987e4-8b6c-4143-bd61-dec1e1466583",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Section 2: F4 = F2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "b00cbd1e-cf4a-49d9-b66d-a2c42351aa34",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in z2 of size 2^2"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define F4\n",
    "\n",
    "F4 = GF(4); F4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "38759666-615f-4b8b-8190-3052fcade138",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, z2, z2 + 1, 1]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F4.list() \n",
    "\n",
    "# Output: \n",
    "#\n",
    "#  [0, z2, z2 + 1, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a0147710-344d-4023-b59b-bc5c549d6821",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in a of size 2^2"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What's `z2`?\n",
    "#\n",
    "# `z2` is analogous to the imaginary part in complex numbers, `a + b*i`\n",
    "#\n",
    "# Any element in F4 is specified by `a + b*z2`, where a,b \\in F2\n",
    "\n",
    "# Rename `z2` into `a`\n",
    "\n",
    "F4.<a> = GF(4, 'a'); F4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "b813413b-eb0b-4e0a-9434-43f4d1ca27a6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Define a polynomial ring: F2[x] \n",
    "\n",
    "R2.<x> = PolynomialRing(F2); R2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "9a633a43-c504-4484-82b6-3faea16ef024",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^3 + x^2"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# So we can do polynomial multiplications over F2[x]\n",
    "\n",
    "(x + 1) * x^2\n",
    "\n",
    "# Output:\n",
    "#   x^3 + x^2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "f7f4b6b9-7d14-4bb1-98a7-3cd9bf82ec8b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# And also polynomial division\n",
    "\n",
    "(x^3 + x + 1).quo_rem(x + 1) == (x^2 + x, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4813f61b-e3b2-44da-93ff-d57dfb907ab1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Compute the evaluation of f(x) \\in F2[x] with f(x=1) \n",
    "\n",
    "(x^3 + x + 1).subs(x=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "58021fdd-070d-4820-b4ea-b449573d9704",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Or, Substitue the indeterminate `x` with a term\n",
    "\n",
    "(x^3 + x + 1).subs(x=x^2) == (x^6 + x^2 + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "81e25766-5690-4f7d-b928-134c4f6b5957",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Theorem: Freshman's Dream\n",
    "#\n",
    "# for any a, b \\in Fq,\n",
    "#\n",
    "#     (a + b)^q = a^q + b^q\n",
    "#\n",
    "# for F_{2^m}, (a + b)^2 = a^2 + b^2\n",
    "#\n",
    "(x + 1) * (x + 1) == (x^2 + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "05c2ba03-38d0-49f7-9fb6-3c9e2e1a391d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The multiplication of a * b (a, b\\in F4)\n",
    "\n",
    "(a + 1) * (a + 1) == a "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "e67694c1-a99f-43aa-901d-16ac5ba1a92e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, x)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Why `(a + 1) * (a + 1) == a` ?\n",
    "#\n",
    "# Because `(a + 1) * (a + 1) = a`  is like `(x + 1) * (x + 1) (mod x^2 + x + 1)`\n",
    "# \n",
    "# \n",
    "((x + 1) * (x + 1)).quo_rem(x^2 + x + 1)\n",
    "\n",
    "# Output:\n",
    "#    (1, x)\n",
    "#\n",
    "# The remainder is x,  `(x + 1) * (x + 1) = x (mod x^2 + x + 1)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "a6590476-df12-4d52-8cfc-f881d25a9c50",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in b of size 2^2"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The multiplications of two GF elements can be viewed as modular multiplication of two polynomials.\n",
    "#\n",
    "# We can construct F4 by modulo operation on polynomials\n",
    "\n",
    "#        F4 = F2[x]/<x^2 + x + 1>,\n",
    "#\n",
    "# F4, as a factor ring of F2[x], is an extension field over F2, if (x^2 + x + 1) is irreducible\n",
    "\n",
    "F4_alt.<b> = F2.extension((x^2 + x + 1), 'b'); F4_alt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "619a6e8c-7934-405f-80d3-353f099212e7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2 + x + 1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(x^2 + x + 1).factor()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "a6b2a33e-92e9-4ac7-8df4-f03705cb8ec9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, b, b + 1, 1]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# List all elements of F4_alt, [0, 1, b, b + 1]\n",
    "\n",
    "F4_alt.list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "de1972f7-66eb-4d76-9525-7969aae733a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Set of field embeddings from Finite Field in a of size 2^2 to Finite Field in b of size 2^2"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H = Hom(F4, F4_alt); H"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "4bab5528-a577-412d-8696-53c10123b661",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Ring morphism:\n",
       "  From: Finite Field in a of size 2^2\n",
       "  To:   Finite Field in b of size 2^2\n",
       "  Defn: a |--> b"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = H([b]); f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "dde3f9a9-8387-40bc-9ab8-36177f5eb947",
   "metadata": {},
   "outputs": [],
   "source": [
    "# But, we have to change the indeterminate `x` to a new notation `b`\n",
    "#\n",
    "#   `x`:  the indeterminate in F2[x]\n",
    "#   `b`:  the indeterminate in F2[X]/<x^2 + x + 1>\n",
    "#\n",
    "#  They are different! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "2d60e472-992b-4147-9e9a-2e1e372ca0cd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Then, F4 can be seen as a vector space F2^2 \n",
    "# with basis (1, a)\n",
    "\n",
    "[1 * i + a * j for i in [0, 1] for j in [0, 1]] == [0, a, 1, a + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "7c74828e-5449-4374-8c3b-242e5932dccd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x * (x + 1) * (x + a) * (x + a + 1)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# F4 is the splitting field of (x^4 - x), that is,\n",
    "#  (x^2 + x + 1) is reducible over F4\n",
    "#\n",
    "# Thm: for any finite field F_{p^m}, (x^{p^m} - x) splits completely in F_{p^m}\n",
    "\n",
    "F4['x'](x^4 - x).factor()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "6a0d0871-eb02-472d-992e-99df57044e2a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The factors (x + a) and (x + a + 1) are actually from (x^2 + x + 1)\n",
    "\n",
    "# The following holds unsurprisingly\n",
    "\n",
    "x^2 + x + 1 ==  (x + a) * (x + a + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "d6a0fa88-bf9f-4ee1-be81-51416210a95c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Thus `a` can also be seen as one root of (x^2 + x + 1),\n",
    "# and `a+1` is the other one. \n",
    "#\n",
    "# Note that there are at most two roots for `(x^2 + x + 1), since deg(x^2 + x + 1) = 2\n",
    "\n",
    "(x^2 + x + 1).degree() == 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "834fde2b-db87-4e45-80d6-c5e1c13d8148",
   "metadata": {},
   "outputs": [],
   "source": [
    "# F4 can be also seen as an algebraic extension over F2 by adjoining `a`, \n",
    "#\n",
    "#     F4 = F2(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6c622d4-6ba6-451d-8cea-c4dc117ec35e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Quiz: why `a^2` equals to `a+1`\n",
    "\n",
    "a^2 == (a + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0bcd41dd-582f-426e-954b-d3e640310f2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Answer: because `a` is one root of (x^2 + x + 1)\n",
    "\n",
    "# a^2 + a + 1 = 0  ==> a^2 = - a - 1 = a + 1\n",
    "\n",
    "a^2 + a + 1 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "6762ceba-c74c-4e3c-9de9-71ec0b5751ad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 2nd Answer: a is a multiplicative generator of F2(a)^*\n",
    "\n",
    "[a, a^2, a^3, a^4] == [a, a + 1, 1, a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "3422afd8-04a0-4cda-8722-51f6aeb45ff5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# In symmetric, \n",
    "\n",
    "[(a+1), (a+1)^2, (a+1)^3, (a+1)^4] == [a + 1, a, 1, a + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02caef6c-52a9-44c8-9384-446cf9ade35f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3rd Answer: (x + 1) is the remainder of polynomial division: (x^2)/(x^2 + x + 1)\n",
    "\n",
    "(x^2).quo_rem(x^2 + x + 1) == (1, x + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "670afbb5-9314-4d31-a30e-a3c5719e6f3d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a^1: \t a\n",
      "a^2: \t a + 1\n",
      "a^3: \t 1\n"
     ]
    }
   ],
   "source": [
    "# `a` is so called \"primitive element\" of F4\n",
    "#\n",
    "# Print (a^i) table of F4^*\n",
    "\n",
    "for i in range(1, 4): print(\"a^{}: \\t {}\".format(i, a^i))\n",
    "\n",
    "# Output:\n",
    "#    a^1: \t a\n",
    "#    a^2: \t a + 1\n",
    "#    a^3: \t 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "102f6dbe-40dd-4634-9aa7-735cedee856f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Order: for any t\\in Fq/{0}, the least integer i satisfying t^i = 1\n",
    "#\n",
    "#   i = ord(t)\n",
    "\n",
    "def ord(elem, card=None):\n",
    "    K = elem.parent()\n",
    "    if card == None:\n",
    "        card = K.order()\n",
    "    for i in range(1, card):\n",
    "        if elem**i == 1:\n",
    "            return i\n",
    "    return \"None\"\n",
    "\n",
    "ord(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c8b6598a-9757-4fce-b6be-ff998735935e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Print all F4 elements with their orders\n",
    "\n",
    "for i in range(1, 4): print(\"a^{}:  \\t ord={}, \\t {}, \".format(i, ord(a^i), a^i))"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}