05_finite_field.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Конечные поля"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Способ описания поля - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in a of size 7^15"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Конечное поле характеристики 7. Будет построено как факторкольцо F[a]/p(a)\n",
    "F.<a> = GF(7^15); F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "a^15 + 5*a^6 + 6*a^5 + 6*a^4 + 4*a^3 + a^2 + 2*a + 4"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# В Sage полином p(a) выбирается из полиномов Конвея (минимальный полином примитивного элемента)\n",
    "# Отображение полинома\n",
    "F.polynomial()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^15 + 5*x^6 + 6*x^5 + 6*x^4 + 4*x^3 + x^2 + 2*x + 4"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Полином Конвея порядка 15 над полем Z_7\n",
    "conway_polynomial(7, 15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "a"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Примитивный элемент поля F, то есть такой элемент, что циклическая группа F\\0 = < \\alpha >\n",
    "F.primitive_element()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Вывод всех элементов. В этом примере очень долго в силу большого количества элементов \n",
    "#F.list() \n",
    "\n",
    "## Еще один способ вывода - обхода элементов\n",
    "#print([x for x in F]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[a, a^2, a^3, a^4, a^5, a^6, a^7, a^8, a^9, a^10, a^11, a^12, a^13, a^14, 2*a^6 + a^5 + a^4 + 3*a^3 + 6*a^2 + 5*a + 3, 2*a^7 + a^6 + a^5 + 3*a^4 + 6*a^3 + 5*a^2 + 3*a, 2*a^8 + a^7 + a^6 + 3*a^5 + 6*a^4 + 5*a^3 + 3*a^2, 2*a^9 + a^8 + a^7 + 3*a^6 + 6*a^5 + 5*a^4 + 3*a^3, 2*a^10 + a^9 + a^8 + 3*a^7 + 6*a^6 + 5*a^5 + 3*a^4, 2*a^11 + a^10 + a^9 + 3*a^8 + 6*a^7 + 5*a^6 + 3*a^5, 2*a^12 + a^11 + a^10 + 3*a^9 + 6*a^8 + 5*a^7 + 3*a^6, 2*a^13 + a^12 + a^11 + 3*a^10 + 6*a^9 + 5*a^8 + 3*a^7, 2*a^14 + a^13 + a^12 + 3*a^11 + 6*a^10 + 5*a^9 + 3*a^8, a^14 + a^13 + 3*a^12 + 6*a^11 + 5*a^10 + 3*a^9 + 4*a^6 + 2*a^5 + 2*a^4 + 6*a^3 + 5*a^2 + 3*a + 6]\n"
     ]
    }
   ],
   "source": [
    "#Вывести все степени примитивного элемента\n",
    "print([a**k for k in range(1,25)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Способ описания поля - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Univariate Quotient Polynomial Ring in a over Ring of integers modulo 7 with modulus z^2 + z + 3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Постройте кольцо полиномов над Z_7 от переменной z\n",
    "P.<z>=Integers(7)[]\n",
    "\n",
    "#Идеал, порожденный z^2+z+3\n",
    "K = P.ideal(z^2+z+3)\n",
    "\n",
    "#Факторкольцо по идеалу\n",
    "H.<a> = P.quotient(K); H "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Проверка неразложимости полинома \n",
    "(z^2+z+3).is_irreducible()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2 + 6*x + 3"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Полином Конвея не совпадает с p(z)\n",
    "conway_polynomial(7, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Проверка является ли H полем\n",
    "H.is_field()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "## H.polynomial() - не работает\n",
    "## H.list() - - не работает\n",
    "## H.multiplication_table() - бесполезно"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, a, a + 1, a + 2, a + 3, a + 4, a + 5, a + 6, 2*a, 2*a + 1, 2*a + 2, 2*a + 3, 2*a + 4, 2*a + 5, 2*a + 6, 3*a, 3*a + 1, 3*a + 2, 3*a + 3, 3*a + 4, 3*a + 5, 3*a + 6, 4*a, 4*a + 1, 4*a + 2, 4*a + 3, 4*a + 4, 4*a + 5, 4*a + 6, 5*a, 5*a + 1, 5*a + 2, 5*a + 3, 5*a + 4, 5*a + 5, 5*a + 6, 6*a, 6*a + 1, 6*a + 2, 6*a + 3, 6*a + 4, 6*a + 5, 6*a + 6]\n"
     ]
    }
   ],
   "source": [
    "#Список всех элементов H\n",
    "print([t for t in H])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 1), (1, 1), (2, 3), (3, 6), (4, 3), (5, 6), (6, 2), (a, 48), (a + 1, 48), (a + 2, 48), (a + 3, 24), (a + 4, 4), (a + 5, 24), (a + 6, 48), (2*a, 48), (2*a + 1, 12), (2*a + 2, 48), (2*a + 3, 8), (2*a + 4, 16), (2*a + 5, 16), (2*a + 6, 8), (3*a, 16), (3*a + 1, 24), (3*a + 2, 24), (3*a + 3, 16), (3*a + 4, 48), (3*a + 5, 12), (3*a + 6, 48), (4*a, 16), (4*a + 1, 48), (4*a + 2, 12), (4*a + 3, 48), (4*a + 4, 16), (4*a + 5, 24), (4*a + 6, 24), (5*a, 48), (5*a + 1, 8), (5*a + 2, 16), (5*a + 3, 16), (5*a + 4, 8), (5*a + 5, 48), (5*a + 6, 12), (6*a, 48), (6*a + 1, 48), (6*a + 2, 24), (6*a + 3, 4), (6*a + 4, 24), (6*a + 5, 48), (6*a + 6, 48)]\n"
     ]
    }
   ],
   "source": [
    "# Выведем порядки всех элементов из H\n",
    "def order_elem(t, H):\n",
    "    return len({\n",
    "        t**k for k in range(1,len(H))\n",
    "               })\n",
    "\n",
    "print([(t,order_elem(t,H)) for t in H])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{a + 4, 6*a + 3, 6, 1}\n"
     ]
    }
   ],
   "source": [
    "print({(a+4)**k for k in range(1,49)})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Упражнения\n",
    "\n",
    "1. Постройте поле порядка 25. Разложите многочлен $x^{25}-x$ на множители над этим полем. Прокомментируйте результаты.\n",
    "2. Постройте поле с помощью неприводимого полинома. Проверьте, будет порождающий элемент примитивным.\n",
    "3. Пусть $\\alpha$ корень многочлена $x^3+x^2+1$ над $Z_2$. Постройте поле GF(8). Покажите, что $x^3+x^2+1$ разлагается на линейные множители $Z_2(\\alpha)$.\n",
    "4. Вычислите [GF⁡(128):GF⁡(16)]\n",
    "5. Покажите, что каждый элемент в конечном поле GF(25) является суммой квадратов.  \n",
    "6. *Покажите, что каждый элемент в конечном поле является суммой квадратов. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.3",
   "language": "sage",
   "name": "sagemath"
  },
  "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}