Theorie_SIDH.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "based-passport",
   "metadata": {},
   "source": [
    "# Die Mathematik des SIDH"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "graphic-senior",
   "metadata": {},
   "source": [
    "Dieses Notebook benötigt das Jupyter-SageMath-9.0-Kernel. \n",
    "Eine Installationsanleitung finden Sie im Textdokument \"Einführung\" innerhalb des Projektanhangs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "significant-apple",
   "metadata": {},
   "source": [
    "***\n",
    "$\\mathbf{\\text{Galois-Feld}}$<br>\n",
    "***\n",
    "1.&emsp;Galois-Feld mit Primcharakteristik $$GF(p) = \\{\\ a\\ ; a\\ mod\\ p\\}$$\n",
    "2.&emsp;Quadratische Erweiterung: $$GF(p^2) = GF(i) = \\{\\ a*z_2 + b\\ ; a,b \\in GF(p)\\ \\}$$\n",
    "***\n",
    "$$GF(7) = \\{0, 1, 2, 3, 4, 5, 6 \\}$$ \n",
    "$$GF(p^2) = GF(i) = \\{\\ a*z_2 + b\\ ; a,b \\in GF(7)\\ \\}$$ \n",
    "$$\\vert GF(7) \\vert = 7$$ \n",
    "$$\\vert(GF(7^2) \\vert = 49$$ "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "architectural-mistress",
   "metadata": {},
   "source": [
    "Ein Galoisfeld ist also grundsätzlich die Menge aller Ganzzahlen, die nach modularer Reduktion durch die Primcharakteristik entstehen. Die quadratische Erweiterung besteht aus der Menge aller möglichen Polynome der Grads größer gleich $1$, mit Koeffizienten aus dem Basisfeld [4]. Im Folgenden ein Beispiel mit $GF(7)$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "mounted-lodge",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Order of GF(p): 7\n",
      "Order of GF(p^2): 49\n"
     ]
    }
   ],
   "source": [
    "galois = GF(7)\n",
    "quadratic_extension = GF(7^2)\n",
    "print(\"Order of GF(p): \" + str(galois.order()))\n",
    "print(\"Order of GF(p^2): \" + str(quadratic_extension.order()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "worth-joining",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "galois.random_element()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "introductory-canon",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3*z2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quadratic_extension.random_element()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "asian-eight",
   "metadata": {},
   "source": [
    "***\n",
    "$\\mathbf{\\text{Isogenien}}$<br>\n",
    "***\n",
    "Eine Isogenie ist eine nicht-konstante rationale Abbildung mit endlichem Kern: $$\\phi : E_0 \\rightarrow E_1$$\n",
    "Eine Isogenie ist durch ihren Kern eindeutig identifizierbar: $$ G = \\{ P_1 , P_2, ..., P_n\\} \\in E_0$$ </br> $$G \\subset E_0$$\n",
    "$$\\phi(G) = \\mathcal{O}$$\n",
    "***\n",
    "$$E_0: y^2 = x^3 + 2x + 3,\\ E_0 \\subset GF(11)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unique-texas",
   "metadata": {},
   "source": [
    "Die Besonderheit einer Isogenie besteht vor allem daraus, dass diese die Gruppenstruktur erhält. Nach Abbildung einer elliptischen Kurve $E_0$ durch die Isogenie $\\phi$ auf die Bildkurve $\\phi(E_0) = E_1$ besitzt $E_1$ ebenfalls wieder die im Notebook \"Grundlagen\" besprochene Gruppenstuktur _[3]_. Eine Isogenie ist somit immer ein Gruppenhomomorphismus.\n",
    "Im Folgenden wird eine Isogenie der Ordnung $8$ konstruiert, womit der Kern dieser Isogenie $8$ Elemente besitzt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "electronic-covering",
   "metadata": {},
   "outputs": [],
   "source": [
    "k = GF(11)\n",
    "E = EllipticCurve(k,[1,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "pointed-minimum",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk4AAAGFCAYAAAALnnwfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAdIklEQVR4nO3df5BddX3/8deyyCZhdi8STEJkA0GjsKCQktWWID9awQrNQMehFaUiWMUaIDEzGihYkErSYKV0zAITqogyQf7gh2ilkkFM5FcJPyIUlIhEGqkxFOm9AXQZ4H7/yNcNkUg+CXdz7obHY+bM5Jy9937es0fJk3MP93Y0m81mAADYrB2qHgAAYKQQTgAAhYQTAEAh4QQAUEg4AQAUEk4AAIWEEwBAIeEEAFCo7cKp2Wym0WjE53ICAO2m7cJp3bp1qdVqWbduXdWjAABspO3CCQCgXW1xOC1btiwzZszIxIkT09HRkRtuuGGjnzebzZx33nmZOHFiRo8encMPPzwPPfRQywYGAKjKFofTs88+mwMOOCALFy7c5M8vvPDCXHTRRVm4cGGWL1+eCRMm5Mgjj/TWGwAw4nU0X8Nd2B0dHbn++utz3HHHJVl/tWnixImZPXt25s6dmyQZHBzM+PHjs2DBgpx66qmbfc1Go5FarZZ6vZ6enp6tHe1166mnkoGBpNlMPvWp5E1vqnoiANh+tPQep1WrVmXNmjU56qijho51dXXlsMMOyx133NHKpdiE559PDj88Offc5LzzksMOSwYHq54KALYfLQ2nNWvWJEnGjx+/0fHx48cP/ez3DQ4OptFobLSxdX7+8+S//mvD/o9/nDz6aGXjAMB2Z1j+q7qOjo6N9pvN5iuO/c78+fNTq9WGtt7e3uEY6XVh992TN75xw36tlrz5zdXNAwDbm5aG04QJE5LkFVeX1q5d+4qrUL9z1llnpV6vD22rV69u5UivK93dyXe/u/7tusMOS/7935Nddql6KgDYfuzYyhebPHlyJkyYkCVLlmTq1KlJkueffz5Lly7NggULNvmcrq6udHV1tXKM17U//uPk1lurngIAtk9bHE7PPPNMHn3ZjTOrVq3KihUrsuuuu2bSpEmZPXt25s2blylTpmTKlCmZN29exowZkw996EMtHRwAYFvb4nC65557csQRRwztz5kzJ0ly0kkn5Wtf+1o++9nP5je/+U0+9alP5emnn8673/3u3Hzzzenu7m7d1AAAFXhNn+M0HHyOEwDQrnxXHQBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhYQTAEAh4QQAUEg4AQAUaptwGhgYSF9fX/r7+6seBQBgk3zJLwBAoba54gQA0O6EEwBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhYQTAEAh4QQAUEg4AQAUet2F05e/nBx/fPLFLyYvvVT1NPBKDz+cfOQjyUc/mjz6aNXTsDUeeCA58cTklFOSn/+86mmAVupoNpvNqod4uUajkVqtlnq9np6enpa+9qWXJp/61Ib9f/qnZO7cli4Br8m6dcmUKcmvfrV+v7c3WbkyGTWq2rko9+tfJ297W/LUU+v39947eeSRZMcdq50LaI22ueI0MDCQvr6+9Pf3D9sad9756vtQtcce2xBNSbJ6dfLEE9XNw5ZbuXJDNCWvPKfAyNY24TRz5sw8/PDDWb58+bCtMX36q+9D1fbeO9l99w37e+6Z7LFHdfOw5d7+9mS33TbsT5mSjB9f3TxAa72uLh6feur6+5qWLUve9a5k9uyqJ4KNdXcnt96aLFiQ7LBDcvbZSVdX1VOxJd74xuQHP1h/H+VOOyWf+5y36WB78rq6xwkA4LVom7fqAADanXACACgknAAACgknAIBCwgkAoJBwAgAoJJwAAAoJJwCAQsIJAKCQcAIAKCScAAAKCScAgELCCQCgUNuE08DAQPr6+tLf31/1KAAAm9TRbDabVQ/xco1GI7VaLfV6PT09PVWPAwAwpG2uOAEAtDvhBABQSDgBABQSTgAAhYQTAEAh4QQAUEg4AQAUEk4AAIWEEwBAIeEEAFBIOAEAFGp5OL3wwgs555xzMnny5IwePTp77713zj///Lz00kutXgoAYJvasdUvuGDBglx22WW58sors99+++Wee+7JySefnFqtllmzZrV6OQCAbabl4XTnnXfm2GOPzTHHHJMk2WuvvXL11VfnnnvuafVSAADbVMvfqjvkkENyyy23ZOXKlUmSH/3oR7ntttty9NFHb/Lxg4ODaTQaG20AAO2o5Vec5s6dm3q9nn322SednZ158cUXc8EFF+SEE07Y5OPnz5+fz3/+860eAwCg5Vp+xemaa67JVVddlcWLF+e+++7LlVdemX/+53/OlVdeucnHn3XWWanX60Pb6tWrWz0SAEBLdDSbzWYrX7C3tzdnnnlmZs6cOXTsC1/4Qq666qr85Cc/2ezzG41GarVa6vV6enp6WjkaAMBr0vIrTs8991x22GHjl+3s7PRxBADAiNfye5xmzJiRCy64IJMmTcp+++2X+++/PxdddFFOOeWUVi8FALBNtfytunXr1uVzn/tcrr/++qxduzYTJ07MCSeckH/4h3/ITjvttNnne6sOAGhXLQ+n10o4AQDtynfVAQAUEk4AAIWEEwBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhdomnAYGBtLX15f+/v6qRwEA2CTfVQcAUKhtrjgBALQ74QQAUEg4AQAUEk4AAIWEEwBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhYQTAEAh4QQAv+eSS5Jx45K99kpuvrnqaWgnHc1ms1n1EC/XaDRSq9VSr9fT09NT9TgAvM785CdJX1/yu78du7uTp55K3vCGaueiPbTNFaeBgYH09fWlv7+/6lEAeB1bu3ZDNCXJunXJc89VNw/txRUnAHiZ3/42mT49ue++9fsf/GBy9dXVzkT72LHqAQCgnYwalSxbllx/fbLzzsmxx1Y9Ee3EFScAgEJtc48TAEC7E04AAIWEEwBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhYQTAEAh4QQAUEg4AQAUaptwGhgYSF9fX/r7+6seBQBgkzqazWaz6iFertFopFarpV6vp6enp+pxAACGtM0VJwCAdiecAAAKCScAgELCCQCgkHACACgknAAACgknAIBCwgkAoJBwAgAoJJwAAAoJJwCAQsMSTk888UROPPHEjB07NmPGjMmBBx6Ye++9dziWAgDYZnZs9Qs+/fTTmT59eo444ojcdNNNGTduXH72s59ll112afVSAMBWevHF5P/+Lxk7tupJRpaWh9OCBQvS29ubK664YujYXnvt1eplAICt9PDDyfvel/ziF8kf/3Hyve8lPT1VTzUytPytuhtvvDHTpk3L8ccfn3HjxmXq1Km5/PLL/+DjBwcH02g0NtoAgOHzmc+sj6Ykueuu5F//tdp5RpKWh9Njjz2WSy+9NFOmTMn3vve9fPKTn8wZZ5yRr3/965t8/Pz581Or1Ya23t7eVo8EALzMc8+9+j5/WEez2Wy28gV32mmnTJs2LXfcccfQsTPOOCPLly/PnXfe+YrHDw4OZnBwcGi/0Wikt7c39Xo9Pa4bAkDLLVmSHHts8pvfJG9+c3L77cmee1Y91cjQ8nucdt999/T19W10bN9998211167ycd3dXWlq6ur1WMAAH/AkUcmK1cmP/tZcsABif9+q1zLw2n69Ol55JFHNjq2cuXK7CllAaBt7LHH+o0t0/J7nD796U/nrrvuyrx58/Loo49m8eLFWbRoUWbOnNnqpQAAtqmW3+OUJN/5zndy1lln5ac//WkmT56cOXPm5OMf/3jRcxuNRmq1mnucAIC2Myzh9FoIJwCgXfmuOgCAQsIJAKCQcAIAKCScAAAKCScAgELCCQCgkHACACgknAAACgknAIBCwgkAoFDbhNPAwED6+vrS399f9SgAAJvku+oAAAq1zRUnAIB2J5wAAAoJJwCAQsIJAKCQcAIAKCScAAAKCScAgELCCQCgkHACACgknAAACgknAIBCwgkAoJBwAoDXobVrk+XLk2eeqXqSkUU4AcDrzLJlyVvekrzrXck73pE88UTVE40cwgkAXmc+//kNV5p+/vNkYKDScUaUtgmngYGB9PX1pb+/v+pRAGC79oY3bLy/007VzDESdTSbzWbVQ7xco9FIrVZLvV5PT09P1eMAwHZnxYrkz/88+dWvkgMPTG65Jdl116qnGhl2rHoAAGDbOvDA5PHHkyefTHbfPensrHqikUM4AcDrUFdXssceVU8x8rTNPU4AAO1OOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhYQTAEAh4QQAUEg4AQAUEk4AAIWEEwBAIeEEAFCobcJpYGAgfX196e/vr3oUAIBN6mg2m82qh3i5RqORWq2Wer2enp6eqscBABjSNlecAADanXACACgknAAACgknAIBCwgkAoJBwAgAoJJwAAAoJJwCAQsIJAKCQcAIAKDTs4TR//vx0dHRk9uzZw70UAMCwGtZwWr58eRYtWpR3vvOdw7kMAMA2MWzh9Mwzz+TDH/5wLr/88rzxjW8crmUAoOV++9vkuuuS//iPpNmsehraybCF08yZM3PMMcfkve9973AtAQAt9/zzyZ/+afKBDyTvf3/ysY9VPRHtZMfheNFvfvObue+++7J8+fLNPnZwcDCDg4ND+41GYzhGAoAid92V3Hnnhv0rrkguvjjp6aluJtpHy684rV69OrNmzcpVV12VUaNGbfbx8+fPT61WG9p6e3tbPRIAFBs7duP9nXdORo+uZhbaT0ez2dp3b2+44Yb85V/+ZTo7O4eOvfjii+no6MgOO+yQwcHBjX62qStOvb29qdfr6ZH3AFTgS19Kzj03GTMm+cpXkhkzqp6IdtHycFq3bl0ef/zxjY6dfPLJ2WeffTJ37tzsv//+r/r8RqORWq0mnACAttPye5y6u7tfEUc777xzxo4du9loAgBoZz45HACgUMvfqnutvFUHALQrV5wAAAoJJwCAQsIJAKCQcAIAKCScAAAKCScAgELCCQCgkHACACgknAAACgknAIBCwgkAoFDbhNPAwED6+vrS399f9SgAAJvkS34BAAq1zRUnAIB2J5wAAAoJJwCAQsIJAKCQcAIAKCScAAAKCScAgELCCQCgkHACACgknAAACgknAIBCwgkAoJBwAgAoJJwAAAoJJwCAQm0TTgMDA+nr60t/f3/VowAAbFJHs9lsVj3EyzUajdRqtdTr9fT09FQ9DgDAkLa54gQA0O6EEwBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhYQTAEAh4QQAUEg4AQAUEk4AAIWEEwBAIeEEAFCobcJpYGAgfX196e/vr3oUAIBN6mg2m82qh3i5RqORWq2Wer2enp6eqscBABjSNlecAADanXACACgknAAACgknAIBCwgkAoJBwAgAoJJwAAAoJJwCAQsIJAKCQcAIAKNTycJo/f376+/vT3d2dcePG5bjjjssjjzzS6mUAALa5lofT0qVLM3PmzNx1111ZsmRJXnjhhRx11FF59tlnW70UAMA2Nexf8vvkk09m3LhxWbp0aQ499NDNPn64v+T3619Pli5N3v3u5BOfaPnLw2u2alXypS8lO+yQfPazyR57VD0RW+rRR5N/+Zdkp52SuXOTCROqngholR2He4F6vZ4k2XXXXYd7qc362teSk09e/+evfjX5zW+SWbMqHQk28uyzyWGHJatXr9+/6abkoYfW/wXMyFCvJ4cemvzyl+v3b745eeCBpLOz2rmA1hjWm8ObzWbmzJmTQw45JPvvv/8mHzM4OJhGo7HRNly+//2N92+9ddiWgq3y6KMbomlT+7S/H/94QzQlycMPJ7/6VXXzAK01rOF02mmn5YEHHsjVV1/9Bx8zf/781Gq1oa23t3fY5pk27dX3oWp77ZXsttuG/YkT12+MHG99a7LLLhv2J01K3vSm6uYBWmvY7nE6/fTTc8MNN2TZsmWZPHnyH3zc4OBgBgcHh/YbjUZ6e3uH5R6nZjO58MJk2bLkXe9KzjnH5XPaz4oVyRe+sP4ep/POS/r6qp6ILXXPPcm8eevfYv3Hf0ymTKl6IqBVWh5OzWYzp59+eq6//vr84Ac/yJQt/CfGcN8cDgCwtVp+c/jMmTOzePHifOtb30p3d3fWrFmTJKnVahk9enSrlwMA2GZafsWpo6Njk8evuOKKfPSjH93s811xAgDaVcuvOA3zx0IBAFTGd9UBABQSTgAAhYQTAEAh4QQAUEg4AQAUEk4AAIWEEwBAIeEEAFBIOAEAFBJOAACF2iacBgYG0tfXl/7+/qpHAQDYpJZ/ye9r5Ut+AYB21TZXnAAA2p1wAgAoJJwAAAoJJwCAQsIJAKCQcAIAKCScAAAKCScAgELCCQCgkHACACgknAAACgknAIBCwgkAoJBw2s7cd19yzDHJ0Ucny5dXPQ0AbF92rHoAWueZZ5L3vS/53/9dv/+f/5k89lhSq1U7FwBsL9rmitPAwED6+vrS399f9Sgj1v/8z4ZoSpJf/zr5xS+qmwcAtjcdzWazWfUQL9doNFKr1VKv19PT01P1OCPK4GBywAHJI4+s33/rW5MHH0xGjap2LgDYXnirbjvS1ZX84AfJxRcnzWYye7ZoAoBWcsUJAKBQ29zjBADQ7oQTAEAh4QQAUEg4AQAUEk4AAIWEEwBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABQSTgAAhdomnAYGBtLX15f+/v6qRwEA2KSOZrPZrHqIl2s0GqnVaqnX6+np6al6HACAIW1zxQkAoN0JJwCAQsIJAKCQcAIAKCScAAAKCScAgELCCQCgkHACACgknAAACgknAIBCwgkAoNCwhdMll1ySyZMnZ9SoUTnooIPywx/+cLiWAgDYJoYlnK655prMnj07Z599du6///685z3vyfvf//7893//93AsBwCwTQxLOF100UX52Mc+lr/927/Nvvvum4svvji9vb259NJLh2M5YARpNJIPfCCZNCn5yEeS3/626onYUr/+dXLssevP4cc+ljz/fNUTwSv9278lb3lLMnVqcvfdrXvdHVv3Uus9//zzuffee3PmmWdudPyoo47KHXfc8YrHDw4OZnBwcGi/0Whs1brNZjPr1q3bqucC285nPpNcd936P3/jG8keeyS/948L2tzs2cmNN67/81e/muy55/pj0C4efjj5+Mc37M+Ykfz0p5t/Xnd3dzo6Ol79Qc0We+KJJ5pJmrfffvtGxy+44ILm2972tlc8/txzz20mecVWr9e3aN16vb7J17HZbDabzWYr2Urao+VXnH7n94ut2WxusuLOOuuszJkzZ2i/0Wikt7d3i9fr7u5OvV4vfnx/f3+WL1++xetsrW253u9+h6tXr05PT882WXN7/n1Wseb2fA6vuy45+eQk6U9n5/Jce21yxBHDvmwS57BVFi9O/u7vkqQ/O+64PN/+dnLwwcO+bBLncKSvt63WbDSSQw9NVq1qJOnNMceszuLFmz+H3d3dm31My8Npt912S2dnZ9asWbPR8bVr12b8+PGveHxXV1e6urpe87odHR1b9D/szs7ObfZ/hCrWS5Kenp5ttubr4ffpHLbGRz+6/r6D44/vzHe+05Np04Z9ySHOYWt88pPJ29+enHBCZ266qSdTpw77kkOcw5G93rZas6dn/X1NX/va+tsDvv711p3Dlt8cvtNOO+Wggw7KkiVLNjq+ZMmSHLyt/pWkwMyZM7fr9ba118Pv0zlsnfe8J/nc52Zu02hKnMNWOuKI9edwW0ZT4hyO9PW25Zq77ZZ84hPr/7xjCy8TdTSbzWbrXm69a665Jn/zN3+Tyy67LH/yJ3+SRYsW5fLLL89DDz2UPffc81Wf22g0UqvVUq/Xt3kFby/8Dkc+53Dkcw5HPudw5BuOczgs9zj99V//dZ566qmcf/75+eUvf5n9998/3/3udzcbTbRGV1dXzj333Ja8BUo1nMORzzkc+ZzDkW84zuGwXHF6LRQ+ANCufFcdAEChtrvi1Pz/H2RZ9CFUAADbUNuFEwBAu/JWHQBAIeG0HZk/f376+/vT3d2dcePG5bjjjssjjzxS9Vhspfnz56ejoyOzfQnYiPPEE0/kxBNPzNixYzNmzJgceOCBuffee6seiwIvvPBCzjnnnEyePDmjR4/O3nvvnfPPPz8vvfRS1aPxKpYtW5YZM2Zk4sSJ6ejoyA033LDRz5vNZs4777xMnDgxo0ePzuGHH56HHnpoq9YSTtuRpUuXZubMmbnrrruyZMmSvPDCCznqqKPy7LPPVj0aW2j58uVZtGhR3vnOd1Y9Clvo6aefzvTp0/OGN7whN910Ux5++OF86Utfyi677FL1aBRYsGBBLrvssixcuDA//vGPc+GFF+aLX/xivvzlL1c9Gq/i2WefzQEHHJCFCxdu8ucXXnhhLrrooixcuDDLly/PhAkTcuSRR2bdunVbvJZ7nLZjTz75ZMaNG5elS5fm0EMPrXocCj3zzDP5oz/6o1xyySX5whe+kAMPPDAXX3xx1WNR6Mwzz8ztt9+eH/7wh1WPwlb4i7/4i4wfPz5f+cpXho594AMfyJgxY/KNb3yjwsko1dHRkeuvvz7HHXdckvVXmyZOnJjZs2dn7ty5SZLBwcGMHz8+CxYsyKmnnrpFr++K03bsd196vOuuu1Y8CVti5syZOeaYY/Le97636lHYCjfeeGOmTZuW448/PuPGjcvUqVNz+eWXVz0WhQ455JDccsstWblyZZLkRz/6UW677bYcffTRFU/G1lq1alXWrFmTo446auhYV1dXDjvssNxxxx1b/HrD8snhVK/ZbGbOnDk55JBDsv/++1c9DoW++c1v5r777tvm31ZO6zz22GO59NJLM2fOnPz93/997r777pxxxhnp6urKRz7ykarHYzPmzp2ber2effbZJ52dnXnxxRdzwQUX5IQTTqh6NLbSmjVrkiTjx4/f6Pj48ePz+OOPb/HrCaft1GmnnZYHHnggt912W9WjUGj16tWZNWtWbr755owaNarqcdhKL730UqZNm5Z58+YlSaZOnZqHHnool156qXAaAa655ppcddVVWbx4cfbbb7+sWLEis2fPzsSJE3PSSSdVPR6vwe9/NmSz2dyqz4sUTtuh008/PTfeeGOWLVuWPfbYo+pxKHTvvfdm7dq1Oeigg4aOvfjii1m2bFkWLlyYwcHBdHZ2VjghJXbffff09fVtdGzffffNtddeW9FEbInPfOYzOfPMM/PBD34wSfKOd7wjjz/+eObPny+cRqgJEyYkWX/laffddx86vnbt2ldchSrhHqftSLPZzGmnnZbrrrsu3//+9zN58uSqR2IL/Nmf/VkefPDBrFixYmibNm1aPvzhD2fFihWiaYSYPn36Kz4GZOXKlb7kfIR47rnnssMOG//V2NnZ6eMIRrDJkydnwoQJWbJkydCx559/PkuXLs3BBx+8xa/nitN2ZObMmVm8eHG+9a1vpbu7e+h93VqtltGjR1c8HZvT3d39ivvRdt5554wdO9Z9aiPIpz/96Rx88MGZN29e/uqv/ip33313Fi1alEWLFlU9GgVmzJiRCy64IJMmTcp+++2X+++/PxdddFFOOeWUqkfjVTzzzDN59NFHh/ZXrVqVFStWZNddd82kSZMye/bszJs3L1OmTMmUKVMyb968jBkzJh/60Ie2fLEm240km9yuuOKKqkdjKx122GHNWbNmVT0GW+jb3/52c//99292dXU199lnn+aiRYuqHolCjUajOWvWrOakSZOao0aNau69997Ns88+uzk4OFj1aLyKW2+9dZN//5100knNZrPZfOmll5rnnntuc8KECc2urq7moYce2nzwwQe3ai2f4wQAUMg9TgAAhYQTAEAh4QQAUEg4AQAUEk4AAIWEEwBAIeEEAFBIOAEAFBJOAACFhBMAQCHhBABQSDgBABT6f980Ygbj28PHAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "Graphics object consisting of 1 graphics primitive"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "private-tender",
   "metadata": {},
   "source": [
    "$$P = (4, 2) \\in E_0$$ </br>\n",
    "$$ord(P) = 8$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "typical-cassette",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = E(4,2)\n",
    "P.order()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "invalid-forest",
   "metadata": {},
   "source": [
    "$$G = \\{P, ..., \\mathcal{O}\\}$$\n",
    "$$\\ \\vert G \\vert = ord(P) = 8$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "mysterious-allergy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(4 : 2 : 1),\n",
       " (8 : 4 : 1),\n",
       " (2 : 10 : 1),\n",
       " (10 : 0 : 1),\n",
       " (2 : 1 : 1),\n",
       " (8 : 7 : 1),\n",
       " (4 : 9 : 1),\n",
       " (0 : 1 : 0)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kernel = []\n",
    "\n",
    "for i in range(1, 9):\n",
    "    kernel.append(P*i)\n",
    "    \n",
    "kernel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "grave-clark",
   "metadata": {},
   "source": [
    "$$\\phi: E_0 \\rightarrow E_1 $$\n",
    "$$kernel(\\phi) = G$$\n",
    "$$\\vert kernel(\\phi) \\vert = \\vert G \\vert = ord(P) = deg(\\phi)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "failing-thanksgiving",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Isogeny of degree 8 from Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 11 to Elliptic Curve defined by y^2 = x^3 + 5*x + 7 over Finite Field of size 11"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phi = E.isogeny(kernel)\n",
    "phi"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "academic-winner",
   "metadata": {},
   "source": [
    "$$\\phi(x, y) = ( \\frac{(x^8 - 5x^7 + 2x^6 - 5x^5 + 5x^3 - 5x^2 + 4x + 4)}{(x^7 - 5x^6 + 5x^5 - 2x^4 - 2x^3 + 4x^2 - 3x + 4)}\\ ,\\ \\frac{(x^{11}y + 4x^{10}y + 5x^9y + 5x^8y - 4x^7y - 2x^6y - 2x^5y + 4x^4y - 4x^2y + xy + 3y)}{(x^{11} + 4x^{10} + 2x^9 + x^8 + x^7 - 5x^6 - 3x^5 + 3x^4 - 5x^3 + 2x^2 - 5x - 3)} )$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "thorough-lecture",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((x^8 - 5*x^7 + 2*x^6 - 5*x^5 + 5*x^3 - 5*x^2 + 4*x + 4)/(x^7 - 5*x^6 + 5*x^5 - 2*x^4 - 2*x^3 + 4*x^2 - 3*x + 4),\n",
       " (x^11*y + 4*x^10*y + 5*x^9*y + 5*x^8*y - 4*x^7*y - 2*x^6*y - 2*x^5*y + 4*x^4*y - 4*x^2*y + x*y + 3*y)/(x^11 + 4*x^10 + 2*x^9 + x^8 + x^7 - 5*x^6 - 3*x^5 + 3*x^4 - 5*x^3 + 2*x^2 - 5*x - 3))"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phi.rational_maps()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fluid-calendar",
   "metadata": {},
   "source": [
    "$$\\phi(G) = \\phi(kernel(\\phi))= \\mathcal{O}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "clean-design",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0 : 1 : 0)\n",
      "(0 : 1 : 0)\n",
      "(0 : 1 : 0)\n",
      "(0 : 1 : 0)\n",
      "(0 : 1 : 0)\n",
      "(0 : 1 : 0)\n",
      "(0 : 1 : 0)\n",
      "(0 : 1 : 0)\n"
     ]
    }
   ],
   "source": [
    "for p in kernel:\n",
    "    print(phi(p))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "amber-accuracy",
   "metadata": {},
   "source": [
    "$$E_1: y^2 = x^3 + 5x + 7$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "electronic-support",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Elliptic Curve defined by y^2 = x^3 + 5*x + 7 over Finite Field of size 11"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_1 = phi.codomain()\n",
    "E_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "dying-yugoslavia",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk4AAAGFCAYAAAALnnwfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAgAElEQVR4nO3dfXQU9aH/8c8SSAg0uwo2CalJCBCBBUGExcNDBQtyLnI5oJb6REWofTgNkpijRcQWtJCAtRx7mxUM9VKUi3B7EKSeUkhrDXKQGoQoUuWhcCnlNqZW2A0gyyWZ3x/7I5CSyjcwO7PJvl/n7CEz7Mz3Mw6YT74z7Hgsy7IEAACAy2rndgAAAIDWguIEAABgiOIEAABgiOIEAABgiOIEAABgiOIEAABgiOIEAABgiOIEAABgKO6Kk2VZCofD4nM5AQBAvIm74lRXVyefz6e6ujq3owAAADQRd8UJAAAgXrW4OG3dulUTJ05UVlaWPB6PNmzY0OT3LcvS/PnzlZWVpdTUVI0ePVp79+61LTAAAIBbWlycTp06pYEDB6qsrKzZ33/22We1ZMkSlZWVqaqqSpmZmbr99tu59AYAAFo9j3UVd2F7PB6tX79ekydPlhSdbcrKylJRUZFmz54tSYpEIsrIyNDixYv13e9+97L7DIfD8vl8CoVC8nq9VxoNAAAksMOHpZdekrxeaeZMqVMne/bb3p7dRB0+fFg1NTUaN25c47qUlBSNGjVK27dvNypOAAAAV+PTT6Xhw6WamuhyRUX0ZQdbi1PN/0+YkZHRZH1GRoaOHDnS7DaRSESRSKRxORwO2xkJAAAkmKqqC6VJkn73O+nMGaljx6vfd0z+VZ3H42mybFnWJevOKy0tlc/na3xlZ2fHIhIAAEgQvXpJHTpcWM7Ls6c0STYXp8zMTEkXZp7Oq62tvWQW6rw5c+YoFAo1vo4ePWpnJAAAkGDy86Vf/Sp6ue7f/k36zW/s27etl+ry8vKUmZmpiooKDRo0SJJ09uxZVVZWavHixc1uk5KSopSUFDtjAACABDdpUvRltxYXp5MnT+rgwYONy4cPH1Z1dbW6dOminJwcFRUVqaSkRPn5+crPz1dJSYk6deqk+++/39bgAAAATmtxcdq5c6duu+22xuXi4mJJ0rRp0/TLX/5SP/jBD/T555/r+9//vo4fP65bbrlFW7ZsUVpamn2pAQAAXHBVn+MUC3yOEwAAiFc8qw4AAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMBQ3BSnYDAov9+vQCDgdhQAAIBm8ZBfAAAAQ3Ez4wQAABDvKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACGKE4AAACG4qY4BYNB+f1+BQIBt6MAAAA0y2NZluV2iIuFw2H5fD6FQiF5vV634wAAADSKmxknAACAeEdxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMBQ3xSkYDMrv9ysQCLgdBQAAoFkey7Ist0NcLBwOy+fzKRQKyev1uh0HAACgUdzMOAEAAMQ7ihMAAIAhihMAAIAhihMAAIAhihMAAIAhihMAAIAhihMAAIAhihMAAIAhihMAAIAhihMAAIAhihMAAIAh24vTuXPn9NRTTykvL0+pqanq0aOHnnnmGTU0NNg9FAAAgKPa273DxYsXa9myZVq5cqX69eunnTt3avr06fL5fCosLLR7OAAAAMfYPuP0zjvvaNKkSZowYYK6d++ur3/96xo3bpx27txp91AAAHyh//xPKRCQ/v3fpf/5H7fToC2wfcZp5MiRWrZsmfbv368bbrhB77//vrZt26bnn3++2fdHIhFFIpHG5XA4bHckAEAC2rFDevhhybKiy7W10rvvupsJrZ/txWn27NkKhULq06ePkpKSVF9fr4ULF+q+++5r9v2lpaV6+umn7Y4BAEhw+/ZdKE2S9PHH7mVB22H7pbq1a9dq1apVWr16tXbt2qWVK1fqueee08qVK5t9/5w5cxQKhRpfR48etTsSACABjR4t+XwXlidPdi0K2hCPZV3cx69edna2nnjiCRUUFDSuW7BggVatWqWPDep+OByWz+dTKBSS1+u1MxoAIMF8/LG0erWUmSl95ztSe9uvsyDR2P5H6PTp02rXrulEVlJSEh9HAABwXJ8+0jPPuJ0CbYntxWnixIlauHChcnJy1K9fP+3evVtLlizRjBkz7B4KAADAUbZfqqurq9MPf/hDrV+/XrW1tcrKytJ9992nH/3oR0pOTr7s9lyqAwAA8cr24nS1KE4AACBe8aw6AAAAQxQnAAAAQxQnAAAAQxQnAAAAQxQnAAAAQxQnAAAAQxQnAAAAQxQnAAAAQxQnAAAAQxQnAAAAQ3FTnILBoPx+vwKBgNtRAAAAmsWz6gAAAAzFzYwTAABAvKM4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4AQAAGKI4JZDf/EbKyZHS06XycrfTAADQ+ngsy7LcDnGxcDgsn8+nUCgkr9frdpw248wZ6brrpFOnosvt2kn790s9e7qbCwCA1iRuZpyCwaD8fr8CgYDbUdqkkycvlCZJamiQ/v539/IAANAaMeOUQL7+dWnduujXQ4dKW7dKKSnuZgIAoDVp73YAOGftWmnDhuhluzvvpDQBANBSFKcEkpQk3X232ykAAGi94uYeJwAAgHhHcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADAUN8UpGAzK7/crEAi4HQUAAKBZHsuyLLdDXCwcDsvn8ykUCsnr9bodBwAAoFHczDgBAADEO4oTAACAIYoTAACAIYoTAACAIYoTAACAIYoTAACAIYoTAACAIYoTAACAIYoTAACAIYoTAACAIYoTAACAoZgUp2PHjmnq1Knq2rWrOnXqpJtuuknvvfdeLIYCAABwTHu7d3j8+HGNGDFCt912mzZt2qT09HT9+c9/1jXXXGP3UFfEsqTPPpO6dJE8HrfTwGn/+Id0zTVSUpLbSZwXiUhnzkg+n9tJAKD1sn3GafHixcrOztaKFSs0dOhQde/eXWPGjFHPnj3tHqrFPvlEGjBAuu46qXdv6cgRtxPBKeGwNHx49Nzn5kp797qdyFnr1knXXhstjd/5jttpAKD1sr04bdy4UUOGDNGUKVOUnp6uQYMGafny5f/y/ZFIROFwuMkrVhYulD78MPr1gQPSvHkxGwpx5j/+Q3rnnejXx45Jjz3mbh6nfetb0uefR79evlx680138wBAa2V7cTp06JCWLl2q/Px8bd68Wd/73vc0a9Ysvfzyy82+v7S0VD6fr/GVnZ1td6RGp09/8TLarkQ+9w0N0Ut0F0uk4wcAO3ksy7Ls3GFycrKGDBmi7du3N66bNWuWqqqq9M75H/kvEolEFIlEGpfD4bCys7MVCoXk9XrtjKYPP5RGj47e5+LzSVu2SEOH2joE4tRf/hK9VHfsmJSaKm3YII0b53Yq5yxaJM2ZE/361luligopOdndTADQGtl+c3i3bt3k9/ubrOvbt6/WrVvX7PtTUlKUkpJid4xm9e8vffxx9P6W3r2lzExHhkUcyMmJFuf335d69JBiOLEZl554Qpo4UTpxIvrDQocObicCgNbJ9uI0YsQI7du3r8m6/fv3Kzc31+6hrsh110mjRrmdAm645prEPvf9+rmdAABaP9vvcXr00Ue1Y8cOlZSU6ODBg1q9erXKy8tVUFBg91AAAACOsv0eJ0l64403NGfOHB04cEB5eXkqLi7Wt7/9baNtw+GwfD5fTO5xAgAAuBoxKU5Xg+IEAADiFc+qAwAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMBQ3xSkYDMrv9ysQCLgdBQAAoFk8qw4AAMBQ3Mw4AQAAxDuKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgCGKEwAAgKGEK06hkFRVJX32mdtJ4LSTJ6PnvrbW7STuOHRI2r1bqq93OwkAtF4JVZz27ZP69JGGDpXy86XqarcTwSn/+7/SgAHRc9+zp1RZ6XYiZ/3sZ1KvXtLNN0t33CGdO+d2IgBonRKqOP30p1JNTfTrzz6TSkvdzQPnvPCCdPhw9OuTJ6X5812N4yjLkp54IvqrJG3ZEn0BAFoubopTMBiU3+9XIBCI2RgdOjRdTk6O2VCIM4l+7tu3b7qcaMcPAHbxWNb5n0PjQzgcls/nUygUktfrtXXff/2rNGaMtH+/lJsr/f730cs2aPuOH4+e+927pYwMadMmadAgt1M557/+S5oxQzp7Vpo6VXr5ZcnjcTsVALQ+CVWcpOi9HTU10W+e/zwLgbatvl7629+kL39ZSklxO43zwmHp9GkpM9PtJADQeiVccQIAALhScXOPEwAAQLyjOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiiOAEAABiKm+IUDAbl9/sVCATcjgIAANAsj2VZltshLhYOh+Xz+RQKheT1et2OAwAA0ChuZpwAAADiHcUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAUMyLU2lpqTwej4qKimI9FAAAQEzFtDhVVVWpvLxcAwYMiOUwAAAAjohZcTp58qQeeOABLV++XNdee22shkELWJa0aZO0fr0UibidBgCA1idmxamgoEATJkzQ2LFjYzUEWujBB6U77pDuuksaO1b6v/9zOxEAAK1L+1jsdM2aNdq1a5eqqqou+95IJKLIRdMf4XA4FpES3qefSqtWXVjetk3atUu65Rb3MgEA0NrYPuN09OhRFRYWatWqVerYseNl319aWiqfz9f4ys7OtjsSJHXuLKWmXlj2eKQuXdzLAwBAa+SxLMuyc4cbNmzQnXfeqaSkpMZ19fX18ng8ateunSKRSJPfa27GKTs7W6FQSF6v185oCW/9eunb347e37RwoTRrltuJAABoXWwvTnV1dTpy5EiTddOnT1efPn00e/Zs9e/f/wu3D4fD8vl8FCcAABB3bL/HKS0t7ZJy1LlzZ3Xt2vWypQkAACCe8cnhAAAAhmy/VHe1uFQHAADiFTNOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhuKmOAWDQfn9fgUCAbejAAAANIuH/AIAABiKmxknAACAeEdxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMERxAgAAMNTe7QAAAMTKoUPSf/+3lJEhTZsmtWO6AFeJ4gQAaJP++ldp6FDpH/+ILm/fLi1f7m4mtH50bwBAm/TmmxdKkxSdeQKuVtwUp2AwKL/fr0Ag4HYUAEAb0KNH0+WePd3JgbbFY1mW5XaIi4XDYfl8PoVCIXm9XrfjAABasbIyaenS6D1O5eVSr15uJ0JrR3ECAAAwFDeX6gAAAOIdxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMAQxQkAAMBQ3BSnYDAov9+vQCDgdhQAAIBmeSzLstwOcbFwOCyfz6dQKCSv1+t2HAAAgEZxM+MEAAAQ7yhOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhmwvTqWlpQoEAkpLS1N6eromT56sffv22T0MAACA42wvTpWVlSooKNCOHTtUUVGhc+fOady4cTp16pTdQwEAADgq5g/5/fvf/6709HRVVlbq1ltvvez7ecgvAACIVzG/xykUCkmSunTpEuuhAAAAYiqmM06WZWnSpEk6fvy43n777WbfE4lEFIlEGpfD4bCys7OZcQIAAHEnpjNOM2fO1AcffKBXX331X76ntLRUPp+v8ZWdnR3LSAAAAFcsZjNOjzzyiDZs2KCtW7cqLy/vX76PGScAANBatLd7h5Zl6ZFHHtH69ev11ltvfWFpkqSUlBSlpKTYHQMAAMB2thengoICrV69Wq+//rrS0tJUU1MjSfL5fEpNTbV7OAAAAMfYfqnO4/E0u37FihV66KGHLrs9H0cAAADiVUwu1QEAALRFPKsOAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAEMUJAADAUNwUp2AwKL/fr0Ag4HYUAACAZtn+kN+rxUN+AQBAvIqbGScAAIB4R3ECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAAAwRHECAABtzubN0u23S3ffLf35z/btt719uwIAAHDfoUPSpElSJBJd/vBDad8+e/YdNzNOwWBQfr9fgUDA7SgAAKAV27fvQmmSpP37pTNn7Nm3x7Isy55d2SMcDsvn8ykUCsnr9bodBwAAtDKffCL17y99+ml0+dZbpcpKe/bNpToAANCmZGRI27ZJL74oeb1ScbF9+2bGCQAAwFDc3OMEAAAQ7yhOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhihOAAAAhuKmOAWDQfn9fgUCAbejAAAANMtjWZbldoiLhcNh+Xw+hUIheb1et+MAAAA0ipsZJwAAgHhHcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADBEcQIAADAUs+L0wgsvKC8vTx07dtTgwYP19ttvx2ooAAAAR8SkOK1du1ZFRUWaO3eudu/era9+9asaP368/vKXv8RiOAAAAEfEpDgtWbJE3/rWt/Twww+rb9++ev7555Wdna2lS5fGYjgA+EJz5ki5udLo0dKRI26ncdb+/dKIEVL37tKCBW6ngZOOHZPGjo3+2X/sMcmy3E7UNngsy97/lGfPnlWnTp30q1/9SnfeeWfj+sLCQlVXV6uysrLJ+yORiCKRSONyOBxWdna2QqGQvF6v8biWZamuru7qDwBAm/Laa9L06ReWR42SNm50L4/TRo+Wdu++sLxuXfSbKdq+KVOkLVsuLL/4onTvve7laQ3S0tLk8Xi+8D3t7R70008/VX19vTIyMpqsz8jIUE1NzSXvLy0t1dNPP33V49bV1cnn8131fgC0bZWVUiL/r+Luu91OALd897vRF/41k0kb24vTef/c2CzLarbFzZkzR8XFxY3L52ecWiotLU2hUMjovefHOHr0qPGsViAQUFVVVYsyObFNS99/JcfuRC6ntuHcx/7cX8k2sRzj4MHorEtdXVhStoqLj2revNZ97luyzdy5UllZ9Nivvfaotm3z6vrr3c/l5Bht6e99S7Z5/nlp3rzoue/U6ajefNOrvn3dz+XkGC0992lpaZd9j+3F6brrrlNSUtIls0u1tbWXzEJJUkpKilJSUq56XI/H06JvBpLk9XqNt0lKSmrx/p3Y5krGkFp27E7lcmobiXMfb+cylmPcfLO0a1f0kt3s2dK8ea3/3Ldkm5//XBo6VHrwQWnrVq/8/vg4L06OcV5b+Hvfkm1+9CPJ749estu61avBg+PrvMTrub8c228OT05O1uDBg1VRUdFkfUVFhYYPH273cI4pKCiIy22uZIwr4UQup7ZxYoxEPvdXsk2sx+jVS/re91o8RNye+5ZuM2lS9NecnNiNcaXb8Pc+ttuMGxf9NT8/dmNc6Tbxeu4vx/abw6XoxxF885vf1LJlyzRs2DCVl5dr+fLl2rt3r3Jzc79w23A4LJ/P1+Kbw1vCiTHiVSIfu5TYx5/Ixy4l9vEn8rFLiX38iXzsUmyOP2n+/PnzbdnTRfr376+uXbuqpKREzz33nD7//HO98sorGjhw4GW3jUQiWrRokebMmWPLJbx/JSkpSaNHj1b79jG7zStuJfKxS4l9/Il87FJiH38iH7uU2MefyMcu2X/8MZlxuhqJ3o4BAED84ll1AAAAhuJuxun8B1mafAgVAACAk+KuOAEAAMQrLtUBAAAYSpjiVFpaqkAgoLS0NKWnp2vy5Mnat2+f27Ecs3TpUg0YMKDxQ8CGDRumTZs2uR3LFaWlpfJ4PCoqKnI7iiPmz58vj8fT5JWZmel2LMccO3ZMU6dOVdeuXdWpUyfddNNNeu+999yO5Yju3btfcu49Hk9cfBZOrJ07d05PPfWU8vLylJqaqh49euiZZ55RQ0OD29EcU1dXp6KiIuXm5io1NVXDhw9v8Sd1txZbt27VxIkTlZWVJY/How0bNjT5fcuyNH/+fGVlZSk1NVWjR4/W3r17r2ishClOlZWVKigo0I4dO1RRUaFz585p3LhxOnXqlNvRHHH99ddr0aJF2rlzp3bu3Kmvfe1rmjRp0hX/wWmtqqqqVF5ergEDBrgdxVH9+vXT3/72t8bXnj173I7kiOPHj2vEiBHq0KGDNm3apD/96U/66U9/qmuuucbtaI6oqqpqct7PfzDxlClTXE4We4sXL9ayZctUVlamjz76SM8++6x+8pOf6Oc//7nb0Rzz8MMPq6KiQq+88or27NmjcePGaezYsTp27Jjb0Wx36tQpDRw4UGVlZc3+/rPPPqslS5aorKxMVVVVyszM1O233666urqWD2YlqNraWkuSVVlZ6XYU11x77bXWL37xC7djOKaurs7Kz8+3KioqrFGjRlmFhYVuR3LEvHnzrIEDB7odwxWzZ8+2Ro4c6XaMuFFYWGj17NnTamhocDtKzE2YMMGaMWNGk3V33XWXNXXqVJcSOev06dNWUlKS9cYbbzRZP3DgQGvu3LkupXKGJGv9+vWNyw0NDVZmZqa1aNGixnVnzpyxfD6ftWzZshbvP2FmnP7Z+QcCd+nSxeUkzquvr9eaNWt06tQpDRs2zO04jikoKNCECRM0duxYt6M47sCBA8rKylJeXp7uvfdeHTp0yO1Ijti4caOGDBmiKVOmKD09XYMGDdLy5cvdjuWKs2fPatWqVZoxY0ZC/IvlkSNH6ve//732798vSXr//fe1bds23XHHHS4nc8a5c+dUX1+vjh07Nlmfmpqqbdu2uZTKHYcPH1ZNTY3GnX/+jKLPyR01apS2b9/e4v0l5MeIWpal4uJijRw5Uv3793c7jmP27NmjYcOG6cyZM/rSl76k9evXy+/3ux3LEWvWrNGuXbva7PX9L3LLLbfo5Zdf1g033KBPPvlECxYs0PDhw7V371517drV7XgxdejQIS1dulTFxcV68skn9e6772rWrFlKSUnRgw8+6HY8R23YsEEnTpzQQw895HYUR8yePVuhUEh9+vRRUlKS6uvrtXDhQt13331uR3NEWlqahg0bph//+Mfq27evMjIy9Oqrr+qPf/yj8lv64LpWrqamRpKUkZHRZH1GRoaOHDnS4v0lZHGaOXOmPvjgg4Rr3b1791Z1dbVOnDihdevWadq0aaqsrGzz5eno0aMqLCzUli1bLvnpKxGMHz++8esbb7xRw4YNU8+ePbVy5UoVFxe7mCz2GhoaNGTIEJWUlEiSBg0apL1792rp0qUJV5xeeukljR8/XllZWW5HccTatWu1atUqrV69Wv369VN1dbWKioqUlZWladOmuR3PEa+88opmzJihr3zlK0pKStLNN9+s+++/X7t27XI7miv+eabVsqwrmn1NuOL0yCOPaOPGjdq6dauuv/56t+M4Kjk5Wb169ZIkDRkyRFVVVfrZz36mF1980eVksfXee++ptrZWgwcPblxXX1+vrVu3qqysTJFIRElJSS4mdFbnzp1144036sCBA25Hiblu3bpd8oNB3759tW7dOpcSuePIkSP63e9+p9dee83tKI55/PHH9cQTT+jee++VFP2h4ciRIyotLU2Y4tSzZ09VVlbq1KlTCofD6tatm+655x7l5eW5Hc1R5/8VcU1Njbp169a4vra29pJZKBMJc4+TZVmaOXOmXnvtNb355psJ9wenOZZlKRKJuB0j5saMGaM9e/aourq68TVkyBA98MADqq6uTqjSJEUfpP3RRx81+R9IWzVixIhLPnZk//79ys3NdSmRO1asWKH09HRNmDDB7SiOOX36tNq1a/otLikpKaE+juC8zp07q1u3bjp+/Lg2b96sSZMmuR3JUXl5ecrMzGz8V6VS9J6/yspKDR8+vMX7S5gZp4KCAq1evVqvv/660tLSGq95+nw+paamupwu9p588kmNHz9e2dnZqqur05o1a/TWW2/pt7/9rdvRYi4tLe2Se9k6d+6srl27JsQ9bo899pgmTpyonJwc1dbWasGCBQqHwwnxU/ejjz6q4cOHq6SkRN/4xjf07rvvqry8XOXl5W5Hc0xDQ4NWrFihadOm2fZ0+NZg4sSJWrhwoXJyctSvXz/t3r1bS5Ys0YwZM9yO5pjNmzfLsiz17t1bBw8e1OOPP67evXtr+vTpbkez3cmTJ3Xw4MHG5cOHD6u6ulpdunRRTk6OioqKVFJSovz8fOXn56ukpESdOnXS/fff3/LBrvaf/bUWkpp9rVixwu1ojpgxY4aVm5trJScnW1/+8petMQa8ou0AAAEFSURBVGPGWFu2bHE7lmsS6eMI7rnnHqtbt25Whw4drKysLOuuu+6y9u7d63Ysx/z617+2+vfvb6WkpFh9+vSxysvL3Y7kqM2bN1uSrH379rkdxVHhcNgqLCy0cnJyrI4dO1o9evSw5s6da0UiEbejOWbt2rVWjx49rOTkZCszM9MqKCiwTpw44XasmPjDH/7Q7Pf4adOmWZYV/UiCefPmWZmZmVZKSop16623Wnv27LmisXhWHQAAgKGEuccJAADgalGcAAAADFGcAAAADFGcAAAADFGcAAAADFGcAAAADFGcAAAADFGcAAAADFGcAAAADFGcAAAADFGcAAAADFGcAAAADP0/CCy2UbEDumIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "Graphics object consisting of 1 graphics primitive"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_1.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "controlled-purpose",
   "metadata": {},
   "source": [
    "***\n",
    "$\\mathbf{\\text{Isogenie-Kern Beziehung}}$<br>\n",
    "***\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "protective-receiver",
   "metadata": {},
   "outputs": [],
   "source": [
    "F = GF(17)\n",
    "E_0 = EllipticCurve(F, [1, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "innovative-intranet",
   "metadata": {},
   "source": [
    "$\\mathbf{\\text{Jede n-Torsionsgruppe definiert eine Isogenie vom Grad n}}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "wound-injection",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(5 : 0 : 1)]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "torsion = 2\n",
    "torsion_group = [point for point in E_0.points() if point.order() == torsion]\n",
    "torsion_group"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "sustained-direction",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x + 6 over Finite Field of size 17 to Elliptic Curve defined by y^2 = x^3 + 12*x + 15 over Finite Field of size 17"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "phi = E_0.isogeny(torsion_group)\n",
    "phi"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "descending-sunrise",
   "metadata": {},
   "source": [
    "$\\mathbf{\\text{Jede Isogenie vom Grad n definiert eine n-Torsionsgruppe}}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "colored-confusion",
   "metadata": {},
   "outputs": [],
   "source": [
    "E_1 = phi.codomain()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "foreign-surveillance",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "From: (0 : 1 : 0) to (0 : 1 : 0)\n",
      "From: (1 : 5 : 1) to (16 : 11 : 1)\n",
      "From: (1 : 12 : 1) to (16 : 6 : 1)\n",
      "From: (2 : 4 : 1) to (5 : 8 : 1)\n",
      "From: (2 : 13 : 1) to (5 : 9 : 1)\n",
      "From: (3 : 6 : 1) to (16 : 11 : 1)\n",
      "From: (3 : 11 : 1) to (16 : 6 : 1)\n",
      "From: (5 : 0 : 1) to (0 : 1 : 0)\n",
      "From: (7 : 4 : 1) to (11 : 13 : 1)\n",
      "From: (7 : 13 : 1) to (11 : 4 : 1)\n",
      "From: (8 : 4 : 1) to (5 : 8 : 1)\n",
      "From: (8 : 13 : 1) to (5 : 9 : 1)\n",
      "From: (9 : 8 : 1) to (11 : 4 : 1)\n",
      "From: (9 : 9 : 1) to (11 : 13 : 1)\n",
      "From: (10 : 8 : 1) to (15 : 0 : 1)\n",
      "From: (10 : 9 : 1) to (15 : 0 : 1)\n",
      "From: (15 : 8 : 1) to (9 : 6 : 1)\n",
      "From: (15 : 9 : 1) to (9 : 11 : 1)\n",
      "From: (16 : 2 : 1) to (9 : 11 : 1)\n",
      "From: (16 : 15 : 1) to (9 : 6 : 1)\n"
     ]
    }
   ],
   "source": [
    "for p in E_0.points():\n",
    "    print(\"From: \" + str(p) + \" to \" +  str(phi(p)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "funny-share",
   "metadata": {},
   "source": [
    "***\n",
    "$\\mathbf{\\text{Supersinguläre elliptische Kurven}}$<br>\n",
    "***\n",
    "1.&emsp;Ordinäre elliptische Kurven: $$tors(p) = \\{P_1, ..., \\mathcal{O}\\}$$\n",
    "2.&emsp;Supersinguläre elliptische Kurven: $$tors(p) = \\{\\mathcal{O}\\}$$\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "canadian-certification",
   "metadata": {},
   "source": [
    "Wie in der Arbeit \"QrTOR - Modernes quantenresistentes Onion Routing\" erklärt, können für kryptographische Anwendungen ausschließlich supersinguläre elliptische Kurven verwendet werden. Diese haben die Eigenschaft einen ungewöhnlich großen Endomorphismusring zu besitzen, also ungewöhnlich viele gruppenstruktur-erhaltende Abbildungen auf sich selbst. \n",
    "Eine eingänglichere Weise der Definition bietet jedoch die obige Formel, wonach eine elliptische Kurve über dem Feld $GF(p)$ supersingulär ist, sofern ihre $p$-Torsionsgruppe trivial ist (also lediglich das Identitäselement enthält)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "thick-floating",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "char = 5\n",
    "E_ss = EllipticCurve(GF(char), [0,1])\n",
    "E_ss.is_supersingular()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "round-stone",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2 : 3 : 1)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gen = E_ss.gens()[0]\n",
    "gen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "practical-census",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "torsion = char\n",
    "torsion_group = [point for point in E_ss.points() if point.order() == torsion - 1]\n",
    "torsion_group"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "stainless-questionnaire",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_ord = EllipticCurve(GF(char), [4,1])\n",
    "E_ord.is_supersingular()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "generic-binary",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0 : 1 : 1)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gen_ord = E_ord.gens()[0]\n",
    "gen_ord"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "prerequisite-geometry",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(4 : 1 : 1), (4 : 4 : 1)]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "torsion_ord = char\n",
    "torsion_group_ord = [point for point in E_ord.points() if point.order() == torsion_ord - 1]\n",
    "torsion_group_ord"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "determined-blair",
   "metadata": {},
   "source": [
    "## Ein mathematischer Blick auf den SIDH"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "significant-tuning",
   "metadata": {},
   "source": [
    "Im Folgenden wird ein beispielhafter Schlüsselaustausch auf Basis von Isogenieberechnungen durchgeführt."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "streaming-filename",
   "metadata": {},
   "source": [
    "### Setzen der öffentlichen Parameter"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alternative-persian",
   "metadata": {},
   "source": [
    "#### Primcharacteristik"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "magnetic-province",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lA = 2 ** 8\n",
    "lB = 3 ** 5\n",
    "p = lA*lB - 1\n",
    "p.is_prime()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cross-ridge",
   "metadata": {},
   "source": [
    "#### Definitionsfeld"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "incident-moldova",
   "metadata": {},
   "outputs": [],
   "source": [
    "_.<I> = GF(p)[]\n",
    "K.<i> = GF(p^2, modulus=I^2+1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unnecessary-partition",
   "metadata": {},
   "source": [
    "#### Elliptische Kurve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "robust-incident",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E = EllipticCurve(K, [1, 0])\n",
    "E.is_supersingular()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "recognized-chicago",
   "metadata": {},
   "source": [
    "#### Torsions/Isogenie Generatoren"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "executed-composition",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(48314*i + 14762 : 46157*i + 12824 : 1) with Order 256\n",
      "(2043*i + 16611 : 44347*i + 58767 : 1) with Order 256\n",
      "(10750*i + 15084 : 21370*i + 13539 : 1) with Order 243\n",
      "(60522*i + 47624 : 56832*i + 45130 : 1) with Order 243\n"
     ]
    }
   ],
   "source": [
    "P_a = E(48314*i + 14762 , 46157*i + 12824 , 1)\n",
    "Q_a = E(2043*i + 16611 , 44347*i + 58767 , 1)\n",
    "P_b = E(10750*i + 15084 , 21370*i + 13539 , 1)\n",
    "Q_b = E(60522*i + 47624 , 56832*i + 45130 , 1)\n",
    "\n",
    "print(str(P_a) + \" with Order \" + str(P_a.order()))\n",
    "print(str(Q_a) + \" with Order \" + str(Q_a.order()))\n",
    "print(str(P_b) + \" with Order \" + str(P_b.order()))\n",
    "print(str(Q_b) + \" with Order \" + str(Q_b.order()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "vertical-belize",
   "metadata": {},
   "source": [
    "### Berechnung der geheimen und der öffentlichen Schlüssel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "advanced-welding",
   "metadata": {},
   "source": [
    "#### Alice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "impressive-venture",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(30140*i + 52660 : 48843*i + 60323 : 1)"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S_a = randint(0, 2^8-1)\n",
    "R = P_a + S_a * Q_a\n",
    "R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "balanced-anime",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Isogeny of degree 256 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2 to Elliptic Curve defined by y^2 = x^3 + (36605*i+31278)*x + (3952*i+1907) over Finite Field in i of size 62207^2\n"
     ]
    }
   ],
   "source": [
    "isogenyA = E.isogeny(R)\n",
    "print(isogenyA)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "optimum-brunswick",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Elliptic Curve defined by y^2 = x^3 + (36605*i+31278)*x + (3952*i+1907) over Finite Field in i of size 62207^2"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_a = isogenyA.codomain()\n",
    "\n",
    "print(E_a.is_supersingular())\n",
    "E_a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "cloudy-ultimate",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Elliptic Curve defined by y^2 = x^3 + (36605*i+31278)*x + (3952*i+1907) over Finite Field in i of size 62207^2,\n",
       " (60911*i + 51118 : 7766*i + 10434 : 1),\n",
       " (25099*i + 43799 : 45246*i + 30237 : 1))"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_a, phi_Pb, phi_Qb = E_a, isogenyA(P_b), isogenyA(Q_b)\n",
    "E_a, phi_Pb, phi_Qb"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "efficient-badge",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "choice-louisiana",
   "metadata": {},
   "source": [
    "#### Bob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "wanted-kingston",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(59196*i + 14747 : 28849*i + 52231 : 1)"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S_b = randint(0, 3^5-1)\n",
    "R = P_b + S_b * Q_b\n",
    "R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "electrical-rugby",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Isogeny of degree 243 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in i of size 62207^2 to Elliptic Curve defined by y^2 = x^3 + (49450*i+16753)*x + (43821*i+15786) over Finite Field in i of size 62207^2"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isogenyB = E.isogeny(R)\n",
    "isogenyB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "visible-diagram",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Elliptic Curve defined by y^2 = x^3 + (49450*i+16753)*x + (43821*i+15786) over Finite Field in i of size 62207^2"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_b = isogenyB.codomain()\n",
    "\n",
    "print(E_b.is_supersingular())\n",
    "E_b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "processed-finance",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Elliptic Curve defined by y^2 = x^3 + (49450*i+16753)*x + (43821*i+15786) over Finite Field in i of size 62207^2,\n",
       " (44905*i + 14667 : 22763*i + 44548 : 1),\n",
       " (2718*i + 32258 : 54815*i + 30726 : 1))"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_b, psi_Pa, psi_Qa = E_b, isogenyB(P_a), isogenyB(Q_a)\n",
    "E_b, psi_Pa, psi_Qa"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "polar-nevada",
   "metadata": {},
   "source": [
    "### Berechnung des gemeinsamen Geheimnis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "equipped-italy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4285*i + 17425"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_b.isogeny(psi_Pa + S_a*psi_Qa).codomain().j_invariant()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exempt-pickup",
   "metadata": {},
   "source": [
    "****"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "ranging-conservation",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4285*i + 17425"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E_a.isogeny(phi_Pb + S_b*phi_Qb).codomain().j_invariant()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "copyrighted-endorsement",
   "metadata": {},
   "source": [
    "## Das Problem hinter dem SIDH"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "animated-florist",
   "metadata": {},
   "source": [
    "Finde einen Algorithmus, der folgendes Problem in subexponentieller Zeit löst\n",
    "$$algorithm(E_0, E_1, deg(\\phi)) = \\phi;\\ \\phi : E_0 \\rightarrow E_1$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "straight-printing",
   "metadata": {},
   "outputs": [],
   "source": [
    "E_0 = EllipticCurve([6,7])\n",
    "E_1 = EllipticCurve([-39,70])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "narrow-release",
   "metadata": {},
   "outputs": [],
   "source": [
    "E_1 = EllipticCurve([-39,70])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "editorial-cowboy",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x + 7 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 39*x + 70 over Rational Field"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EllipticCurveIsogeny(E_0, kernel = None, codomain = E_1, degree = 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "choice-positive",
   "metadata": {},
   "source": [
    "Der schnellste (öffentlich bekannte) Algorithmus zur Berechnung einer Isogenie, bei gegebener Ur- und Bildkurve, benötigt\n",
    "1. auf einem klassischen Computer: $$O(p^{\\frac{1}{4}})$$\n",
    "2. auf einem Quantencomputer: $$O(p^{\\frac{1}{6}})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "understood-throat",
   "metadata": {},
   "source": [
    "## Ein Kompositionsalgorithmus zur effizienten Berechnung von Isogenien"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "separated-slide",
   "metadata": {},
   "source": [
    "Ein großes Problem für isogeniebasierte Kryptosysteme geht von der hohen Komplexität der Berechnungen von Isogenien aus. Wie oben besprochen, wird eine Isogenie stets aus der Urbild-Kurve und aus dem Kern der zu berechnenden Isogenie konstruiert. Die Anzahl der Elemente innerhalb des Kerns ist dabei gleich dem Grad der Isogenie. \n",
    "Für kryptographische Anwendungen werden Isogenien mit sehr hohen Graden benötigt [3], um Kryptoanalysealgorithmen standzuhalten. Im Notebook \"SIDHforJ\" werden zum Beispiel Isogenien vom Grad $2^{250}$ verwendet. Um eine solche Isogenie zu berechnen benötigt man also die Urbildkurve $E_0$ und die $2^{250}$-Torsionsgruppe dieser Kurve. \n",
    "Um letztere zu berechnen könnte man den obigen \"Algorithmus\" verwenden, der auf alle Punkte der Kurve $E_0$ eine $2^{250}$-Skalarmultiplikation anwendet und prüft, ob das Ergebnis gleich dem Identitätselement ist. Dieser hätte dabei eine Zeitkomplexität von $O(order(E_0))$, wobei zusätzlich bei jeder Iteration die kostspielige $2^{250}$-Skalarmultiplikation berechnet werden muss. Dieser Algorithmus kommt also für einen praktischen Einsatz nicht in Frage. \n",
    "Lange Zeit (ca. 1990 - 2011) herrschte ein Mangel an Algorithmen, die dieses Problem effizient lösen. Daher wurden isogeniebasierte Kryptosysteme in dieser Zeit innerhalb der Post-Quanten-Kryptographie vernachlässigt. Erst nach dem Vorschlag eines solchen Algorithmus, mit effizienter Laufzeit konnten praxistaugliche kryptographische Protokolle implementiert werden [2]."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "complicated-singing",
   "metadata": {},
   "source": [
    "Die Kernidee hinter diesem Algorithmus ist dabei folgende:\n",
    "Eine Isogenie $\\phi$ des Grads $l^e$ kann auch als $e$ Isogenien des Grads $l$ ausgedrückt werden. Dann gilt: $$\\phi = \\underbrace{\\phi_0 \\oplus \\phi_1 \\oplus \\dots \\oplus \\phi_{e-1}}_{e-mal}$$\n",
    "Eine Isogenie mit dieser Eigenschaft wird auch als separable Isogenie bezeichnet.\n",
    "Der Algorithmus, der sich diese Eigenschaft zunutze macht wir nun im Folgenden besprochen."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "white-lighter",
   "metadata": {},
   "source": [
    "Zunächst wird der geheime Generatorpunkt $R$ ausgewählt, der die Ordnung $l^e$ besitzt. Durch diesen Punkt $R$ wird nun mittels der $l^{e-1}$-Skalarmultiplikation der Punkt $R_0 = [l^{e-1}]R$ berechnet. Dieser Punkt $R_0$ hat selbstverständlich die Ordnung $l$. Mithilfe dieses Punktes $R_0$ wird nun die erste Isogenie $\\phi_0$ berechnet und der intiale Punkt $R$ wird durch $\\phi_0$ auf das Bild $\\phi_0(R)$ abgebildet. Dieser Bildpunkt hat nun wiederum die Ordnung $l^{e-1}$. \n",
    "Dann kann der Prozess wiederholt werden. Der Bildpunkt $\\phi_0(R)$ wird nun durch die $l^{e-2}$ Skalarmultiplikation auf einen Punkt der Ordnung $l$ abgebildet. Dieser wird wieder zur Berechnung einer Isogenie $\\phi_1$ verwendet und durch diese abgebildet. Der Prozess wird insgesamt also $e$-mal wiederholt [2]. \n",
    "Die bekannten Eigenschaften der Isogenieberechnungen bleiben dabei gleich. Sowohl alle einzelnen als auch die zusammengesetzte Isogenie wird eindeutig durch den Generatorpunkt (bzw. dem von diesem aufgespannten Kern) definiert. \n",
    "Dieser Algorithmus besitzt somit eine konstante Zeitkomplexität von $O(e)$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "interim-cherry",
   "metadata": {},
   "source": [
    "Nun kann schlussendlich auf dieser Grundlage ein Algorithmus definiert werden, der eine noch deutlich geringere Komplexiät besitzt und daher auch durch den SIDHforJ implementiert wird. \n",
    "Erinnern wir uns daran, dass während der ersten Skalarmultiplikation $R_0 = [l^{e-1}]R$ selbstverständlich jedes Zwischenergebnis (jedes Resultat der $k$-Skalarmultilpikation) gespeichert werden kann. Nehmen wir nun an, dass ein solcher Punkt $Q = [l^{d}]R$ gespeichert wurde. Nachdem die Isogenie $\\phi$ durch den Punkt $R_0$ berechnet wurde, wird nun nicht der Punkt $R_0$ sondern der Punkt $Q$ durch die Isogenie abgebildet. Mittels des Bilds des Punktes durch die Isogenie $\\phi(Q)$ wird nun der nächste Generator $R_1 = [l^{e-d-2}]$ durch den Punkt $Q$ berechnet. Mittels dieser Methode sparen wir uns also in diesem Durchgang $d$ Skalarmulitplikationen auf der ersten Bildkurve. Je höher wir den Parameter $d$ wählen, desto weniger Skalarmultiplikationen müssen wir auf der Bildkurve durchführen. Jedoch wird bei steigenden $d$ die Anzahl der möglichen Punkte $Q$ kleiner, da schließlich gilt:  $Q = [l^{d}]R$ [2].\n",
    "Es gilt nun, für jede Iteration dieses Algorithmus den \"besten\" Parameter $d$ zu finden. Dieses Optimierungsproblem kann bei gegebener initialer Kurve und gegebenen Generatorenpunkten bereits gelöst werden, sodass diese \"Parameterstrategie\" in der Praxis Teil der öffentlichen Parameter wird."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "appointed-outdoors",
   "metadata": {},
   "source": [
    "Die im SIDHforJ verwendete Liste **splitA**, bzw. **splitsB** innerhalb der öffentlichen Parameter enthält dabei für jede Iteration des genannten Algorithmus den \"besten\" Parameter. Die Anzahl der Einträge dieser Liste, die durch die Parameter **maxA**, bzw, **maxB** gespeichert wird, gibt dabei die Anzahl der Iterationen an, die der Algorithmus durchlaufen muss."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "gothic-supplier",
   "metadata": {},
   "source": [
    "# Referenzen\n",
    "_[1]_ Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies; Jao David, De Feo Luca; 2011 PQCrypto 2011\\\n",
    "_[2]_ Public-Key Cryptosystem Based on Isogenies; Rostovtsev Alexander, Stolbunov Anton; 2006 DBLP \\\n",
    "_[3]_ Mathematics of Isogeny Based Cryptography; De Feo Luca; 2017 Université de Versailles\\\n",
    "_[4]_ Understanding Cryptography; Paar Christof, Pelzl Jan; 2010 Springer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "confident-sleeve",
   "metadata": {},
   "source": [
    "***\n",
    "&copy; 2021, Linus Meierhöfer"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}