{ "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": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 0 + \\Large\\frac{1}{\\Large\\frac{225}{157}}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 0 + \\Large\\frac{1}{1 + \\Large\\frac{1}{\\Large\\frac{157}{68}}}$" ], "text/plain": [ "" ] }, "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": [ "" ] }, "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": [ "" ] }, "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": [ "" ] }, "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": [ "" ] }, "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\n", "\n", "Ввести значения $a_i$ и $m_i$ выражения\n", "$$\\begin{cases}\n", "x \\equiv a_1 \\pmod{m_1} \\\\\n", "\\dots \\\\\n", "x \\equiv a_n \\pmod{m_n}\n", "\\end{cases}$$\n" ] }, { "cell_type": "code", "execution_count": 85, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle M = 4 \\cdot 9 = 36$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle M_{1} = 9; 9 x \\equiv 3 \\pmod{4}; z_{1} = 3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle M_{2} = 4; 4 x \\equiv 6 \\pmod{9}; z_{2} = 6$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle x = M_{1} \\cdot z_{1} + M_{2} \\cdot z_{2} = 9 \\cdot 3 + 4 \\cdot 6 = 15 \\pmod{36}$" ], "text/plain": [ "" ] }, "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": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a^1 \\pmod{37} = 3^1 \\pmod{37} = 3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a^2 \\pmod{37} = 3^2 \\pmod{37} = 9$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a^3 \\pmod{37} = 3^3 \\pmod{37} = 27$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a^4 \\pmod{37} = 3^4 \\pmod{37} = 7$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a^5 \\pmod{37} = 3^5 \\pmod{37} = 21$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a^6 \\pmod{37} = 3^6 \\pmod{37} = 26$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\text{Отсортированные пары:}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle (1, 3), (4, 7), (2, 9), (5, 21), (6, 26), (3, 27)$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a^{-r} = 3^{-7} = (3^7)^{-1} = 4^{-1} = 28 \\pmod{p}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a_1^{0} \\cdot 1 \\pmod{37} = 1$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a_1^{1} \\cdot 1 \\pmod{37} = 28$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle a_1^{2} \\cdot 1 \\pmod{37} = 7$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\text{Значение } a^{-r} \\cdot b \\text{ совпало с вторым значением пары } (4, 7)$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\text{Получаем результат: } k + ri = 4 + 7 \\cdot 2 = 18$" ], "text/plain": [ "" ] }, "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\n", "\n", "Ввести параметры кривой $a$, $b$, размер поля `field` и индекс точки в полученном отсортированном списке точек `pt_idx`." ] }, { "cell_type": "code", "execution_count": 157, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "a: 1\n", "b: 1\n" ] }, { "data": { "text/latex": [ "$\\displaystyle \\begin{array}{|c|c|c|c|}\n", "x & x^2 & x^3 + 1 \\cdot x + 1 & y \\\\\n", "0 & 0 & 1 & \\\\\n", "1 & 1 & 3 & \\\\\n", "2 & 4 & 0 & \\\\\n", "3 & -2 & -2 & \\\\\n", "4 & 5 & 3 & \\\\\n", "5 & 3 & -1 & \\\\\n", "-5 & 3 & 3 & \\\\\n", "-4 & 5 & -1 & \\\\\n", "-3 & -2 & 4 & \\\\\n", "-2 & 4 & 2 & \\\\\n", "-1 & 1 & -1 & \\\\\n", "\\end{array}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Порядок: 14\n", "Точки:\n", "(0, 1)\n", "(0, -1)\n", "(1, 5)\n", "(1, -5)\n", "(2, 0)\n", "(3, 3)\n", "(3, -3)\n", "(4, 5)\n", "(4, -5)\n", "(-3, 2)\n", "(-3, -2)\n", "(-5, 5)\n", "(-5, -5)\n", "None\n", "Проверяем точку (0, -1)\n" ] }, { "data": { "text/latex": [ "$\\displaystyle $" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = \\frac{3 \\cdot x_1^2 + a}{2 \\cdot y_1} = \\frac{3 \\cdot 0^2 + 1}{2 \\cdot 10} = \\frac{3 \\cdot 0 + 1}{20} = \\frac{1}{20}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = 1 \\cdot 20^{-1} = 1 \\cdot 5 = 5 \\pmod{11} = 5$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle x_3 = \\lambda^2 - x_1 - x_2 = 5^2 - 0 - 0 = 25 - 0 - 0 = 25 \\pmod{11} = 3 = 3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle y_3 = \\lambda \\cdot (x_1 - x_3) - y_1 = 5 \\cdot (0 - 3) - 10 = 5 \\cdot -3 - 10 = -15 - 10 = -25 \\pmod{11} = 8 = -3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 2P = P + P = (0, -1) + (0, -1) = (3, -3)$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle $" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = \\frac{y_2 - y_1}{x_2 - x_1} = \\frac{10 - 8}{0 - 3} = \\frac{2}{-3}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = 2 \\cdot -3^{-1} = 2 \\cdot 7 = 14 \\pmod{11} = 3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle x_3 = \\lambda^2 - x_1 - x_2 = 3^2 - 3 - 0 = 9 - 3 - 0 = 6 \\pmod{11} = 6 = -5$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle y_3 = \\lambda \\cdot (x_1 - x_3) - y_1 = 3 \\cdot (3 - 6) - 8 = 3 \\cdot -3 - 8 = -9 - 8 = -17 \\pmod{11} = 5 = 5$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 3P = 2P + P = (3, -3) + (0, -1) = (-5, 5)$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle $" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = \\frac{y_2 - y_1}{x_2 - x_1} = \\frac{10 - 5}{0 - 6} = \\frac{5}{-6}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = 5 \\cdot -6^{-1} = 5 \\cdot 9 = 45 \\pmod{11} = 1$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle x_3 = \\lambda^2 - x_1 - x_2 = 1^2 - 6 - 0 = 1 - 6 - 0 = -5 \\pmod{11} = 6 = -5$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle y_3 = \\lambda \\cdot (x_1 - x_3) - y_1 = 1 \\cdot (6 - 6) - 5 = 1 \\cdot 0 - 5 = 0 - 5 = -5 \\pmod{11} = 6 = -5$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 4P = 3P + P = (-5, 5) + (0, -1) = (-5, -5)$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle $" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = \\frac{y_2 - y_1}{x_2 - x_1} = \\frac{10 - 6}{0 - 6} = \\frac{4}{-6}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = 4 \\cdot -6^{-1} = 4 \\cdot 9 = 36 \\pmod{11} = 3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle x_3 = \\lambda^2 - x_1 - x_2 = 3^2 - 6 - 0 = 9 - 6 - 0 = 3 \\pmod{11} = 3 = 3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle y_3 = \\lambda \\cdot (x_1 - x_3) - y_1 = 3 \\cdot (6 - 3) - 6 = 3 \\cdot 3 - 6 = 9 - 6 = 3 \\pmod{11} = 3 = 3$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 5P = 4P + P = (-5, -5) + (0, -1) = (3, 3)$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle $" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = \\frac{y_2 - y_1}{x_2 - x_1} = \\frac{10 - 3}{0 - 3} = \\frac{7}{-3}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\lambda = 7 \\cdot -3^{-1} = 7 \\cdot 7 = 49 \\pmod{11} = 5$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle x_3 = \\lambda^2 - x_1 - x_2 = 5^2 - 3 - 0 = 25 - 3 - 0 = 22 \\pmod{11} = 0 = 0$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle y_3 = \\lambda \\cdot (x_1 - x_3) - y_1 = 5 \\cdot (3 - 0) - 3 = 5 \\cdot 3 - 3 = 15 - 3 = 12 \\pmod{11} = 1 = 1$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 6P = 5P + P = (3, 3) + (0, -1) = (0, 1)$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle $" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\text{Координаты } x \\text{ данных точек одинаковы} \\implies \\text{ сумма равна } \\mathcal{O}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle 7P = 6P + P = (0, 1) + (0, -1) = \\mathcal{O}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/latex": [ "$\\displaystyle \\text{Порядок точки } (0, -1) \\text{ равен } 7$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "a, b, field, pt_idx = 1, 1, 11, 1\n", "\n", "from math import gcd\n", "\n", "def point_neg(point, A, B, p):\n", " if not is_on_curve(point, A, B, p):\n", " raise RuntimeError\n", " if point is None:\n", " return point\n", " \n", " x, y = point\n", "\n", " result = x, -y % p\n", " if not is_on_curve(result, A, B, p):\n", " raise RuntimeError\n", " return result\n", "\n", "def extended_gcd(a, b):\n", " if a == 0:\n", " return b, 0, 1\n", " else:\n", " gcd, x, y = extended_gcd(b % a, a)\n", " return gcd, y - (b // a) * x, x\n", "\n", "def inverse_mod(k, p):\n", " if k < 0:\n", " return p - inverse_mod(-k, p)\n", " gcd, x, _ = extended_gcd(k, p)\n", " if gcd == 1:\n", " if x < 0:\n", " x += p\n", " return x\n", " else:\n", " raise RuntimeError\n", "\n", "def is_on_curve(point, A, B, p):\n", " if point is None:\n", " return True\n", "\n", " x, y = point\n", " return (y ** 2 - x ** 3 - A * x - B) % p == 0\n", "\n", "\n", "def point_addition(point1, point2, A, B, p):\n", " display(Math(''))\n", " if not is_on_curve(point1, A, B, p) or not is_on_curve(point2, A, B, p):\n", " raise RuntimeError\n", "\n", " if point1 is None:\n", " return point2\n", " elif point2 is None:\n", " return point1\n", "\n", " x1, y1 = point1\n", " x2, y2 = point2\n", "\n", " if x1 - x2 == 0 and y1 != y2:\n", " display(Math(r'\\text{Координаты } x \\text{ данных точек одинаковы} \\implies \\text{ сумма равна } \\mathcal{O}'))\n", " return None\n", "\n", " if x1 == x2:\n", " display(Math(fr\"\\lambda = \\frac{{3 \\cdot x_1^2 + a}}{{2 \\cdot y_1}} = \\frac{{3 \\cdot {x1}^2 + {A}}}{{2 \\cdot {y1}}} = \\frac{{3 \\cdot {x1 * x1} + {A}}}{{{2 * y1}}} = \\frac{{{3 * x1 * x1 + A}}}{{{2 * y1}}}\"))\n", " # print(f\"\\talpha = (3 * x1^2 + a) / (2 * y1) = (3 * {x1}^2 + {A}) / (2 * {y1}) = (3 * {x1 * x1} + {A}) / {2 * y1} = {3 * x1 * x1 + A} / {2 * y1}\")\n", " num = (3 * x1 ** 2 + A)\n", " den = 2 * y1\n", " else:\n", " display(Math(fr\"\\lambda = \\frac{{y_2 - y_1}}{{x_2 - x_1}} = \\frac{{{y2} - {y1}}}{{{x2} - {x1}}} = \\frac{{{y2 - y1}}}{{{x2 - x1}}}\"))\n", " # print(f\"\\talpha = (y2 - y1) / (x2 - x1) = ({y2} - {y1}) / ({x2} - {x1}) = {y2 - y1} / {x2 - x1}\")\n", " num = y2 - y1\n", " den = x2 - x1\n", "\n", " if gcd(den, p) != 1:\n", " return None\n", "\n", " m = num * inverse_mod(den, p)\n", " display(Math(fr\"\\lambda = {num} \\cdot {den}^{{-1}} = {num} \\cdot {inverse_mod(den, p)} = {m} \\pmod{{{p}}} = {m % p}\"))\n", " # print(f\"\\talpha = {num} * {inverse_mod(den, p)} = {m} (mod {p}) = {m % p}\")\n", " m = m % p\n", "\n", " x3 = m * m - x1 - x2\n", " display(Math(fr\"x_3 = \\lambda^2 - x_1 - x_2 = {m}^2 - {x1} - {x2} = {m * m} - {x1} - {x2} = {x3} \\pmod{{{p}}} = {x3 % p} = {mm(x3 % p)}\"))\n", " # print(f\"\\tx3 = alpha^2 - x1 - x2 = {m}^2 - {x1} - {x2} = {m * m} - {x1} - {x2} = {x3} (mod {p}) = {x3 % p}\")\n", " x3 = x3 % p\n", "\n", " y3 = m * (x1 - x3) - y1\n", " display(Math(fr\"y_3 = \\lambda \\cdot (x_1 - x_3) - y_1 = {m} \\cdot ({x1} - {x3}) - {y1} = {m} \\cdot {x1 - x3} - {y1} = {m * (x1 - x3)} - {y1} = {y3} \\pmod{{{p}}} = {y3 % p} = {mm(y3 % p)}\"))\n", " # print(f\"\\ty3 = alpha * (x1 - x3) - y1 = {m} * ({x1} - {x3}) - {y1} = {m} * {x1 - x3} - {y1} = {m * (x1 - x3)} - {y1} = {y3} (mod {p}) = {y3 % p}\")\n", " y3 = y3 % p\n", " result = (x3 % p, y3 % p)\n", " if not is_on_curve(result, A, B, p):\n", " raise RuntimeError\n", " return result\n", "\n", "\n", "def mm(x):\n", " if x <= 5:\n", " return x\n", " else:\n", " return x - field\n", "\n", "def mmm(p):\n", " return (mm(p[0]), mm(p[1]))\n", "\n", "N = 1\n", "\n", "print(\"a: \", a)\n", "print(\"b: \", b)\n", "\n", "\n", "points = []\n", "\n", "tmp = []\n", "for x in range(field):\n", " ys = (x * x) % field\n", " xs = (x * x * x + a * x + b) % field\n", " tmp.append((mm(x), mm(ys), mm(xs)))\n", " # print(f\"x = {mm(x)}; x^2 = {mm(ys)}; x^3 + ax + b = {mm(xs)}\")\n", "\n", "ltx = [r\"\\begin{array}{|c|c|c|c|}\", fr\"x & x^2 & x^3 + {a} \\cdot x + {b} & y \\\\\"]\n", "for (x, x2, x3) in tmp:\n", " ltx.append(fr\"{x} & {x2} & {x3} & \\\\\")\n", "ltx.append(r\"\\end{array}\")\n", "display(Math('\\n'.join(ltx)))\n", "\n", "for x in range(field):\n", " sqrt_y = x * x * x + a * x + b\n", " for y in range(field):\n", " if (y * y) % field == sqrt_y % field:\n", " N += 1\n", " points.append((x, y))\n", "\n", "def sort_key(a):\n", " m = list(mmm(a))\n", " if m[0] < 0:\n", " m[0] = abs(m[0]) + 1e9\n", " if m[1] < 0:\n", " m[1] = abs(m[1]) + 1e9\n", " return tuple(m)\n", "\n", "points.sort(key=sort_key)\n", "points = points + [None]\n", "\n", "print(\"Порядок:\", N)\n", "print(\"Точки:\")\n", "pts_print = []\n", "for pt in points:\n", " if pt is not None:\n", " pt = mmm(pt)\n", " print(pt)\n", "\n", "\n", "pt = points[pt_idx]\n", "print(f\"Проверяем точку {mmm(pt)}\")\n", "\n", "kpts = set([pt])\n", "last = pt\n", "for k in range(2, N + 1):\n", " try:\n", " kpt = point_addition(last, pt, a, b, field)\n", "\n", " last1 = mm(last[0]), mm(last[1])\n", " if kpt is not None:\n", " kpt1 = mm(kpt[0]), mm(kpt[1])\n", " else:\n", " kpt1 = r'\\mathcal{O}'\n", " pt1 = mm(pt[0]), mm(pt[1])\n", " \n", " if k != 2:\n", " display(Math(f\"{k}P = {k - 1}P + P = {last1} + {pt1} = {kpt1}\"))\n", " else:\n", " display(Math(f\"{k}P = P + P = {last1} + {pt1} = {kpt1}\"))\n", " last = kpt\n", " if kpt is not None:\n", " kpts.add(kpt)\n", " else:\n", " break\n", " except RuntimeError:\n", " break\n", "\n", "pt1 = mm(pt[0]), mm(pt[1])\n", "display(Math(fr\"\\text{{Порядок точки }} {pt1} \\text{{ равен }} {k}\"))\n" ] } ], "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 }