Задание 4

1 files changed, 277 insertions, 2 deletions

diff --git a/t4mk.ipynb b/t4mk.ipynb
index 1f12fc8..ce13d34 100644
--- a/t4mk.ipynb
+++ b/t4mk.ipynb
@@ -11,7 +11,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 41,
+   "execution_count": 42,
    "metadata": {},
    "outputs": [
     {
@@ -207,7 +207,7 @@
     "f.display()\n",
     "\n",
     "table = successive_convergents(*frac)\n",
-    "display_table(table)\n"
+    "display_table(table)"
    ]
   },
   {
@@ -216,6 +216,281 @@
    "source": [
     "# Задание 2"
    ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Задание 3"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Задание 4\n",
+    "\n",
+    "Ввести значения $p$ и $a$ для определения порядка элемента в группе $Z^*_p$"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 63,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle \\text{Значение } r = \\lfloor\\sqrt{B}\\rfloor + 1 = 7$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a^1 \\pmod{37} = 3^1 \\pmod{37} = 3$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a^2 \\pmod{37} = 3^2 \\pmod{37} = 9$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a^3 \\pmod{37} = 3^3 \\pmod{37} = 27$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a^4 \\pmod{37} = 3^4 \\pmod{37} = 7$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a^5 \\pmod{37} = 3^5 \\pmod{37} = 21$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a^6 \\pmod{37} = 3^6 \\pmod{37} = 26$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle \\text{Отсортированные пары:}$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle (1, 3), (4, 7), (2, 9), (5, 21), (6, 26), (3, 27)$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a^{-r} = 3^{-7} = (3^7)^{-1} = 4^{-1} = 28 \\pmod{p}$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a_1^{0} \\cdot 1 \\pmod{37} = 1$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a_1^{1} \\cdot 1 \\pmod{37} = 28$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle a_1^{2} \\cdot 1 \\pmod{37} = 7$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle \\text{Значение } a^{-r} \\cdot b \\text{ совпало с вторым значением пары } (4, 7)$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    },
+    {
+     "data": {
+      "text/latex": [
+       "$\\displaystyle \\text{Получаем результат: } k + ri = 4 + 7 \\cdot 2 = 18$"
+      ],
+      "text/plain": [
+       "<IPython.core.display.Math object>"
+      ]
+     },
+     "metadata": {},
+     "output_type": "display_data"
+    }
+   ],
+   "source": [
+    "a, p = 3, 37\n",
+    "\n",
+    "from math import sqrt\n",
+    "\n",
+    "def gcd_extended(x1, x2):\n",
+    "    if x1 == 0:\n",
+    "        return x2, 0, 1\n",
+    "    else:\n",
+    "        div, x, y = gcd_extended(x2 % x1, x1)\n",
+    "    return div, y - (x2 // x1) * x, x\n",
+    "\n",
+    "def inverse(a, m):\n",
+    "    d, u, v = gcd_extended(a, m)\n",
+    "    if d != 1:\n",
+    "        print('Нет обратного у элемента a =', a, 'в кольце вычетов по модулю', m)\n",
+    "        exit()\n",
+    "    x = u % m\n",
+    "    return x\n",
+    "\n",
+    "def bg_step(a, b, p):\n",
+    "    ltx = []\n",
+    "\n",
+    "    r = int(sqrt(p - 1)) + 1\n",
+    "    # TODO: написать дальше\n",
+    "    ltx.append(f\"\\\\text{{Значение }} r = \\\\lfloor\\\\sqrt{{B}}\\\\rfloor + 1 = {r}\")\n",
+    "\n",
+    "    ka = []\n",
+    "    for i in range(1, r):\n",
+    "        i, pi = i, pow(a, i, p)\n",
+    "        ltx.append(f\"a^{i} \\pmod{{{p}}} = {a}^{i} \\pmod{{{p}}} = {pi}\")\n",
+    "        ka.append((i, pi))\n",
+    "    ka = sorted(ka, key=lambda k: [k[1], k[0]])\n",
+    "    \n",
+    "    ltx.append(\"\\\\text{Отсортированные пары:}\")\n",
+    "    tmp = []\n",
+    "    for (ai, ap) in ka:\n",
+    "        tmp.append(f'({ai}, {ap})')\n",
+    "    ltx.append(', '.join(tmp))\n",
+    "\n",
+    "\n",
+    "    a1 = inverse(pow(a, r, p), p)\n",
+    "    ltx.append(f\"a^{{-r}} = {a}^{{{-r}}} = ({a}^{r})^{{-1}} = {pow(a,r,p)}^{{-1}} = {a1} \\\\pmod{{p}}\")\n",
+    "\n",
+    "    for i in range(r):\n",
+    "        a1ib = pow(a1, i, p) * b % p\n",
+    "        ltx.append(f\"a_1^{{{i}}} \\\\cdot {b} \\\\pmod{{{p}}} = {a1ib}\")\n",
+    "        for k, ak in ka:\n",
+    "            if a1ib == ak:\n",
+    "                ltx.append(f\"\\\\text{{Значение }} a^{{-r}} \\cdot b \\\\text{{ совпало со вторым значением пары }} {(k, ak)}\")\n",
+    "                res = k + r * i\n",
+    "                ltx.append(f\"\\\\text{{Получаем результат: }} k + ri = {k} + {r} \\cdot {i} = {res}\")\n",
+    "                return ltx, res\n",
+    "\n",
+    "ltx, res = bg_step(a, 1, p)\n",
+    "for line in ltx:\n",
+    "    display(Math(line))"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Задание 5"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "# Задание 6"
+   ]
   }
  ],
  "metadata": {