shklyarik_practice.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e3b2c6a3-dc01-4d20-9890-d0c82313f9ae",
   "metadata": {},
   "source": [
    "# Эндоморфизмы эллиптических кривых и проблема дискретного логарифма. Решение задачи дискретного логарифмирования в частном случае"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "514f04ed-2ccd-4a45-a0ce-4b51c7a1e620",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Некоторые необходимые для создания классов Curve и Point функции "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "afb39715-a7c1-4d42-b72b-151fe5dabdf8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "from sympy import randprime \n",
    "import time\n",
    "\n",
    "def st(n):\n",
    "    s = 0\n",
    "    t = n\n",
    "    while t % 2 == 0:\n",
    "        s += 1\n",
    "        t = t // 2\n",
    "    return s, t\n",
    "\n",
    "def Jacobi(a,n):\n",
    "    if n < 0 or not n % 2:\n",
    "        raise ValueError(\"n should be an odd positive integer\") \n",
    "    j = 1\n",
    "    if n == 1:\n",
    "        return j\n",
    "    if a<0:\n",
    "        a = -a\n",
    "        if n%4 == 3:\n",
    "            j = -j\n",
    "    while n>1:\n",
    "        if a == 0:\n",
    "            return 0\n",
    "        s,t = st(a)\n",
    "        if (s%2 == 1) & (n%8 in [3, 5]):\n",
    "            j = -j\n",
    "        if 3 == n%4 == t%4:\n",
    "            j = -j\n",
    "        a = n%t\n",
    "        n = t\n",
    "    return j\n",
    "\n",
    "def Shanks(a, p):\n",
    "    if a % p == 0:\n",
    "        return 0\n",
    "    if not Jacobi(a, p) == 1: \n",
    "        return \"no solution\"\n",
    "    s,t = st(p-1)             \n",
    "    n = randint(2,p-2) \n",
    "    while Jacobi(n,p) == 1:   \n",
    "        n = randint(2,p-2)\n",
    "    b = pow(n,t,p)            \n",
    "    r = pow(a,(t+1)//2,p)     \n",
    "    d = 0\n",
    "    f = pow(a,t,p)            \n",
    "    b2 = b\n",
    "    for i in range(1,s):      \n",
    "        b2 = b2*b2 % p        \n",
    "        if not pow(f,2**(s-1-i), p) == 1:  \n",
    "            d += 2**i                   \n",
    "            f = f*b2 % p                 \n",
    "    return r*pow(b,d//2,p) % p          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7b575175-1808-4431-9565-67136a1ae511",
   "metadata": {},
   "outputs": [],
   "source": [
    "def D(a,b):\n",
    "    return 27*b**2 + 4*a**3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17443bff-ab9a-4325-9a58-7122d86ccbcd",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Реализация классов Point (infPoint) и Curve для работы с точками эллиптической кривой"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "104f6821-d244-4b3c-aa00-1eef3dc005ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Point:\n",
    "    def __init__(self,x,y, curve):\n",
    "        self.curve = curve\n",
    "        x %= self.curve.p\n",
    "        y %= self.curve.p\n",
    "        if not self.curve.isPoint(x,y):\n",
    "            print(\"Ошибка! Точка не лежит на кривой!\")\n",
    "        else:\n",
    "            self.x = x \n",
    "            self.y = y \n",
    "            \n",
    "    def __eq__(self, other):\n",
    "        if isinstance(other, self.__class__):\n",
    "            return (self.x == other.x) and (self.y == other.y) and (self.curve == other.curve)\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"({self.x}, {self.y})\"\n",
    "    \n",
    "    def __neg__(self):\n",
    "        return Point(self.x, -self.y, self.curve)\n",
    "    \n",
    "    def doubling(self):\n",
    "        y1 = self.y\n",
    "        x1 = self.x\n",
    "        if y1 == 0:\n",
    "            return infPoint(self.curve)\n",
    "        else:\n",
    "            k = (3*(x1*x1 % self.curve.p) + self.curve.a)*pow((2*y1),-1, self.curve.p) % self.curve.p  \n",
    "            x3 = k*k % self.curve.p - 2*x1            \n",
    "            y3 = k*(x1-x3) - y1        \n",
    "            return Point(x3,y3, self.curve)\n",
    "        \n",
    "    def __add__(self, P):\n",
    "        if isinstance(P, infPoint):\n",
    "            return self\n",
    "        y1 = self.y\n",
    "        x1 = self.x\n",
    "        y2 = P.y\n",
    "        x2 = P.x\n",
    "        if x1 == x2:\n",
    "            if y1 == y2 == 0:\n",
    "                return infPoint(self.curve)\n",
    "            elif y1 != y2:\n",
    "                return infPoint(self.curve)\n",
    "            else:\n",
    "                k = (3*(x1*x1 % self.curve.p) + self.curve.a)*pow((2*y1),-1, self.curve.p) % self.curve.p  \n",
    "                x3 = k*k % self.curve.p - 2*x1            \n",
    "                y3 = k*(x1-x3) - y1        \n",
    "                return Point(x3,y3, self.curve)\n",
    "        k = (y2-y1)*pow((x2 - x1), -1, self.curve.p) % self.curve.p       \n",
    "        x3 = k*k % self.curve.p - x1- x2                        \n",
    "        y3 = k*(x1-x3) - y1                     \n",
    "        return Point(x3,y3, self.curve)\n",
    "        \n",
    "    def __sub__(self,P):\n",
    "        return self + (-P)\n",
    "    \n",
    "    def __mul__(self, m):\n",
    "        if isinstance(m, int):\n",
    "            if m < 0:\n",
    "                m = -m\n",
    "                self = -self\n",
    "            m = bin(m)[2:]\n",
    "            result = infPoint(self.curve)\n",
    "            Q = self\n",
    "            for i in m[::-1]:\n",
    "                if i == \"1\":\n",
    "                    result = result + Q\n",
    "                Q += Q\n",
    "            return result\n",
    "        else:\n",
    "            return f\"{m} должно быть целым числом\"\n",
    "        \n",
    "    def __rmul__(self,m):\n",
    "        return self*m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2d909a59-b1cc-4434-9ffd-3e4180dc7943",
   "metadata": {},
   "outputs": [],
   "source": [
    "class infPoint():\n",
    "    def __init__(self, curve):\n",
    "        self.curve = curve\n",
    "    def __neg__(self):\n",
    "        return self  \n",
    "    def __add__(self, P):\n",
    "        return P\n",
    "    def __sub__(self,P):\n",
    "        return self + (-P)\n",
    "    def __repr__(self):\n",
    "        return \"O\"\n",
    "    def __mul__(self, m):\n",
    "        return self\n",
    "    def __rmul__(self, m):\n",
    "        return self\n",
    "    def toProjective(self):\n",
    "        return ProjectivePoint(0,1,0,self.curve.toProjective())\n",
    "    def toJacobian(self):\n",
    "        return JacobianPoint(1,1,0,self.curve.toJacobian())\n",
    "    def toChudnovskyJacobian(self):\n",
    "        return ChudnovskyJacobianPoint(1,1,0,0,0,self.curve.toChudnovskyJacobian())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c4493ee1-58d4-4640-896e-ca929a61cecf",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Curve:\n",
    "    def __init__(self,a,b,p):\n",
    "        if D(a,b) % p: \n",
    "            self.a = a % p\n",
    "            self.b = b % p\n",
    "            self.p = p\n",
    "        else:\n",
    "            print(\"Ошибка! Дискриминант кривой нулевой!\")\n",
    "            \n",
    "    def __eq__(self, other):\n",
    "        if isinstance(other, self.__class__):\n",
    "            return (self.a == other.a) and (self.b == other.b) and (self.p == other.p)\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def findPointsShanks(self):\n",
    "        points = []\n",
    "        for x in range(self.p):\n",
    "            a = (pow(x,3,self.p) + self.a*x + self.b) % self.p\n",
    "            y = Shanks(a, self.p)\n",
    "            if isinstance(y, int):\n",
    "                points.append(Point(x,y,self))\n",
    "                if y != ((self.p - y) % self.p):\n",
    "                    points.append(Point(x,-y, self))\n",
    "        points.append(infPoint(self))\n",
    "        return points\n",
    "    \n",
    "    def findRandomPoint(self):\n",
    "        while True:\n",
    "            x = randint(0, self.p - 1)\n",
    "            a = (pow(x,3,self.p) + self.a*x + self.b) % self.p\n",
    "            y = Shanks(a, self.p)\n",
    "            if isinstance(y, int):\n",
    "                return Point(x,y, self)\n",
    "    \n",
    "    def isPoint(self,x,y):\n",
    "        return not ((pow(y,2,self.p) - (pow(x,3,self.p) + self.a*x + self.b)) % self.p)\n",
    "        \n",
    "    def toProjective(self):\n",
    "        return ProjectiveCurve(self.a,self.b,self.p)\n",
    "    \n",
    "    def toJacobian(self):\n",
    "        return JacobianCurve(self.a,self.b,self.p)\n",
    "    \n",
    "    def toChudnovskyJacobian(self):\n",
    "        return ChudnovskyJacobianCurve(self.a,self.b,self.p)\n",
    "    \n",
    "    def curveOrder(self):\n",
    "        return len(self.findPointsShanks())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb213638-ab79-46ba-acdb-bf0e73be694e",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Реализация алгоритмов для вычисления дискретного логарифма эллиптической кривой"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9556f321-ed45-487b-b7e0-91d31f8a271a",
   "metadata": {},
   "source": [
    "Исходный код функции `nthroot_mod` из `sympy.ntheory.residue_ntheory`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "fc5e65d3-5ed4-47e6-93fe-1be0b5dd4eac",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy.core.compatibility import as_int\n",
    "from sympy.core.numbers import igcd, igcdex, mod_inverse\n",
    "from sympy.ntheory.residue_ntheory import is_nthpow_residue\n",
    "from sympy.ntheory.residue_ntheory import primitive_root\n",
    "from sympy.ntheory.residue_ntheory import _nthroot_mod1\n",
    "def nthroot_mod(a, n, p, all_roots = False):\n",
    "    \"\"\"\n",
    "    Find the solutions to ``x**n = a mod p``\n",
    "\n",
    "    Parameters\n",
    "    ==========\n",
    "\n",
    "    a : integer\n",
    "    n : positive integer\n",
    "    p : positive integer\n",
    "    all_roots : if False returns the smallest root, else the list of roots\n",
    "\n",
    "    Examples\n",
    "    ========\n",
    "\n",
    "    >>> from sympy.ntheory.residue_ntheory import nthroot_mod\n",
    "    >>> nthroot_mod(11, 4, 19)\n",
    "    8\n",
    "    >>> nthroot_mod(11, 4, 19, True)\n",
    "    [8, 11]\n",
    "    >>> nthroot_mod(68, 3, 109)\n",
    "    23\n",
    "    \"\"\"\n",
    "    from sympy.core.numbers import igcdex\n",
    "    a, n, p = as_int(a), as_int(n), as_int(p)\n",
    "    if n == 2:\n",
    "        return sqrt_mod(a, p, all_roots)\n",
    "    # see Hackman \"Elementary Number Theory\" (2009), page 76\n",
    "    if not is_nthpow_residue(a, n, p):\n",
    "        return None\n",
    "    if primitive_root(p) is None:\n",
    "        raise NotImplementedError(\"Not Implemented for m without primitive root\")\n",
    "\n",
    "    if (p - 1) % n == 0:\n",
    "        return _nthroot_mod1(a, n, p, all_roots)\n",
    "    # The roots of ``x**n - a = 0 (mod p)`` are roots of\n",
    "    # ``gcd(x**n - a, x**(p - 1) - 1) = 0 (mod p)``\n",
    "    pa = n\n",
    "    pb = p - 1\n",
    "    b = 1\n",
    "    if pa < pb:\n",
    "        a, pa, b, pb = b, pb, a, pa\n",
    "    while pb:\n",
    "        # x**pa - a = 0; x**pb - b = 0\n",
    "        # x**pa - a = x**(q*pb + r) - a = (x**pb)**q * x**r - a =\n",
    "        #             b**q * x**r - a; x**r - c = 0; c = b**-q * a mod p\n",
    "        q, r = divmod(pa, pb)\n",
    "        c = pow(b, q, p)\n",
    "        c = igcdex(c, p)[0]\n",
    "        c = (c * a) % p\n",
    "        pa, pb = pb, r\n",
    "        a, b = b, c\n",
    "    if pa == 1:\n",
    "        if all_roots:\n",
    "            res = [a]\n",
    "        else:\n",
    "            res = a\n",
    "    elif pa == 2:\n",
    "        return sqrt_mod(a, p , all_roots)\n",
    "    else:\n",
    "        res = _nthroot_mod1(a, pa, p, all_roots)\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e79b075b-65c9-44e2-bf4b-55069ba1fbb3",
   "metadata": {},
   "source": [
    "Зададим функцию для использования эндоморфизма $\\phi: (x, y) \\mapsto(\\beta x, y)$ и $\\mathcal{O} \\mapsto \\mathcal{O}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ea00133f-ea20-4ce6-94a1-665e4256e79e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def end(p, beta):\n",
    "    if isinstance(p, infPoint):\n",
    "        return infPoint(p.curve)\n",
    "    return Point(p.x*beta, p.y, p.curve)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6697ae56-2ab3-43a9-8f3c-1bb695436ce1",
   "metadata": {},
   "source": [
    "1. Решение уравнения $xG = P_1$ по известному решению уравнения $xG = P_2$, где $P_1$ и $P_2$ имеют одинаковую координату $y$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "6504192f-420b-44a5-b28c-079c6ad69ad9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dLogSolver(p, n, P1, P2, t, b = None, l = None):\n",
    "    if not b:\n",
    "        b = nthroot_mod(1, 3, p, True)[1]\n",
    "    if not l:\n",
    "        l = nthroot_mod(1, 3, n, True)[1]\n",
    "    if end(P1, b) == P2:\n",
    "        x = t*pow(l,-1, n) % n\n",
    "    else:\n",
    "        x = t*pow(l**2, -1, n) % n\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91fe963c-a30a-4670-9977-3059cb482440",
   "metadata": {},
   "source": [
    "2. Решение уравнения $xG = P_1$ по известному решению уравнения $xG = P_2 - P_1$, где $P_1$ и $P_2$ имеют одинаковую координату $y$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "9279d159-4904-4271-b7a4-1a0f2a10300c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def dLogSolverDif(p, n, P1, dif, t, b = None, l = None):\n",
    "    P2 = dif + P1\n",
    "    if not b:\n",
    "        b = nthroot_mod(1, 3, p, True)[1]\n",
    "    if not l:\n",
    "        l = nthroot_mod(1, 3, n, True)[1]\n",
    "    if end(P1, b) == P2:\n",
    "        x = t*pow(l - 1,-1, n) % n\n",
    "    else:\n",
    "        x = t*pow(l**2 - 1, -1, n) % n\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d3b132b-3d7d-4347-b042-4e6bb3dc9fcb",
   "metadata": {},
   "source": [
    "## Тестирование алгоритмов на кривой небольшого порядка"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "cb15c3ab-edd8-4e93-a83c-d725ae79ee15",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = 43\n",
    "p % 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "d386109f-c22d-452b-8540-1894ce1b0090",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 31),\n",
       " (2, 12),\n",
       " (7, 36),\n",
       " (7, 7),\n",
       " (12, 31),\n",
       " (12, 12),\n",
       " (13, 21),\n",
       " (13, 22),\n",
       " (20, 40),\n",
       " (20, 3),\n",
       " (21, 25),\n",
       " (21, 18),\n",
       " (25, 25),\n",
       " (25, 18),\n",
       " (29, 31),\n",
       " (29, 12),\n",
       " (32, 40),\n",
       " (32, 3),\n",
       " (34, 40),\n",
       " (34, 3),\n",
       " (35, 21),\n",
       " (35, 22),\n",
       " (37, 36),\n",
       " (37, 7),\n",
       " (38, 21),\n",
       " (38, 22),\n",
       " (40, 25),\n",
       " (40, 18),\n",
       " (42, 36),\n",
       " (42, 7),\n",
       " O]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = Curve(0,7,p)\n",
    "c.findPointsShanks()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "7df847f8-bdfd-4beb-9c54-2f24c292b4f5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = c.curveOrder()\n",
    "n % 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5746e479-27ac-4e13-95c4-7e832750d04a",
   "metadata": {},
   "source": [
    "Рассмотрим первую задачу.\n",
    "\n",
    "Выберем следующие исходные данные:\n",
    "+ $G = (12, 31)$\n",
    "+ $P_1 = (32, 40)$\n",
    "+ $P_2 = 23G = (20, 40)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "eebf1789-54f5-42f0-b3ba-4c9ab80a4ca4",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = Point(12, 31, c)\n",
    "P1 = Point(32, 40, c)\n",
    "P2 = Point(20, 40, c)\n",
    "t = 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0506711a-2f5d-4b0f-afcb-105a9132ff88",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sol1 = dLogSolver(p, n, P1, P2, t)\n",
    "sol1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "674def3b-fe73-4d51-b8e0-8cf9ae4b23ad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(32, 40) (32, 40)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(G*sol1, P1)\n",
    "G*sol1 == P1 # получили верный ответ"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc5769c4-3611-4adc-89ed-5ec80fdf08d3",
   "metadata": {},
   "source": [
    "Для решения второй задачи выберем новые исходные данные:\n",
    "+ $G = (42, 36)$\n",
    "+ $P_1 = (25,18)$\n",
    "+ $P_2 = (21,18)$\n",
    "+ $(P2 - P1) = 22G = (35, 22)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ccf7b4ea-fdd6-47aa-be97-9e2f98fc9e92",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = Point(42,36,c)\n",
    "P1 = Point(25,18,c)\n",
    "P2 = Point(21,18,c)\n",
    "t = 22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "c225e6df-a14d-425c-977a-e9d567a41d24",
   "metadata": {},
   "outputs": [],
   "source": [
    "sol2 = dLogSolverDif(p, n, P1, P2 - P1, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "87e5c30d-9c70-4620-b045-692ea00cfdf0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(25, 18) (25, 18)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(sol2*G, P1)\n",
    "G*sol2 == P1 # получили верный ответ"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2961c03-64ae-417a-9794-75bb3dd261cb",
   "metadata": {},
   "source": [
    "## Тестирование алгоритмов на кривой SECP256k1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "e0b7354f-a3cc-4e13-a909-69d8a020fc50",
   "metadata": {},
   "outputs": [],
   "source": [
    "p = 115792089237316195423570985008687907853269984665640564039457584007908834671663\n",
    "SECP256k1 = Curve(0, 7, p)\n",
    "n = 115792089237316195423570985008687907852837564279074904382605163141518161494337\n",
    "b = 55594575648329892869085402983802832744385952214688224221778511981742606582254\n",
    "l = 37718080363155996902926221483475020450927657555482586988616620542887997980018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "f10166da-3fcf-404b-bb3f-03238dcee576",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 1)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p%3, n%3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b3a1a98-2e45-442b-8e94-16f9ea010c5a",
   "metadata": {},
   "source": [
    "Зададим следующие параметры:\n",
    "+ $G = (43972058008956600510070150284766821022977458755289054035007856031232840643000, 51855161223576362722185940022860364125581297957735844065328061563388767261889)$\n",
    "+ $P_1 = (106425298635331082471917436389928683282463065844388670776519822248290723610944, 34945961817953480676324849611701869571657592225822792221501648520056584636503)$\n",
    "+ $P_2 = 876349152G =(99611287690666069782340804267622554666571445305230259955467091930852038341810, 34945961817953480676324849611701869571657592225822792221501648520056584636503)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "697f41f1-fa60-4b30-b4e3-c6d82d7aae3e",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = Point(43972058008956600510070150284766821022977458755289054035007856031232840643000, 51855161223576362722185940022860364125581297957735844065328061563388767261889, SECP256k1)\n",
    "P1 = Point(106425298635331082471917436389928683282463065844388670776519822248290723610944, 34945961817953480676324849611701869571657592225822792221501648520056584636503, SECP256k1)\n",
    "P2 = Point(99611287690666069782340804267622554666571445305230259955467091930852038341810, 34945961817953480676324849611701869571657592225822792221501648520056584636503, SECP256k1)\n",
    "t = 876349152"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "3dd2511e-3faf-4001-9721-6e8eacc54834",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "58954822210603468252214086162047578713591482914170349323264093426055053402803"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sol3 = dLogSolver(p, n, P1, P2, t, b, l)\n",
    "sol3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "0f7b2df6-8548-4ef6-b65b-dcf71ebfcb51",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sol3*G == P1 #получили верный ответ"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6cab691-b768-4418-a7af-1b3d5c511196",
   "metadata": {},
   "source": [
    "Для второй задачи выберем другие данные:\n",
    "+ $G = (39461403700986745438887632700736590506022318167932797587556248728463688478273,5167084641483602694706148308472026672006224131072422397043928705280825404911)$\n",
    "+ $P_1 = (29504267309223397090056414194879693394903635186795986539925375262018400605330, 2700387467372297884102013513072671864733541412877449417142217900456736081571)$\n",
    "+ $P_2 = 35416965966288193029253887080699235993332046944537972994674884479846800530688, 2700387467372297884102013513072671864733541412877449417142217900456736081571)$\n",
    "+ $P_2 - P_1 = 2G = (22652517870328640072629002346542970354171872300069809619334405179449632131455, 37389770910085060872490402131497203789856670372833309420913746515394634041417)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "633f0e27-79dc-4994-9976-e3a018c7d190",
   "metadata": {},
   "outputs": [],
   "source": [
    "G = Point(39461403700986745438887632700736590506022318167932797587556248728463688478273,5167084641483602694706148308472026672006224131072422397043928705280825404911, SECP256k1)\n",
    "P1 = Point(29504267309223397090056414194879693394903635186795986539925375262018400605330, 2700387467372297884102013513072671864733541412877449417142217900456736081571, SECP256k1)\n",
    "P2 = Point(35416965966288193029253887080699235993332046944537972994674884479846800530688, 2700387467372297884102013513072671864733541412877449417142217900456736081571, SECP256k1)\n",
    "t = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1ec50d5f-2f99-4b6a-8f17-f767eb02ba94",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "52049339249440132347096509016808591601273271149061544929325695065753442342878"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sol4 = dLogSolverDif(p, n, P1, P2-P1, t, b, l)\n",
    "sol4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "73871992-9203-45ba-961e-43e5627549cc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G*sol4 == P1 # получили верный ответ"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}