{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Задание 1\n",
    "\n",
    "Изменяем значение `frac` на свою дробь."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\Large\\frac{157}{225}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 0 + \\Large\\frac{1}{\\Large\\frac{225}{157}}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 0 + \\Large\\frac{1}{1 + \\Large\\frac{1}{\\Large\\frac{157}{68}}}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 0 + \\Large\\frac{1}{1 + \\Large\\frac{1}{2 + \\Large\\frac{1}{\\Large\\frac{68}{21}}}}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 0 + \\Large\\frac{1}{1 + \\Large\\frac{1}{2 + \\Large\\frac{1}{3 + \\Large\\frac{1}{\\Large\\frac{21}{5}}}}}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle 0 + \\Large\\frac{1}{1 + \\Large\\frac{1}{2 + \\Large\\frac{1}{3 + \\Large\\frac{1}{4 + \\Large\\frac{1}{5}}}}}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\begin{array}{ccccccccc}\n",
       "i & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\\\n",
       "q_i &  &  & 0 & 1 & 2 & 3 & 4 & 5 \\\\\n",
       "P_i & 0 & 1 & 0 & 1 & 2 & 7 & 30 & 157 \\\\\n",
       "Q_i & 1 & 0 & 1 & 1 & 3 & 10 & 43 & 225 \\\\\n",
       "\\end{array}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "frac = (157, 225)\n",
    "\n",
    "from IPython.display import display, Math\n",
    "\n",
    "# Задание 1 - 157 225\n",
    "def continued_fraction(a0, a1):\n",
    "    if a1 > 0:\n",
    "        qs = []\n",
    "        while a1 != 0:\n",
    "            r = a0 % a1\n",
    "            qs.append((a0 - r) // a1)\n",
    "            # print(f'{a0} / {a1} = {qs[-1]} + {a1} / {r}')\n",
    "            a0 = a1\n",
    "            a1 = r\n",
    "        # print('Непрерывная дробь', qs)\n",
    "        return qs\n",
    "    else:\n",
    "        return 'Знаменатель должен быть больше нуля!'\n",
    "\n",
    "\n",
    "def successive_convergents(a0, a1):\n",
    "    qs = [0, 0] + continued_fraction(a0, a1)\n",
    "    big_ps = [0, 1]\n",
    "    big_qs = [1, 0]\n",
    "    for i in range(2, len(qs)):\n",
    "        big_ps.append(big_ps[i - 1] * qs[i] + big_ps[i - 2])\n",
    "        big_qs.append(big_qs[i - 1] * qs[i] + big_qs[i - 2])\n",
    "    # print(f'P = {big_ps}')\n",
    "    # print(f'Q = {big_qs}')\n",
    "    qs[0] = qs[1] = None\n",
    "    return qs, big_ps, big_qs\n",
    "\n",
    "\n",
    "class Num:\n",
    "  def __init__(self, val):\n",
    "    self.val = val\n",
    "\n",
    "  def math(self):\n",
    "    return str(self.val)\n",
    "\n",
    "class Fr:\n",
    "  def __init__(self, den, num):\n",
    "    self.val = None\n",
    "    self.den = den\n",
    "    self.num = num\n",
    "  \n",
    "  def math(self):\n",
    "    if self.val is None:\n",
    "      return f\"\\\\Large\\\\frac{{{self.den}}}{{{self.num}}}\"\n",
    "    else:\n",
    "      return f\"{self.val} + \\\\Large\\\\frac{{{self.den}}}{{{self.num.math()}}}\"\n",
    "  \n",
    "  def display(self):\n",
    "    return display(Math(self.math()))\n",
    "  \n",
    "  def next(self):\n",
    "    ret = True\n",
    "    if self.val is None:\n",
    "      self.val = self.den // self.num\n",
    "      self.den = self.den % self.num\n",
    "      if self.den == 1:\n",
    "        f1 = Num(self.num)\n",
    "        ret = False\n",
    "      else:\n",
    "        f1 = Fr(self.num, self.den)\n",
    "      self.den = 1\n",
    "      self.num = f1\n",
    "    else:\n",
    "      ret = self.num.next()\n",
    "    return ret\n",
    "\n",
    "\n",
    "def display_table(table):\n",
    "  qs, bps, bqs = table\n",
    "  res = [r\"\\begin{array}{\" + 'c' * (len(qs) + 1) + '}']\n",
    "\n",
    "  i_row = ['i'] + list(map(str, range(-1, len(qs) - 2 + 1)))\n",
    "  q_row = ['q_i', '', '']\n",
    "  bq_row = ['Q_i']\n",
    "  bp_row = ['P_i']\n",
    "  for (qi, bqi, bpi) in zip(qs, bqs, bps):\n",
    "    if qi is not None:\n",
    "      q_row.append(str(qi))\n",
    "    bq_row.append(str(bqi))\n",
    "    bp_row.append(str(bpi))\n",
    "  res.append(' & '.join(i_row) + r' \\\\')\n",
    "  res.append(' & '.join(q_row) + r' \\\\')\n",
    "  res.append(' & '.join(bp_row) + r' \\\\')\n",
    "  res.append(' & '.join(bq_row) + r' \\\\')\n",
    "\n",
    "  res.append(r\"\\end{array}\")\n",
    "  res = '\\n'.join(res)\n",
    "  return display(Math(res))\n",
    "\n",
    "f = Fr(*frac)\n",
    "while True:\n",
    "  f.display()\n",
    "  if not f.next():\n",
    "    break\n",
    "f.display()\n",
    "\n",
    "table = successive_convergents(*frac)\n",
    "display_table(table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Задание 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Задание 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle M = 3 \\cdot 5 \\cdot 4 = 60$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle M_{1} = 20; 20 x \\equiv 1 \\pmod{3}; z_{1} = 2$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle M_{2} = 12; 12 x \\equiv 3 \\pmod{5}; z_{2} = 4$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle M_{3} = 15; 15 x \\equiv 2 \\pmod{4}; z_{3} = 2$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle x = M_{0} \\cdot z_{0} + M_{1} \\cdot z_{1} + M_{2} \\cdot z_{2} = 20 \\cdot 2 + 12 \\cdot 4 + 15 \\cdot 2 = 58 \\pmod{60}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "ai, mi = [1, 3, 2], [3, 5, 4]\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 greco_chinese_theorem(u, m):\n",
    "    ltx = []\n",
    "    M = 1\n",
    "    for i in m:\n",
    "        M *= i\n",
    "    tmp = ' \\\\cdot '\n",
    "    ltx.append(f\"M = {tmp.join(map(str, m))} = {M}\")\n",
    "\n",
    "    tmp1 = []\n",
    "    tmp2 = []\n",
    "    x = 0\n",
    "    for i in range(len(m)):\n",
    "        c = M // m[i]\n",
    "        d = inverse(c, m[i])\n",
    "        x += c * d * u[i]\n",
    "        ltx.append(f\"M_{{{i + 1}}} = {c}; {c} x \\\\equiv {u[i]} \\\\pmod{{{m[i]}}}; z_{{{i + 1}}} = {(d * u[i]) % m[i]}\")\n",
    "        tmp1.append(f\"M_{{{i + 1}}} \\cdot z_{{{i + 1}}}\")\n",
    "        tmp2.append(f\"{c} \\cdot {(d * u[i]) % m[i]}\")\n",
    "    \n",
    "    ltx.append(f\"x = {' + '.join(tmp1)} = {' + '.join(tmp2)} = {x % M} \\\\pmod{{{M}}}\")\n",
    "\n",
    "    return ltx, x % M\n",
    "\n",
    "ltx, x = greco_chinese_theorem(ai, mi)\n",
    "for line in ltx:\n",
    "    display(Math(line))"
   ]
  },
  {
   "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": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}