Grundlagen.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "failing-awareness",
   "metadata": {},
   "source": [
    "# Grundlagen "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "verbal-compact",
   "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": "junior-breath",
   "metadata": {},
   "source": [
    "Ziel dieses Notebooks ist die Erläuterung der absoluten Grundlagen des Supersingular Isogeny Diffie Hellman."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "divine-preliminary",
   "metadata": {},
   "source": [
    "## Elliptische Kurven"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "significant-simulation",
   "metadata": {},
   "source": [
    "Elliptische Kurven sind spezielle mathematische Kurven, die neben ihrer geometrischen Betrachtung auch mittels algebraischer Methoden untersucht werden können. \\\n",
    "Eine elliptische Kurve kann durch folgende Gleichung beschrieben werden:  \n",
    "$$y^2 = x^3 + ax + b \\ ; \\ a, b \\in \\mathbb{K}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "separate-stomach",
   "metadata": {},
   "source": [
    "Eine beispielhafte, über den reellen Zahlen definierte elliptische Kurve: $$y^2 = x^3 - 5x + 10$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "simplified-faith",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk4AAAGGCAYAAACNCg6xAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAgAElEQVR4nO3deZzNdf//8ccxGIMxso5hLFmqsQ4NRUqSNUsqSYs2UZIlRV3tC12trusylNYvTamrUioSslSIMIguO1mGKctsZZiZ8/vj9ZvNksGc8znL8367vW/nnJnjnJdheM77836/3i632+1GRERERE6rhNMFiIiIiPgLBScRERGRIlJwEhERESkiBScRERGRIlJwEhERESkiBScRERGRIlJwEhERESkiBScRERGRIlJwkqDgdrtJTU1F/V5FRORcKDhJUEhLSyMiIoK0tDSnSxERET+m4CQiIiJSRApOEtDi4+OJiYkhLi7O6VJERCQAuHTIrwSD1NRUIiIiSElJoUKFCk6XIyIifkozTiIiIiJFpOAkIiIiUkQKTiIiIhJwEhIgPr74X1fBSURERAJGairceivccgusXAnFvZK7ZPG+nIiIiIgzfvoJBgyA5GSYNs3CU3HTjJOIiIj4texsGD8eLrsMqlSBxETPhCZQcBIRERE/tmcPXH01/OMf8NBD8MMPUL++595Pl+pERETEL33xBdx5J5QpA/PmQceOnn9PzThJQFPncBGRwPPXX3DffdCnD7RvD2vXeic0gTqHS5BQ53ARkcCwbh3cdBNs3QqvvgpDhoDL5b3314yTiIiI+Dy3GyZOhLg4C0orVsC993o3NIGCk4iIiPi4P/6A3r1h2DAYNAiWL4cmTZypRYvDRURExGfNmwe33QZHj8LMmdCzp7P1aMZJREREfM7RozBmDHTuDI0b2wJwp0MTaMZJREREfMyWLbYAPDERXngBRo+GEj4y1eMjZUiwW7x4MT179iQqKgqXy8Xnn39e6PO33347Lper0LjkkkscqlZERDzB7YapUyE2Fg4fhiVL4OGHfSc0gYKT+IiMjAyaN2/OxIkTT/mcrl27kpSUlDdmzZrlxQpFRMSTDh6E/v1h4EC47jpYtcp20PkaXaoTn9CtWze6dev2t88JDQ0lMjLSSxWJiIi3zJ9vgSkjAz76CPr1c7qiU9OMk/iNhQsXUq1aNRo1asSgQYNITk4+5XMzMzNJTU0tNERExLdkZtr6pU6d4IILrLmlL4cmUHASP9GtWzcSEhL47rvveOWVV1ixYgUdO3YkMzPzpM8fP348EREReSM6OtrLFYuIyN/55Rdo3Rr+8x94+WWYOxdq1XK6qtPTkSvic1wuFzNmzKBPnz6nfE5SUhJ16tRh+vTp9O3b94TPZ2ZmFgpVqampREdH68gVERGH5eRYWBozBho0gIQEaN7c6aqKTmucxC/VqFGDOnXqsHnz5pN+PjQ0lNDQUC9XJSIif2fvXrjjDvj2Wxg+HMaPh7Awp6s6MwpO4pcOHDjArl27qFGjhtOliIhIEXz2mR2XEhoKc+ZYY0t/pDVO4hPS09NJTEwkMTERgO3bt5OYmMhvv/1Geno6o0ePZunSpezYsYOFCxfSs2dPqlSpwrXXXutw5SIi8nfS0uCuu6zFQIcOtgDcX0MTaMZJfMTPP//MlVdemfd41KhRAAwcOJDJkyezbt06pk6dyuHDh6lRowZXXnklH330EeHh4U6VLCIip7F0KdxyCyQnwzvvwO23g8vldFXnRovDJSikpqYSERGhxeEiIl6QlQXPPWejdWuYNg3q13e6quKhGScREREpNps3w623ws8/wxNPwKOPQskAShta4yQiIiLnzO2GyZOhRQs4cAB++MGCUyCFJlBwEhERkXO0Zw906wb33WdHpyQmQqCewx5gOVBERES8xe2G6dMtMJUtC998A126OF2VZ2nGSQJafHw8MTExxPniEdsiIn7swAHo3x8GDIDu3e0IlUAPTaBddRIktKtORKT4zJplvZmOHrV1Tb5+MG9x0oyTiIiIFEl6OgweDD16QGysNbMMptAEWuMkIiIiRfDDD7bwe/9+eOMNOz7F35tZng3NOImIiMgpZWbCmDFw+eVQowasWQP33BOcoQk04yQiIiKnsGaNNbPcuBFeeAEefBBCQpyuylmacRIREZFCsrMtKMXF2czSihXw8MMKTaDgJCIiIgVs2WKX5f7xDxg9GpYvh2bNnK7Kdyg4iYiICDk5EB8PzZvbAvDFi2HcOAgNdboy36LgJCIiEuR27IBOneD++/OPTGnXzumqfJOCk4iISJByu+H116FpU9i6FebNg0mToHx5pyvzXQpOEtB05IqIyMnt3AmdO8O999qxKevWwVVXOV2V79ORKxIUdOSKiIhxu+Gtt6y1QMWKdr9zZ6er8h+acRIREQkSu3ZB167WwPLGG22WSaHpzKgBpoiISIBzu+Gdd2DUKAgPh9mzLUDJmdOMk4iISADbvRu6d4e774brroNfflFoOheacRIREQlAbje89x6MHAnlysHXX1uAknOjGScREZEAs2cPXHMN3Hkn9O5ts0wKTcVDM04iIiIBwu2GadNg+HAoUwZmzoSePZ2uKrBoxklERCQA7NoFPXpY5+8ePWD9eoUmT1BwEhER8WM5Odb9u3FjWLPGZpnefx8qVXK6ssCk4CQiIuKntmyBjh2t+3f//ppl8gYFJwloOnJFRAJRdja88go0awa//Qbz58OUKdYJXDxLR65IUNCRKyISKNavt91yK1bAAw/A889buwHxDs04iYiI+IGjR+GZZyA2FlJT4YcfYMIEhSZvUzsCERERH/fzzzbLtGEDjB0Ljz1m7QbE+zTjJCIi4qP++gvGjIE2bSAkxC7PPfecQpOTNOMkIiLig77/Hu66C3buhGefhYceglKlnK5KNOMkIiLiQ9LS4P774fLLoUoVSEyERx9VaPIVmnESERHxEbNnW0+m33+3hd/332+X6MR3aMZJRETEYfv3w0032UG8DRvCunV23pxCk+/RjJOIiIhD3G54910YPRpKlICpU+GWW8DlcroyORXNOElAU+dwEfFVmzfbcSl33QXXXAP/+x/ceqtCk69T53AJCuocLiK+4uhRePlla2YZFQVvvAFXX+10VVJUulQnIiLiJcuWwaBB8OuvMGoUPPUUlC3rdFVyJnSpTkRExMPS0mDYMGjbFkJDrZHliy8qNPkjzTiJiIh40MyZMHQoHDwIr7xiAaqk/vf1W5pxEhER8YCkJLj+eujdG5o0gfXrYeRIhSZ/p+AkIiJSjHJy4PXX4aKLYPFi+OADmDUL6tZ1ujIpDgpO4hMWL15Mz549iYqKwuVy8fnnnxf6vNvt5qmnniIqKoqwsDA6dOjA+vXrHapWROTkEhNtHdO998J111mLgZtuUouBQKLgJD4hIyOD5s2bM3HixJN+/sUXX+TVV19l4sSJrFixgsjISK6++mrS0tK8XKmIyInS0uwyXKtWkJ5uB/S+/TZUquR0ZVLc1MdJfI7L5WLGjBn06dMHsNmmqKgoRowYwZgxYwDIzMykevXq/POf/2Tw4MGnfU31cRIRT3C74bPP7HiUgwetvcDIkTqQN5Bpxkl83vbt29m3bx+dO3fO+1hoaChXXHEFS5YsOemvyczMJDU1tdAQESlO27dbx+/rr4eWLWHDBnj4YYWmQKfgJD5v3759AFSvXr3Qx6tXr573ueONHz+eiIiIvBEdHe3xOkUkOBw9CuPGQUyMHcb7+efWckCLv4ODgpP4DddxqyvdbvcJH8v1yCOPkJKSkjd27drljRJFJMAtWgQtWsATT8D999ssU+/eTlcl3qRuEuLzIiMjAZt5qlGjRt7Hk5OTT5iFyhUaGkpoaKhX6hORwPf77/DQQ/B//weXXgqrVkGzZk5XJU7QjJP4vHr16hEZGcncuXPzPnb06FEWLVpE27ZtHaxMRAJdTg68+SZccIFdjnvzTfjhB4WmYKYZJ/EJ6enpbNmyJe/x9u3bSUxMpFKlStSuXZsRI0Ywbtw4GjZsSMOGDRk3bhxly5ZlwIABDlYtIoFs7VoYMgSWLoWBA+Gll6BqVaerEqcpOIlP+Pnnn7nyyivzHo8aNQqAgQMH8t577/Hwww/z119/cd9993Ho0CHatGnDt99+S3h4uFMli0iASkmxtgL/+Q80agQLF8IVVzhdlfgK9XGSoKA+TiJyOm43TJtmLQXS0+Gxx2DUKChd2unKxJdojZOIiAS9xERo394uyXXoYEeljB2r0CQnUnASEZGgdeiQtRVo1cruz58P06dDrVpOVya+SmucREQk6OTkwHvv2azSkSO28HvYMHX9ltPTjJOIiASVn3+Gtm3hrrugc2fYuNHWMik0SVEoOElAi4+PJyYmhri4OKdLERGHHThg7QVat4Y//7Qu4O+/DwX66oqclnbVSVDQrjqR4JWdDW+9BY8+CllZ8OyzcN99UFKLVeQsaMZJREQC1k8/QZs2NtPUqxds2gQPPKDQJGdPwUlERAJOUhLccQdccoktBP/xR3j3XTjF8ZYiRabgJCIiAePIEXjhBev4/eWXMGkSrFhhi8FFioMmK0VExO+53fD55zB6NPz2m/VmeuIJOO88pyuTQKMZJxER8Wvr1kGnTtC3r800rVsHr72m0CSeoeAkIiJ+6Y8/bHdcixawezd8/TXMng0XXuh0ZRLIdKlORET8yrFjtnbpqafsEt3LL8PQoTpXTrxDwUlERPzGN9/AyJHW7fuee6wnU9WqTlclwUSX6kRExOdt2gTXXAPdullLgVWr4PXXFZrE+xScJKDpyBUR/3bwoM0wNW4M69fDJ5/AggW2rknECTpyRYKCjlwR8S+ZmRAfb5fisrJg7Fg7iDcszOnKJNhpjZOIiPgMtxs+/RTGjIEdO2DQIHj6aXX8Ft+hS3UiIuITfvoJ2reHG26ACy6AtWttHZNCk/gSBScREXHUjh3Qv7+dK5eWBt9+C7Nm2bomEV+j4CQiIo44fBgefthmlxYvhrfftt1yV1/tdGUip6Y1TiIi4lVHj8KUKdbA8q+/4JFH7Iy58uWdrkzk9BScRETEK9xu+O9/4dFHYds2uOMO2zUXFeV0ZSJFp0t1IiLicQsWQOvWcOONdpbcmjV2aU6hSfyNgpOIiHjMmjXW7btjRyhRAhYuhK++gqZNna5M5OwoOImISLHbsQNuuw1iY2HrVuv4vWwZXHGF05WJnBsFJwloOnJFxLsOHIAHH7Sdct9+C5Mm2VEp110HLpfT1YmcOx25IkFBR66IeFZGBvz73/DPf0J2trUZGDlSO+Uk8GhXnYiInLXMTGst8PzzdiDvkCHw2GNQrZrTlYl4hi7ViYjIGcvKgnffhUaNYMQI6N4dNm2yWSeFJglkmnESEZEiy8mxhd5PPAEbN9q5cnPmWIsBkWCgGScRETktt9vOj2vVynox1a9vx6N8/LFCkwQXBScREflbixbBZZdBjx4QHg7ffw9ff22tBkSCjYKTiIic1LJl0LkzdOhgi8C/+SY/RIkEKwUnEREp5KefrNv3pZfC3r22pmnFCujSRb2YRBScREQEgOXLbXfcJZfAb7/BRx/B2rVqXilSkIKTBDR1Dhc5vZ9/hmuugTZt7KiU6dMtMPXrZ+fLiUg+dQ6XoKDO4SInWrkSnnrKDt298EJrMdCvH4SEOF2ZiO/SzxIiIkFm1Sro3Rsuvhg2b4aEBPjlF7jpJoUmkdNRcBIRCRJLllhLgVat4NdfYdo0O4B3wAAFJpGiUnASEQlgbjfMnWstBdq1g5074f33YcMGuOUWBSaRM6XgJCISgHJy4IsvbMF3586QkQEzZtii75tvhpI6cEvkrCg4iYgEkKws+OADaN4c+vSBsDA7S275cnusXXIi50bfQuIXnnrqKVwuV6ERGRnpdFkiPuPoUXjrLdsdd/PNUKuWHY2yaJHNOKkPk0jx0GSt+I3GjRszb968vMchWpwhQkYGvP02vPQS7NkDffvawbstWzpdmUhgUnASv1GyZEnNMon8f/v3w8SJMGkSpKTYzrixYyEmxunKRAKbgpP4jc2bNxMVFUVoaCht2rRh3LhxnH/++Sd9bmZmJpmZmXmPU1NTvVWmiEf973/w6qswdaot8L77bhgxAurWdboykeCgNU7iF9q0acPUqVOZM2cOb775Jvv27aNt27YcOHDgpM8fP348EREReSM6OtrLFYsUH7fb1iv17g0XXQRffglPPgm7dsGECQpNIt6kI1fEL2VkZFC/fn0efvhhRo0adcLnTzbjFB0drSNXxK9kZ1sLgZdfhp9+sstwo0fbZbnQUKerEwlOulQnfqlcuXI0bdqUzZs3n/TzoaGhhOp/FvFT6enw3nvw2muwbRtceSV8/TV07ap2AiJOU3ASv5SZmcmvv/5K+/btnS5FpNhs2wbx8bZLLj0dbrgBPvrIzpQTEd+g4CR+YfTo0fTs2ZPatWuTnJzMc889R2pqKgMHDnS6NJFz4nbDggXw73/DzJlw3nkwZAjcdx/Uru10dSJyPAUn8Qu7d+/mpptu4o8//qBq1apccsklLFu2jDp16jhdmshZ+fNPSEiwwPTLL9CkCbzxhjWvLFvW6epE5FS0OFyCQmpqKhEREVocLo7bvBmmTIF33oFDh6BXL3jgAVvHpO7eIr5PM04iIh527JgduPv66zB/PlSqBLffDkOHwilakYmIj1JwEhHxkJ074c03bbH3vn3Qrh1MmwbXXw9lyjhdnYicDQUnEZFilJ0Ns2fb7NKsWVC+PNx2GwweDE2bOl2diJwrBScRkWKwa5f1XnrzTbvfqpWtZerf38KTiAQGBScJaPHx8cTHx5Odne10KRKA/vrLOnu/9x7MmwdhYdbVe/Bg9V4SCVTaVecDsrPh8GFIS7Mtyn/+af8g597PHceO2XOPHzk5dthnyZIQEpJ///hRurT95FuunI2C98uVs18bqLSrToqL223Hn7z7LkyfDqmp0L493HGHrV0KD3e6QhHxJM04eYDbDQcPwt69hUdSkn384EE4cCD//uHDRXvd3GB0/ChRwgJUVlb+yA1VZ6JMGQtTFStaE77cUalS4ceVK0O1alC9ug1dhpBgsH27BaWpU+F//4PoaGsjMHAgNGjgdHUi4i0KTmfpyBH7h3TrVtiypfDtb79BgfNlAahaFSIjoUoVCyK1a9tt7jjvPIiIsMZ3YWF2W3CUKXPmPV7c7sKB6sgRyMjIH+npJz5OT7cgd+iQjeRk2LjR7h88aLNixytbNj9EFRyRkVCzpv0HU6uW/d51zpb4k/374eOP4YMPYNky+97s08eaVnbsGNiztCJycrpUdxpZWdawbu1aWLfObteutXCU+5UrUwbq17fRoAHUqWOBISrKbiMj7TJZIMjKsgC1f//JR3Jy4cdZWfm/tnTpwkEqd+Q+rlPHwpUnmgDqUp0U1aFD8NlnNrv03XcW9rt2hZtusmaVmmEVCW4KTgW43RaSli2DpUth+XJYvz5/9igqCpo1sy3FF15oIal+fahRQzMpJ5OTA7//bjuMdu/OH8c/Pno0/9eULw9160K9eicfZ7t+RMFJ/k56Onz9NXz4obUSOHYMOnSwsHTddTYrLCICQR6csrJgxQrr5LtkiS34PHjQPhcTA61bQ2xsfliqXNnZegOR250frnbutNPht2/PHzt22CXGXJUrW4CqXx8aNSo8KlY89fsoOMnx/vgDvvzSdsXNnWt/z1q3trDUr5/9oCQicrygCk5uN2zYYNuG582DRYtszU6FCtbR95JLbLRu/ff/CYv3uN3WcblgmMpdW7Z5sy26z1W16olhqlEjmxk8elTBSewS+4wZNr7/3v5+tW0L115ra5fq13e6QhHxdQEfnLKybDbp88/trKht22ytTbt20KkTXHWVNaorqWXyfiktzRblb9pkY+PG/PspKfYclwtq1Upl164I7rknhSZNKuSFqtq1tcA3kB07Zt//s2dbF+916+z7/6qrLCz17GlrEEVEiiogg1NWll1+mz7dpuIPHLB1SL16Qe/ecMUVthNMAlfuJcDcELVuXSoTJkRw4YUpbN9eIW/dWunSNiN1spmqatV0Wr0/2r0bvv3WgtLcudZnqVo16NYtf2jSUUTOVkAFp1WrrMfK9Om2o6tRI1vY2aePdfHVAu7gVXCNU7lyFdi1Kz9UFRw7duTvlqxQ4eSBqmFD/cfrS/bvhwULbHz3nc1Aulx22b1bN+je3dYq6vtfRIqD3wenv/6yoDR5si30rl7dFnfecgu0bKkZg2BX8MiVTZs2nXaN05Ejdjm34CW/3JGcnP+8yMjCYeqCCyxQnX8+hIZ64TcWxHbtsl2v339vQWnDBvv4RRfBlVfmD23mEBFP8NvgtGWLhaV337WGjV26wL332k+XWq8kxyuOXXWHD9uC9JPNVKWn23NKlLB1Uw0aWJAqeKtQdeaOHLGZ5NwWIUuXwp499rn69S0gdexorQNq1HC0VBEJEn4XnNasgfHj4b//tZ1vd91lB2pqN4z8HU+2I8jd+bdxowX6LVssYOXe//NPe57LdWKoql/fGn/WrWt/n4N5hjQ52b6/C45ff7U1i2FhEBdnl98uvdRutahbRJzgN8Fp9Wp4/HFrUle3LowZY2dEhYU5XZn4A6f6OLnddkZhwTBVMFRlZOQ/Nzw8P0Qdf1u7trVb8Pd1OtnZ1hJg06b82buNG223W1KSPadcOeub1qIFNG9ugalZMyhVytnaRUTAD4LTjh3w2GOQkGBrSR57DPr31z+icmZ8sQFm7s6/HTus+efJbnMvAYK1Tahe3S5JRUYWvs29X7WqnXtYsaL32yxkZdlxJXv35neF37OncMf4bdvyO8WXLm0zbg0bWlBq3tzCUv36/h8QRSRw+WxwSk+HZ56Bf/3Ljjt4+mm4806tX5Kz44vB6XTcbgsiO3bYLM2+fTYrk3ube3/fvsJnAuYKD7cQlRukIiJshjYszM5XLHhburRdJiw43G47bujIkRNvMzKsy37uYdAnOwC6RAkLdLlnEtasWbj1g3poiYg/8sngNHMm3H+//TT+yCPw4IM2fS9ytvwxOBVVTo4Fl6QkO0bk8OH8QHPoUP7jlBTbhXrkSOHbv/6yWSC3O3+AhacyZWxB+/G3ZcvaDzS5wSz3fqVK+YdbV6+uH3REJPD41D9rv/8OQ4bYyeRdu0J8vO1EEpFTK1ECqlSxISIinuUzwWnuXLjtNrvkMH26HbIZzDuMRERExPc4vgTz2DF46CHo3NkWiK5dCzfeqNAkIiIivsfR4HTwoF2SmzABXnoJvvlGTeykeMXHxxMTE0NcXJzTpYiISABwbHH45s12jtThw/Dpp3bwroinBPLicBER8R5H1jitWwdXX227cFasgHr1nKhCRERE5Mx4/VLdihU2uxQVBYsXKzSJiIiI//BqcPrf/2xN0wUX2KnmVat6891FREREzo3XgtPevRaaatSAWbOsk7GIiIiIP/FKcMrMhN69rUfT7Nm2tklERETE33hlcfjo0dafackSiI72xjuKiIiIFD+PB6evvoKJE2HSJGjVytPvJiIiIuI5Hu3jlJYGjRvbmDVL3cDFOerjJCIixcGja5yeeQYOHIDJkxWaRERExP95LDglJdkluocegrp1PfUuIn9PR66IiEhx8tiluuHDYepU2LEDIiI88Q4iRadLdSIiUhw8MuOUng7vvAP336/QJCIiIoHDI8Hpv/+FjAy4+25PvLqIiIiIMzwSnD76CK68EurU8cSri4iIiDij2IPTkSOwaBH06FHcrywiIiLirGIPTsuWWXjq1Km4X1lERETEWcUenNasgdBQiIkp7lcWERERcVaxB6eNG6FRIyjplVPwRERERLyn2IPTH39A9erF/aoiIiIizivSvJDb7SYtLa1IL3joEJQpA6mp51SXyDnJzMwkMzMz73Hu399U/cUUEZFTCA8Px3WaM+KK1Dk8t+uyiIiISKAqyukSRQpOfzfjFBcXx4oVK/IeDx5sx6zMmXNmxRbV8e/naampqURHR7Nr1y6vHdXh7d9jIL7n8TNOSUlJtG7dmg0bNlCzZk2PvOfJBNrX1Rfez4nvSQj8r6sT76l/XwPjPQPpe7IoM05FulTncrlO+cUICQkp9LkaNWxnnae+dse/n7dUqFDBa+/rxO8xWN4zPDzcq+8ZDF/XYPiehOD4ugbDn2WwfF2deM9A/57Mdc6Lw4cOHVrocd26sG0bHDt2rq9ctPcLRE78HoPlPb0tGL6uwfDnCMHxdQ2GP8tg+brqz9JzinSp7kz88AO0bw+rV0OLFsX5ys7IXd9VlOue4rt2796dN5Vcq1Ytp8uRc6DvycChP8vAEGx/jsXejqBlS2uAuWBBcb+yM0JDQ3nyyScJDQ11uhQ5B7l/fvpz9H/6ngwc+rMMDMH251jsM04A3bvbsSvffVfcryxydoLtJyIREfGMYp9xAujb1w76/e03T7y6iIiIiDM8Epz694dy5eDNNz3x6iIiIiLO8EhwKl8ebr8dJk2ClBRPvIOIiIiI93kkOAGMGQN//gmvvuqpdxARERHxLo8Fp5o1YdgwePll2L7dU+/iWceOHWPMmDE0bdqUcuXKERUVxW233cbevXudLk2KKD4+npiYGOLi4pwuRc7R+PHjiYuLIzw8nGrVqtGnTx82btzodFlyjsaPH4/L5WLEiBFOlyJnYc+ePdxyyy1UrlyZsmXL0qJFC1auXOl0WR7lseAE8PjjULmyHcNS/Hv3PO/PP/9k1apVPP7446xatYrPPvuMTZs20atXL6dLkyIaOnQoGzZs8PpxB1L8Fi1axNChQ1m2bBlz584lKyuLzp07k5GR4XRpcpZWrFjBlClTaNasmdOlyFk4dOgQ7dq1o1SpUsyePZsNGzbwyiuvULFiRadL8yiPtCMoaPZsa08waRLce68n38k7VqxYQevWrdm5cye1a9d2uhwpIrUjCDy///471apVY9GiRVx++eVOlyNnKD09nZYtWzJp0iSee+45WrRowYQJE5wuS87A2LFj+fHHH/n++++dLsWrPDrjBNCtG9x3HwwfDsuWefrdPC8lJUXBiFIAAB6ESURBVAWXyxXwiVrE16X8/50nlSpVcrgSORtDhw6lR48edOrUyelS5CzNnDmTiy++mBtuuIFq1aoRGxvLm0Gwnd7jwQngtdfg4ovh+ushKckb7+gZR44cYezYsQwYMECzFiIOcrvdjBo1issuu4wmTZo4XY6coenTp7Nq1SrGjx/vdClyDrZt28bkyZNp2LAhc+bMYciQITzwwANMnTrV6dI8yivBqXRp+OQTu9+5Mxw86I13PXMJCQmUL18+bxScfjx27Bj9+/cnJyeHSZMmOViliNx///2sXbuWDz/80OlS5Azt2rWL4cOH8/7771OmTBmny5FzkJOTQ8uWLRk3bhyxsbEMHjyYQYMGMXnyZKdL86iS3nqjqCiYO9cOAO7eHb79Fnxt0qZXr160adMm73HNmjUBC039+vVj+/btfPfdd5ptEnHQsGHDmDlzJosXL9aBzX5o5cqVJCcn06pVq7yPZWdns3jxYiZOnEhmZiYhISEOVihFVaNGDWJiYgp97KKLLuLTTz91qCLv8FpwArjoIvjmG7j6arjySls4Xq2aNyv4e+Hh4YSHhxf6WG5o2rx5MwsWLKBy5coOVScS3NxuN8OGDWPGjBksXLiQevXqOV2SnIWrrrqKdevWFfrYHXfcwYUXXsiYMWMUmvxIu3btTmgJsmnTJurUqeNQRd7h1eAEttZp0SLo0gXatbOZJ1/99y8rK4vrr7+eVatW8dVXX5Gdnc2+ffsAW5BaunRphysUCR5Dhw7lgw8+4IsvviA8PDzvezEiIoKwsDCHq5OiCg8PP2FdWrly5ahcubLWq/mZkSNH0rZtW8aNG0e/fv1Yvnw5U6ZMYcqUKU6X5lEeb0dwKtu22XqnlBT4+GObgfI1O3bsOOVPtQsWLKBDhw7eLUjOmtoR+D+Xy3XSj7/77rvcfvvt3i1GilWHDh3UjsBPffXVVzzyyCNs3ryZevXqMWrUKAYNGuR0WR7lWHAC+OMPOxB44UJ48UUYORJO8W+jyDlRcBIRkeLglV11p1Kliq15GjkSHnwQunYFnWYixUlHroiISHFydMapoG++gTvvhMxMmDwZbrhBs09SfDTjJCIixcHRGaeCunaFdetsrdONN0KPHrBli9NViYiIiOTzmRmnXG43zJxpR7Ts2wdjxsDYsaBNM3IuAnnGKSfHmsr+/ruN5GRbP3j4MKSmnjjS0uDIETh6FI4dO/G2RAkbISE2SpSAMmWgXDkoX95uC96vWNHailStWvi2enV934pI4PG54JTrzz/h+efhpZdsLdTjj8Ndd1kXcpEz5Y/Bye22oLNrF+zeXXjs2gV79lhIOnDAwlNBISEWaCpUsBEeXvh+mTL2vVS6NJQqlX+/ZEl73+xse82cHLt/5AhkZEB6+om3hw5ZYDt8+MTfQ9WqUKcO1K6df9ugAVxwgbUhKen1higiIufGZ4NTrq1b4amnICEB6taFJ5+Em2/WP7hyZnw1OGVmWmuOTZtg82Yb27blB6T09PznulwQGQm1akF0NNSsaTM7ubM8uaNaNQtN3l4jePSozXQlJ1uQ2rsXfvsNdu4sfHvkiD2/ZEmoX99CVJMm0KIFNG9uwaqEzywiEBEpzOeDU65ffoEnnoAZM+wn1ZEjbTF5uXJOVyb+wMnglJVloSE3HBUMSTt35s8WlSsHDRtamIiOtoCUO6KjoUYNmx3yZzk5NlO2aZONjRttrF2bv6O2bFlo1sxCVPPmEBdnt/7+exeRwOA3wSnXqlXw8svWNLNCBbj3XrjnHrsMIHIqng5OBQPB8eFo2zZbOwQQGmrBqFEjC0m5tw0bWjAK5p2kv/8Oa9bkj8RE+PVXC55hYXbqwKWX5o/q1Z2uWESCkd8Fp1w7d8KECfDWW7bWonNnuPtu6NVL66DkRMURnNxuuwx1snC0eXP+JaiQEJsVPT4cNWpks0c6iqvoMjNh9WpYsgSWLrWxZ4997vzzbRdux452W6OGs7WKSHDw2+CUKz3dZp/efBOWLbM1Hrfeai0N4uKC+yd4yXcmwenQoZOHo02bbEca2N+r2rXzZ4sKhqO6dXVZyZN27bIA9eOP8N13dhkf7BDxjh1tdOgAlSo5WqaIBCi/D04FrVtnM1AffmjT/nXqWCPNfv1sml8hKvjEx8cTHx9PdnY2mzZtygtO6emFA1HB+wcO5P/6GjVOHo7q17edaeK8/fvt2KbvvoP5821Dictl3/M9etho2VILzkWkeARUcMqVlQWLF8N//wuffpoforp1s9Gxo/WgkcB25Ij9J7p5M6xdm8qTT0bQtm0K27dXICkp/3mVK588HDVoYFv3xb/s3GkhavZsmDPHWjpUrw7du9u4+mqIiHC6ShHxVwEZnArKyoJFi+Dzz+0f0q1bbQ1U+/a2LuqKK+ynUV1a8U+pqfZnunWrdZrPvd2yxdbC5P7tLl8+lfT0CK67LoWYmAqFQpIu6QSuY8dsfdTXX9vYsMHaIHToAH37wrXXWosHEZGiCvjgdLwtWyxAzZ5tgerPP23786WXwuWXW6C6+GLNNPgKt9sunRUMRQVvk5PznxsRYbNEDRrYpbTc20aNICwslYoVfa+Pk3jXjh0WoD7/HBYssN2Q7dpZiOrbV7tzReT0gi44FXTsmLU3WLwYvv/exuHDtj6iUSMLUK1a2YiNVZjyhOxs699TsEni8fczMvKfX7164VBUMChVqnTqdWy+2gBTnHPgAHz5pV3O//Zba+DZqhVcfz3072+L/EVEjhfUwel4OTk2lf/zzzZWrrReMrnbzGvVsp07x4+qVbXw/GSysmxGaO/e/LF7d+FQtHu3hadc551nP/Xnjtq17T+wBg1s+/nZhlcFJ/k7qakwa5aFqK+/hr/+grZtYcAA21xStarTFYqIr1BwOo2sLAtTa9ZYM77csWVL/n/4FSoU/o++4H/80dF2BEagrKHKzMw/TPZkIykpPyQlJxc+Qy0kxNaTnOprVbu252b1FJykqNLT7aDxhARbXA62HnLAAOjdWzPPIsFOweksHT1q4enXX22tTe4MSu7I7feTq1Kl/HPFcsd55+UfvJo7IiLy74eFFT6AtVSpM99S7XbbJck//7Sfok91m5YGKSl2qfLw4RPv5x7kevzvC6zOqlXtMOaoqPxRo0bhx1WrOtf8UcFJzsbvv8Mnn8AHH8APP9jf9T594Pbb4aqr1MxUJBgpOHmA222BI/dSVHJy/ti/P/9+SopdIkhJOfF0+1MJCckPU6VK2XsVPMU+937Bx0UVFmbBrWJFG7n3c28LHiRbcPjDeYEKTnKudu60HnFTp9oPTLVqwW23WYhq2NDp6kTEWxScfIDbbTM/qamFx5EjNrN19KjNGhW8zb3vclmYKlHCRsH7uaNMGQtFYWG2g7Dgbe79cuXsHLVApeAkxcXthuXL4b33LEilpNjOvDvusPVQupQnEtgUnCQoKDiJJ/z1F3zxBbz7Lsydaz+I3HQTDBliu3JFJPDoEAIJaPHx8cTExBAXF+d0KRKAwsKsdcGcObZbdOxYa20QF2fB6a23bLG5iAQOzThJUNCMk3hLdrY12H39dWtxUL68HTw+eDA0a+Z0dSJyrjTjJCJSjEJC4Jpr4KuvYPt2GD4cPvsMmje3tVDTptklPhHxTwpOIiIeUqcOPPusXcb75BPbiHHbbVCzJjz4IGzb5nSFInKmFJxERDysVCm47jpbQL55M9x1l+3Ka9DA+kJ9913+gdQi4tsUnEREvKhBA3jpJdi1C954wxrpXnWVXcp76y1dxhPxdQpO4hduv/12XC5XoXHJJZc4XZbIWStbFgYNgnXrYN48O5PxnnvsmKZHH7XmuSLiexScxG907dqVpKSkvDFr1iynSxI5Zy6XzTjNnAmbNsEtt8DEiRakbrwRfvrJ6QpFpCAFJ/EboaGhREZG5o1KlSo5XZJIsWrQACZMsNmm116DVavgkkugfXsLVmdyhJKIeIaCk/iNhQsXUq1aNRo1asSgQYNITk52uiQRj6hQAYYNg40bYcYMC0y9e0NMDLz5ph3HJCLOUANM8QsfffQR5cuXp06dOmzfvp3HH3+crKwsVq5cSehJDtnLzMwkMzMz73FqairR0dFqgCl+a8kSePll+PxzO1x72DC4916oXNnpykSCi4KT+JyEhAQGDx6c93j27Nm0b9++0HOSkpKoU6cO06dPp2/fvie8xlNPPcXTTz99wscVnMTfbdpkl/Hee88O8b7zTusJVbeu05WJBAcFJ/E5aWlp7N+/P+9xzZo1CQsLO+F5DRs25O6772bMmDEnfE4zThLokpMhPt7G4cMwYAA88ghcdJHTlYkENq1xEp8THh5OgwYN8sbJQtOBAwfYtWsXNWrUOOlrhIaGUqFChUJDJJBUqwZPPw07d8Irr1gTzcaNrdHmypVOVycSuBScxOelp6czevRoli5dyo4dO1i4cCE9e/akSpUqXHvttU6XJ+KocuXsPLytW23h+Nq1cPHF0LUrLF7sdHUigUfBSXxeSEgI69ato3fv3jRq1IiBAwfSqFEjli5dSnh4uNPlifiE0FA7yuXXX+HDD2HvXrjiCmtlMHu2jnQRKS5a4yRBITU1lYiICK1xkqDhdsNXX8Hzz1sTzdhY60h+7bUQEuJ0dSL+SzNOIiIByOWCnj1h6VJb/1S5MtxwAzRpAh98ANnZTlco4p8UnEREApjLBVdeCXPnwrJl1p385pstQH34oQKUyJlScBIRCRJt2sCXX8Ly5VC/vrUwUIASOTMKTiIiQSYuztY/KUCJnDkFJxGRIKUAJXLmFJwkoMXHxxMTE0NcXJzTpYj4rNwA9dNPcP75ClAif0ftCCQoqB2BSNEtX25dyWfNgpgYePZZa2PgcjldmYjzNOMkIiKFtG4NX39tu/Bq1rRjXOLiYM4cNdIUUXASEZGTatMGvv0WFiywzuRdu0KHDvDDD05XJuIcBScREflbuWHpq68gJcWOcenRA1avdroyEe9TcBIRkdNyuSwsrVoFH30EW7ZAy5bQrx/8739OVyfiPQpOIiJSZCVKWFhavx7eecd24jVuDHfeCTt3Ol2diOcpOImIyBkrWRLuuAM2bYIJE2wxecOG8MADkJzsdHUinqPgJCIiZy00FIYNg23b4JlnYOpUa6b57LOQkeF0dSLFT8FJRETOWblyMHYsbN0KgwfDc8/ZgcJvvAHHjjldnUjxUXCSgKbO4SLeVbkyvPyyXcK7+mq4917rQv7ZZ+oBJYFBncMlKKhzuIgzEhNtJmrOHLj0UnjxRbjsMqerEjl7mnESERGPadECvvkG5s2DzEzrAdW7N/z6q9OViZwdBScREfG4q66CFSvggw9g3Tq7fDdoEOzd63RlImdGwUlERLyiRAm46SabbXr1VZgxwxaQ/+MfkJbmdHUiRaPgJCIiXhUaCsOH2w68kSMtRDVsCG+9BdnZTlcn8vcUnERExBEREfD887YDr1Mnu3QXG2vroUR8lYKTiIg4Kjoa3n/fjm+pUMHaGPTsqTPwxDcpOImIiE9o3Rq+/x4+/hh++cUWkA8bBn/84XRlIvkUnERExGe4XHDDDbaAfNw4O8KlQQN45RVrZyDiNAUnERHxOWXKwMMPw+bNMGCA3W/cWB3IxXkKThLQdOSKiH+rVg0mTYK1a23n3XXXQYcOsHKl05VJsNKRKxIUdOSKSGD45ht48EHYsAFuuw3Gj4eoKKerkmCiGScREfEbXbvCmjUweTLMmgWNGsELL2j9k3iPgpOIiPiVkiVhyBDr/3T33fDYY7b+6csvtf5JPE/BSURE/NJ558GECbb+qV496NULundX/yfxLAUnERHxazEx8O23dvbdxo3QtCmMHg0pKU5XJoFIwUlERPyeywV9+tii8aeesjVQjRrBO+9ATo7T1UkgUXASEZGAUaYM/OMfNvPUqRPcdRdccgksW+Z0ZRIoFJxERCTg1KoFCQl2hEtWFlx6KQwcCElJTlcm/k7BSUREAtZll8GKFTBlSn77ghdfhKNHna5M/JWCk4iIBLSQEBg0yNoX3HUXPPooNGsG8+c7XZn4IwUnCWg6ckVEcuW2L1i92o5y6dQJbrwR9uxxujLxJzpyRYKCjlwRkYLcblsDNXo0pKfbTrzhw6FUKacrE1+nGScREQk6Lhfccovtvrv7bhgzBlq0gAULnK5MfJ2Ck4iIBK2ICLt8t2qVXcrr2BEGDIC9e52uTHyVgpOIiAS95s1h8WJ47z2YNw8uvBBeew2OHXO6MvE1Ck4iIiJAiRLW62nTJrsdPRpatrRAJZJLwUkc99lnn9GlSxeqVKmCy+UiMTHxhOdkZmYybNgwqlSpQrly5ejVqxe7d+92oFoRCXQVK8J//gM//wzly8MVV8Ctt8K+fU5XJr5AwUkcl5GRQbt27XjhhRdO+ZwRI0YwY8YMpk+fzg8//EB6ejrXXHMN2dnZXqxURIJJbCz8+CO8/TZ88w1ccAHEx4P+2QluakcgPmPHjh3Uq1eP1atX06JFi7yPp6SkULVqVaZNm8aNN94IwN69e4mOjmbWrFl06dLltK+tdgQici4OHoRHHrEO5HFx8MYbFqwk+GjGSXzeypUrOXbsGJ07d877WFRUFE2aNGHJkiUOViYiwaJSJQtLP/4If/0FF18Mo0ZBWprTlYm3KTiJz9u3bx+lS5fmvPPOK/Tx6tWrs+8Uiw4yMzNJTU0tNEREzlXbtta6YPx4eP11iImBGTOsoaYEBwUn8aqEhATKly+fN77//vuzfi23243L5Trp58aPH09ERETeiI6OPuv3EREpqFQpePhh2LDBmmb27Qu9e8POnU5XJt6g4CRe1atXLxITE/PGxRdffNpfExkZydGjRzl06FChjycnJ1O9evWT/ppHHnmElJSUvLFr165iqV9EJFfdujBzJnz6qc1CxcTASy+p91OgU3ASrwoPD6dBgwZ5Iyws7LS/plWrVpQqVYq5c+fmfSwpKYlffvmFtm3bnvTXhIaGUqFChUJDRKS4uVw24/TrrzBoEIwda+ufli51ujLxFAUncdzBgwdJTExkw4YNAGzcuJHExMS89UsRERHcddddPPjgg8yfP5/Vq1dzyy230LRpUzp16uRk6SIiAISH29EtK1ZA6dLQrh0MGQLHTZRLAFBwEsfNnDmT2NhYevToAUD//v2JjY3l9ddfz3vOa6+9Rp8+fejXrx/t2rWjbNmyfPnll4SEhDhVtojICVq2hGXL4N//hg8+sKNbEhK0eDyQqI+TBAX1cRIRb9u7F0aMgP/+Fzp1sl149es7XZWcK804iYiIeEBUFHz8McyaBZs3Q9Omtng8K8vpyuRcKDiJiIh4ULdu8MsvtuZp7Fho3dp24Yl/UnASERHxsPLl4dVXbf1TTo4d2/LQQ/Dnn05XJmdKwUlERMRL4uJs593zz8PEidCkCRTotCJ+QMFJRETEi0qVskt2a9daE83OnWHgQDhwwOnKpCgUnCSgxcfHExMTQ1xcnNOliIgU0rAhzJ8Pb79tHcgvvNBaGGivu29TOwIJCmpHICK+bN8+GD7cduF17WqtC+rUcboqORnNOImIiDgsMhI++shmnn75BRo3tk7k2dlOVybHU3ASERHxET17wvr1cMcdMGoUXHoprFvndFVSkIKTiIiID6lQAf7zH/jxR8jIgFat4Omn4ehRpysTUHASERHxSZdeao0yx4yBZ5+Fiy+GlSudrkoUnERERHxUaKiFphUrICQE2rSxVgZHjjhdWfBScBIREfFxsbGwfDk88wy89hq0aAFLljhdVXBScBIREfEDpUrBo4/C6tVQsSJcdhmMGGHroMR7FJxERET8SEyMLRx/+WV44w1o1gy++87pqoKHgpMENHUOF5FAFBJi7QrWrYPoaLjqKhgyBFJTna4s8KlzuAQFdQ4XkUCVk2MzTw8/bJfwpkyBbt2cripwacZJRETEj5UoAffeax3HY2Kge3e4/XY4eNDpygKTgpOIiEgAqFMHvvkG3nkHPv/cQtSMGU5XFXgUnERERAKEy2XHtWzYAK1bQ9++MGAAHDjgdGWBQ8FJREQkwERFwRdfwPvv2yxUkyZ2gLCcOwUnERGRAORywc0329qnVq2gd28YOBAOHXK6Mv+m4CQiIhLAoqLgyy/h3Xdt7VOTJjB7ttNV+S8FJxERkQDnctlOu/XroWlT23l3992QkuJ0Zf5HwUlERCRI1Kpls01TpsBHH1mImjfP6ar8i4KTiIhIEHG5YNAgW/vUsCFcfbX1gUpLc7oy/6DgJAFNR66IiJxcnTowdy7Ex8PUqXbm3YIFTlfl+3TkigQFHbkiInJq27ZZ/6fFi2HYMBg/HsqVc7oq36QZJxERkSB3/vk22/Svf8Fbb0Hz5vDDD05X5ZsUnERERIQSJeCBByAxEapXh8svhwcfhCNHnK7Mtyg4iYiISJ5GjeyS3Ysv2vqnVq1g1Sqnq/IdCk4iIiJSSEgIjB4NP/8MpUtDmzbw/POQleV0Zc5TcBIREZGTatIEfvoJxoyBJ56A9u1h82anq3KWgpOIiIicUunS8Nxztlj8jz+gRQuYPBmCdU++gpOIiIic1qWXwurVcNttcN99dmzL3r1OV+V9Ck4iIiJSJOXL22zTrFmwZo0d2fLxx05X5V0KTiIiInJGunWDdeugUye48UYYMAAOHXK6Ku9QcJKApiNXREQ8o3JlmD4dEhLs4OCmTe0Il0CnI1ckKOjIFRERz9m9245smTcP7r8f/vlPKFvW6ao8QzNOIiIick5q1YI5c+A//4G334bYWFi+3OmqPEPBSURERM5ZiRI227R6NUREQNu28OSTcOyY05UVLwUnERERKTYXXABLlljDzOefh8suC6ymmQpOIiIiUqxKlrTgtHSp7baLjYW33gqMppkKTuK4zz77jC5dulClShVcLheJiYknPKdDhw64XK5Co3///g5UKyIiRRUXZwcE33QTDBoE110HBw44XdW5UXASx2VkZNCuXTteeOGFv33eoEGDSEpKyhtvvPGGlyoUEZGzVb48vPkmfPYZLF7s/20LSjpdgMitt94KwI4dO/72eWXLliUyMtILFYmISHG79lpo08baFnTuDCNGwPjxUKaM05WdGc04id9ISEigSpUqNG7cmNGjR5OWluZ0SSIicgaioqxZ5muv2dEtrVtbB3J/ouAkfuHmm2/mww8/ZOHChTz++ON8+umn9O3b95TPz8zMJDU1tdAQERHnlShhs00rVthi8bg4+Ne/ICfH6cqKRsFJvCohIYHy5cvnje+//75Iv27QoEF06tSJJk2a0L9/fz755BPmzZvHqlWrTvr88ePHExERkTeio6OL87chIiLnqGlTC09DhliQ6tYNkpKcrur0dOSKeFVaWhr79+/Pe1yzZk3CwsIAW+NUr149Vq9eTYsWLf72ddxuN6GhoUybNo0bb7zxhM9nZmaSmZmZ9zg1NZXo6GgduSIi4oO+/RYGDrRmmW+9BX36OF3RqWlxuHhVeHg44eHh5/w669ev59ixY9SoUeOknw8NDSU0NPSc30dERDyvc2db6zRokC0iHzTI1kGVK+d0ZSdScBLHHTx4kN9++429e/cCsHHjRgAiIyOJjIxk69atJCQk0L17d6pUqcKGDRt48MEHiY2NpV27dk6WLiIixaRKFWtZ8PbbMHw4LFwICQm2BsqXaI2TOG7mzJnExsbSo0cPAPr3709sbCyvv/46AKVLl2b+/Pl06dKFCy64gAceeIDOnTszb948QkJCnCxdRESKkcsFd99d+Ly755+H7GynK8unNU4SFFJTU4mIiNAaJxERP3HsGDz9NIwbZ+fdTZsGdeo4XZVmnERERMQHlSoFzz0HixbBzp3QogV88onTVSk4iYiIiA9r3x4SE6FTJ7jhBrjnHsjIcK4eBScRERHxaeedBx9/bGfeJSTAxRfDmjXO1KLgJCIiIj4vd+H4ypUQGmrHtfz739Z93JsUnERERMRvXHghLFsG995rbQt69oTff/fe+ys4SUCLj48nJiaGOF9rBCIiImetTBmYMAG+/hqWL4dmzWDePO+8t9oRSFBQOwIRkcCUlAS33Qbz58NDD8Gzz0Lp0p57P804iYiIiN+qUQPmzIF//hNefRXatYMtWzz3fgpOIiIi4tdKlLDZpiVL4NAhiI21hpkeeS/PvKyIiIiId8XF2XEtffva5bs77yz+XXc65FdEREQCRng4/N//QZcuNvvkchXv62txuAQFLQ4XEZHioEt1IiIiIkWk4CQiIiJSRApOIiIiIkWk4CQBTZ3DRUSkOGlxuAQFLQ4XEZHioBknERERkSLSjJMEBbfbTVpaGuHh4biKu6mHiIgEDQUnERERkSLSpToRERGRIlJwEhERESkiBScRERGRIlJwEhERESkiBScRERGRIlJwEhERESkiBScRERGRIvp/K75fSqw7magAAAAASUVORK5CYII=\n",
      "text/plain": [
       "Graphics object consisting of 1 graphics primitive"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E = EllipticCurve([-5, 10])\n",
    "E.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "occupational-cloud",
   "metadata": {},
   "source": [
    "Zahlenpaare $(x, y)$ welche die Kurvengleichung von $E$ erfüllen, nennt man Punkte der elliptischen Kurve. Deren Menge nennt man Punktmenge von $E$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "wound-gabriel",
   "metadata": {},
   "source": [
    "Die Besonderheit an elliptischen Kurven ergibt sich aus den Eigenschaften ihrer Punktmenge. \n",
    "Diese kann nicht nur geometrisch (als Kurve/Graph), sondern auch algebraisch aufgefasst werden. Die Punktmenge jeder elliptischen Kurve repräsentiert eine algebraische Gruppe $G$. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ranking-correspondence",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "casual-suggestion",
   "metadata": {},
   "source": [
    "Eine Gruppe besteht immer aus einer Menge von Objekten und aus einer zweistelligen Operation bezüglich _G_: $ \\ G = (M, *)$. Im Falle der elliptischen Kurve ist die Menge der Gruppe die Punktmenge der elliptischen Kurve _E_ und die Operation wird durch die sogenannte Punktaddition repräsentiert. Für die Gruppe _G_ müssen folgende Eigenschaften gelten _[1]_:\n",
    "1. Abgeschlossenheit: $ \\ a, b, c \\in M_G \\ ; \\ a * b = c$\n",
    "2. Assoziativität: $ \\ a, b, c \\in M_G \\ ; \\ (a*b)*c = a*(b*c)$\n",
    "3. Es existiert ein neutrales Element: $ \\ a, e \\in M_G ; \\ a * e = a$\n",
    "4. Zu jedem Element existiert eine Inverse: $ \\ a, e \\in M_G \\ ; \\ a * a^{-1} = e$\n",
    "5. Um zusätzlich als abelsche Gruppe bezeichnet zu werden muss die Operation kommutativ sein: $ \\ a, b \\in M_G \\ ; \\ a * b = b * a$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "utility-report",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hearing-blank",
   "metadata": {},
   "source": [
    "Die Gruppenoperation einer elliptschen Kurve wird als Punktaddition ($\\oplus$) bezeichnet.\n",
    "Diese kann vorzugsweise graphisch veranschaulicht werden.\n",
    "Dabei ist das Ergebnis der Gleichung: $A \\oplus B \\ ; \\ A, B \\in E$ der dritte Schnittpunkt der Geraden durch die Punkte $A$ und $B$ mit der Kurve $E$ _[3]_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "clinical-yukon",
   "metadata": {},
   "source": [
    "Mithilfe dieser Grundlage kann zusätzlich noch eine weitere Operation definiert werden:\n",
    "Die Multiplikation eines Skalars $k$ mit einem Punkt $A$ auf der elliptischen Kurve $E$.\n",
    "Dabei ist das Ergebnis der Gleichung $[k] A \\ ; \\ A \\in E$ der Schnittpunkt der Tangente von $A$ an $E$ mit der Kurve $E$ _[3]_.\n",
    "Es ist dabei darauf zu achten, dass die Skalarmultiplikation lediglich eine wiederholte Punktaddition notiert und direkt aus dieser hergeleitet werden kann"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "vanilla-japanese",
   "metadata": {},
   "source": [
    "Mithilfe einfacher Beweismittel kann gezeigt werden, dass die Gruppe $E(M_{Punktmenge}, \\oplus)$ die oben genannten Gruppengesetze erfüllt (siehe _[2]_)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "scientific-savannah",
   "metadata": {},
   "source": [
    "Elliptische Kurven sind in der modernen Mathematik unverzichtbar. So stellen elliptische Kurven zum Beispiel die Grundlage für den berühmten Beweis des Großen Fermatschen Satzes durch den britischen Mathematiker Andrew Wiles dar.\n",
    "Wie im Weiteren besprochen ist das größte Anwendungsgebiet elliptischer Kurven zweifelsfrei die Kryptographie, wobei heutzutage jeder internetfähige Rechner die oben genannten Berechnungen mehrere Milliarden mal am Tag durchführt"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "piano-revelation",
   "metadata": {},
   "source": [
    "## Elliptische Kurven über endlichen Feldern"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "royal-valve",
   "metadata": {},
   "source": [
    "Die in den oben gezeigten Abbildungen verwendeten elliptischen Kurven sind alle über den reelen Zahlen definiert. Die Punktmenge solcher elliptischer Kurven ist daher unendlich (sogar überabzählbar) groß. Für zahlentheoretische und kryptographische Anwendungen werden jedoch elliptische Kurven mit einer endlichen Menge an Punkten benötigt. Daher definiert man elliptische Kurven oftmals über endlichen Feldern. Die elliptische Kurve $E: y^2 = x^3 - 3x + 7$ über dem endlichen Feld $GF(13)$ sieht wie folgt aus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "improved-survey",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk4AAAGFCAYAAAALnnwfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAfDUlEQVR4nO3df3DU9Z3H8dcazPLjsguJByHjorGNB0tQqKyeQAVHZU4ZlOIvRJRK9abXKGCmFShSlJFEqeWcaVa40DlKjwvSGwGVw6lRMBGRMRBBjyoRySADZqKes98AZQnJ9/7IsRIS4BP4br7fZJ+PmZ3m+83m+3nrV+DZ737Z9dm2bQsAAADndYnbAwAAAHQVhBMAAIAhwgkAAMAQ4QQAAGCIcAIAADBEOAEAABginAAAAAwRTgAAAIY8F062bcuyLPG+nAAAwGs8F04NDQ0KBoNqaGhwexQAAIBWPBdOAAAAXtXhcKqsrNTEiROVk5Mjn8+nDRs2JL7X2NioOXPmaNiwYerTp49ycnL08MMP6/Dhw44ODQAA4IYOh9PRo0d17bXXqqSkpM33jh07purqai1YsEDV1dVat26dampqdOeddzoyLAAAgJt89kXche3z+bR+/XpNmjTprM+pqqrS9ddfrwMHDmjQoEHnPaZlWQoGg4rFYgoEAhc6GgB0S5s2SRUV0vXXS3ff7fY0QOrpkewFYrGYfD6f+vbtm+ylAKBbe/VV6Z57vt8uLZUee8y9eYBUlNSbw48fP665c+dq6tSpZ716FI/HZVlWqwcAoK033mi9vXGjO3MAqSxp4dTY2KgpU6aoublZL7/88lmfV1xcrGAwmHiEQqFkjQQAXVo43Hp7yBB35gBSWVLucWpsbNR9992n/fv3a/PmzcrKyjrrMeLxuOLxeGLbsiyFQiHucQKAMzQ1SfPmtdzjFIlIL74o9ezp9lRAanH8HqdT0fT5559ry5Yt54wmSfL7/fL7/U6PAQDdTlqatGSJ21MAqa3D4XTkyBHt27cvsV1bW6tdu3YpMzNTOTk5uueee1RdXa2NGzeqqalJdXV1kqTMzEylp6c7NzkAAEAn6/BLde+++65uvvnmNvunT5+uZ555Rrm5ue3+3JYtWzRu3LjzHp+3IwAAAF51Ufc4JQPhBAAAvIrPqgMAADBEOAEAABginAAAAAwRTgAAAIYIJwAAAEOEEwAAgCHCCQAAwBDhBAAAYMgz4RSNRhUOhxWJRNweBQAAoF28czgAAIAhz1xxAgAA8DrCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhggnAAAAQ4QTAACAIcIJQLf3v/8rvfaatHu325MA6OoIJwDd2ldfScOHS5MmSSNGSH/4g9sTAejKCCcA3dqaNdLBgy1f27b04ovuzgOga/NMOEWjUYXDYUUiEbdHAdCN9OvXertvX3fmANA9+Gzbtt0e4nSWZSkYDCoWiykQCLg9DoAu7uRJ6aGHpD//WQqFpA0bWl66A4ALQTgBSAlNTVJamttTAOjqPPNSHQAkE9EEwAmEEwAAgCHCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhggnAAAAQ4QTAACAIcIJAADAkGfCKRqNKhwOKxKJuD0KAABAu/iQXwAAAEOeueIEAADgdYQTAACAIcIJAADAEOEEAABgiHACAAAwRDgBAAAYIpwAAAAMEU4AAACGOhxOlZWVmjhxonJycuTz+bRhw4ZW37dtW88884xycnLUq1cvjRs3Tnv27HFsYAAAALd0OJyOHj2qa6+9ViUlJe1+f8mSJVq6dKlKSkpUVVWl7Oxs3XbbbWpoaLjoYZ3Q1CTV1bX8LwAA6L6+/VY6etTZY3Y4nG6//XY999xzmjx5cpvv2batl156SfPnz9fkyZOVn5+vVatW6dixYyorK3Nk4Ivx1VfSsGHSwIHS1VdLtbVuTwQAAJLhX/5FuuwyqV8/6T/+w7njOnqPU21trerq6jR+/PjEPr/fr7Fjx2rbtm3t/kw8HpdlWa0eyVJUJH36acvX+/dLCxcmbSkAAOCS99+Xli9v+bqxUfrnf3bulSZHw6murk6SNGDAgFb7BwwYkPjemYqLixUMBhOPUCjk5EitHD/eejseT9pSAADAJWf++d7YKDU3O3PspPytOp/P12rbtu02+06ZN2+eYrFY4nHw4MFkjCRJKiyU/v7vW77u10966qmkLQUAAFxy003SP/3T99uLFkmXXurMsXs4c5gW2dnZklquPA0cODCxv76+vs1VqFP8fr/8fr+TY5zVkCHSZ5+1PPLyvo8oAADQffToIW3cKO3cKQUC0uDBzh3b0StOubm5ys7OVnl5eWLfiRMnVFFRoVGjRjm51AXLzJRGjSKaAADoztLSpOuvdzaapAu44nTkyBHt27cvsV1bW6tdu3YpMzNTgwYN0uzZs1VUVKS8vDzl5eWpqKhIvXv31tSpUx0dHAAAoLN1OJx27Nihm2++ObFdWFgoSZo+fbr++Mc/6qmnntLf/vY3/eIXv9B3332nG264QW+99ZYyMjKcmxoAAMAFPtu2bbeHOJ1lWQoGg4rFYgoEAm6PAwAAkMBn1QEAABginAAAAAwRTgAAAIYIJwAAAEOEEwAAgCHCCQAAwBDhBAAAYMgz4RSNRhUOhxWJRNweBQAAoF28ASYAAIAhz1xxAgAA8DrCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhggnAAAAQ4QTAACAIcIJAADAEOEEAABgiHACAAAw5JlwikajCofDikQibo8CAADQLp9t27bbQ5zOsiwFg0HFYjEFAgG3xwEAAEjwzBUnAAAAryOcAAAADBFOAAAAhggnAAAAQ4QTAACAIcIJAADAEOEEAABgiHACAAAwRDgBAAAYIpwAAAAMEU4AAACGCCcAAABDngmnaDSqcDisSCTi9igAAADt8tm2bbs9xOksy1IwGFQsFlMgEHB7HAAAgATPXHECAADwOsIJAADAEOEEAABgiHACAAAwRDgBAAAYIpwAAAAMEU4AAACGCCcAAABDjofTyZMn9fTTTys3N1e9evXSVVddpUWLFqm5udnppQAAADpVD6cP+MILL2j58uVatWqVhg4dqh07duiRRx5RMBjUrFmznF4OAACg0zgeTh988IHuuusuTZgwQZJ05ZVXas2aNdqxY4fTS6W0xkapuFj67DPprruk++93eyIAALo/x1+qGzNmjN555x3V1NRIknbv3q2tW7fqjjvucHqplPbLX0oLF0pr1khTpkibNrk9EQAA3Z/jV5zmzJmjWCymwYMHKy0tTU1NTVq8eLEeeOCBdp8fj8cVj8cT25ZlOT1St/T++623t26VaFMAAJLL8StOa9eu1erVq1VWVqbq6mqtWrVKL774olatWtXu84uLixUMBhOPUCjk9Ejd0j/+Y+vtUaPcmQMAgFTis23bdvKAoVBIc+fOVUFBQWLfc889p9WrV+uzzz5r8/z2rjiFQiHFYjEFAgEnR+tW4nFp8WLp009b7nGaNs3tiQAA6P4cf6nu2LFjuuSS1hey0tLSzvp2BH6/X36/3+kxuj2/X1q0yO0pAABILY6H08SJE7V48WINGjRIQ4cO1UcffaSlS5dqxowZTi8FAADQqRx/qa6hoUELFizQ+vXrVV9fr5ycHD3wwAP6zW9+o/T09PP+vGVZCgaDvFQHAAA8x/FwuliEEwAA8Co+qw4AAMAQ4QQAAGCIcAIAADBEOAEAABginAAAAAwRTgAAAIYIJwAAAEOEEwAAgCHPhFM0GlU4HFYkEnF7FAAAgHbxzuEAAACGPHPFCQAAwOsIJwAAAEOEEwAAgCHCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhnq4PQAAb/rmG+m//ksKBKQpU6S0NLcnAgD3EU4A2ojFpBtvlPbta9netEn6z/90dyYA8AJeqgPQxvvvfx9NkrRmjXTihHvzAIBXeCacotGowuGwIpGI26MAKe/yyyWf7/vtAQOk9HT35gEAr/DZtm27PcTpLMtSMBhULBZTIBBwexwgZS1fLj3/vBQMSqWl0g03uD0RALiPcAIAADDkmZfqAAAAvI5wAgAAMEQ4AQAAGCKcAAAADBFOAAAAhggnAAAAQ4QTAACAIcIJAADAEOEEAABgiHACAAAwRDgBAAAY8kw4RaNRhcNhRSIRt0cBAABoFx/yCwAAYMgzV5wAAAC8jnACAAAwRDgBAAAYIpwAAAAMEU4AAACGCCcAAABDhBMAAIAhwgkAAMBQUsLp0KFDmjZtmrKystS7d28NHz5cO3fuTMZSAAAAnaaH0wf87rvvNHr0aN18881688031b9/f33xxRfq27ev00sBSKLmZmn3bikQkH7wA7enAQBvcDycXnjhBYVCIa1cuTKx78orr3R6GQBJ1NQk3XmntGmT5PNJS5ZIv/yl21MBgPscf6nu9ddf18iRI3Xvvfeqf//+GjFihFasWHHW58fjcVmW1eoBwF1btrREkyTZtjRvnnTypLszAYAXOB5O+/fv17Jly5SXl6e//OUv+vnPf66ZM2fqT3/6U7vPLy4uVjAYTDxCoZDTIwHooEsvbb3do4d0CX+VBADks23bdvKA6enpGjlypLZt25bYN3PmTFVVVemDDz5o8/x4PK54PJ7YtixLoVBIsVhMgUDAydEAdMCMGdLKlS0RtWKFNH262xMBgPsc//+QAwcOVDgcbrVvyJAh+vLLL9t9vt/vVyAQaPUA4L5//3fpq6+kr78mmgDgFMdvDh89erT27t3bal9NTY2uuOIKp5cCkGTZ2W5PAADe4vgVpyeffFLbt29XUVGR9u3bp7KyMpWWlqqgoMDppQAAADqV4/c4SdLGjRs1b948ff7558rNzVVhYaEee+wxo5+1LEvBYJB7nAAAgOckJZwuBuEEAAC8ir9gDAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhggnAAAAQ4QTAACAIc+EUzQaVTgcViQScXsUAACAdvEGmAAAAIY8c8UJAADA6wgnAAAAQ4QTAACAIcIJAADAEOEEAABgiHACAAAwRDgBAAAYIpwAAAAMEU4AAACGCKcuzlvv+w4AQPdGOHVR+/ZJ+flSerp0993SiRNuTwQAQPdHOHVRM2dKe/ZIJ09K69ZJy5a5PREAAN2fZ8IpGo0qHA4rEom4PUqX8O23594GAADO89m2t+6SsSxLwWBQsVhMgUDA7XE8q6xMeughqblZysqStm+XfvhDt6cCAKB76+H2ALgwU6dKQ4dKNTXS6NFSTo7bEwEA0P1xxQkAAMCQZ+5xAgAA8DrCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhggnAAAAQ4QTAACAIcIJAADAkGfCKRqNKhwOKxKJuD0KAABAu/isOgAAAEOeueIEAADgdYQTAACAIcIJAADAEOEEAABgiHACAAAwRDgBAAAYIpwAAAAMEU4AAACGkh5OxcXF8vl8mj17drKXAgAASKqkhlNVVZVKS0t1zTXXJHMZAACATpG0cDpy5IgefPBBrVixQv369UvWMgAAAJ0maeFUUFCgCRMm6NZbbz3n8+LxuCzLavUAAADwoh7JOOgrr7yi6upqVVVVnfe5xcXFevbZZ5MxBgAAgKMcv+J08OBBzZo1S6tXr1bPnj3P+/x58+YpFoslHgcPHnR6JAAAAEf4bNu2nTzghg0b9JOf/ERpaWmJfU1NTfL5fLrkkksUj8dbfe9MlmUpGAwqFospEAg4ORoAAMBFcfylultuuUWffPJJq32PPPKIBg8erDlz5pwzmgAAALzM8XDKyMhQfn5+q319+vRRVlZWm/0AAABdCe8cDgAAYMjxe5wuFvc4AQAAr+KKEwAAgCHCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhggnAAAAQ54Jp2g0qnA4rEgk4vYoAAAA7eKdwwEAAAx55ooTAACA1xFOAAAAhggnAAAAQ4QTAACAIcIJAADAEOEEAABgiHACAAAwRDgBAAAYIpwAAAAM9XB7gM72xhtSRYV0ww3Svfe6PQ0AAEiGL76Q/vAHKRCQZs6U+vRx5rgpFU5//rN0//3fb5eWSo895t48AADAeV9/LY0aJdXXt2y//bb0zjvOHDulXqrbuLH19n//tztzAACA5Nmx4/tokqTNm6Xjx505tmfCKRqNKhwOKxKJJG2N/PxzbwMAgK4vL09KT/9++wc/kHr2dObYPtu2bWcO5QzLshQMBhWLxRQIBBw9dlOTNH++VFkpXX+9tGRJ63+xAACge9i4seXP+UBAWrpUuvpqZ46bUuEEAABwMTzzUh0AAIDXEU4AAACGCCcAAABDhBMAAIAhwgkAAMAQ4QQAAGCIcAIAADBEOAEAABginAAAAAwRTgAAAIYIJwAAAEOeCadoNKpwOKxIJOL2KAAAAO3iQ34BAAAMeeaKEwAAgNcRTgAAAIYIJwAAAEOEEwAAgCHCCQAAwBDhBAAAYIhwAgAAMOR4OBUXFysSiSgjI0P9+/fXpEmTtHfvXqeXAQAA6HSOh1NFRYUKCgq0fft2lZeX6+TJkxo/fryOHj3q9FIAAACdKunvHP7111+rf//+qqio0E033XTe5/PO4QCc9s03UmWldOWV0o9+5PY0ALqypN/jFIvFJEmZmZnJXgoA2jh8WBo+XLr7bmnkSOnf/s3tiQB0ZUkNJ9u2VVhYqDFjxig/P7/d58TjcVmW1eoBAE555RXp0KGWr21b+td/dXceAF1bUsPp8ccf18cff6w1a9ac9TnFxcUKBoOJRygUSuZIAFJMv37n3gaAjkjaPU5PPPGENmzYoMrKSuXm5p71efF4XPF4PLFtWZZCoRD3OAFwRFOTNH16y5WnK66Q1q+XrrnG7akAdFWOh5Nt23riiSe0fv16vfvuu8rLy+vQz3NzOIBksG3J53N7CgBdXQ+nD1hQUKCysjK99tprysjIUF1dnSQpGAyqV69eTi8HAEaIJgBOcPyKk+8svzutXLlSP/3pT8/781xxAgAAXuX4Fackvy0UAACAa/isOgAAAEOEEwAAgCHCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGCKcAAAADBFOAAAAhjwTTtFoVOFwWJFIxO1RAAAA2uX4R65cLD5yBQAAeJVnrjgBAAB4HeEEAABgiHACAAAwRDgBAAAYIpwAAAAMEU4AAACGCCcAAABDhBMAAIAhwgkAAMAQ4QQAXUhTk3TokNTY6PYkQGoinACgizh8WMrPly6/XMrLk/btc3siIPUQTgDQRTz/vPTZZy1fHzggLVzo7jxAKvJMOEWjUYXDYUUiEbdHAQBPOnHi3NsAks9n27bt9hCnsyxLwWBQsVhMgUDA7XEAwDNqaqSxY6W6OqlfP+ntt6Uf/cjtqYDU0sPtAQAAZq6+Wvr0U2nvXumHP5SystyeCEg9hBMAdCF9+0o33OD2FEDq8sw9TgAAAF5HOAEAABginAAAAAwRTgAAAIYIJwAAAEOEEwAAgCHCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGPJMOEWjUYXDYUUiEbdHAQAAaJfPtm3b7SFOZ1mWgsGgYrGYAoGA2+MAAAAkeOaKEwAAgNcRTgAAAIYIJwAAAEOEEwAAgCHCCQAAwBDhBAAAYIhwAgAAMEQ4AQAAGEpaOL388svKzc1Vz549dd111+m9995L1lIAAACdIinhtHbtWs2ePVvz58/XRx99pB//+Me6/fbb9eWXXyZjOQAAgE6RlHBaunSpfvazn+nRRx/VkCFD9NJLLykUCmnZsmXJWA7wjLfeksJh6R/+QVq/3u1pAABO6+H0AU+cOKGdO3dq7ty5rfaPHz9e27Zta/P8eDyueDye2LYs64LWtW1bDQ0NF/SzgBMaGqTJk6WjR1u2p0yR/ud/pAED3J0LAGAmIyNDPp/vnM9xPJy++eYbNTU1acAZf1oMGDBAdXV1bZ5fXFysZ5999qLXbWhoUDAYvOjjAE45cUK6+mq3pwAAmIrFYgoEAud8juPhdMqZxWbbdrsVN2/ePBUWFia2LctSKBTq8HoZGRmKxWJGzz21xsGDB8/7L+hiRCIRVVVVJe34nbVGZ6zTWedESt4/S3OzNHGitHWrJEU0fHiVysul9HTHl5LUOee+O/1a6ax1OC/eW6Mz1ukOv4d1xzU6el4yMjLO+xzHw+myyy5TWlpam6tL9fX1ba5CSZLf75ff77/odX0+X4f/Yw0EAkn9DzwtLS3pv4A6Y43OXCfZ50RK7j9Lebm0erW0YEGa3nsvoL/7u6QsI6nzzonUPX6tdNY6nBfvrdGZ63T138O62xqnOHleHL85PD09Xdddd53Ky8tb7S8vL9eoUaOcXs7TCgoKusUanblOZ0jmP0vPntKjj0pPP12Q1GiSOCdeXYfz4r01OnOdztBdzktXPSc+27Ztpw+6du1aPfTQQ1q+fLluvPFGlZaWasWKFdqzZ4+uuOKKc/6sZVkKBoNGrzNeqM5YAx3DOfEmzos3cV68h3PiTck4L0m5x+n+++/Xt99+q0WLFumrr75Sfn6+Nm3adN5o6ix+v18LFy505CVCOINz4k2cF2/ivHgP58SbknFeknLF6WJQ7QAAwKv4rDoAAABDnrvidOqNLE3ehAoAAKAzeS6cAAAAvIqX6gAAAAylTDgVFxcrEokoIyND/fv316RJk7R37163x8JpiouL5fP5NHv2bLdHSXmHDh3StGnTlJWVpd69e2v48OHauXOn22OltJMnT+rpp59Wbm6uevXqpauuukqLFi1Sc3Oz26OllMrKSk2cOFE5OTny+XzasGFDq+/btq1nnnlGOTk56tWrl8aNG6c9e/a4NG3qONd5aWxs1Jw5czRs2DD16dNHOTk5evjhh3X48OELWitlwqmiokIFBQXavn27ysvLdfLkSY0fP15HT30iK1xVVVWl0tJSXXPNNW6PkvK+++47jR49WpdeeqnefPNN/fWvf9Xvfvc79e3b1+3RUtoLL7yg5cuXq6SkRJ9++qmWLFmi3/72t/r973/v9mgp5ejRo7r22mtVUlLS7veXLFmipUuXqqSkRFVVVcrOztZtt93Gh9An2bnOy7Fjx1RdXa0FCxaourpa69atU01Nje68884LW8xOUfX19bYku6Kiwu1RUl5DQ4Odl5dnl5eX22PHjrVnzZrl9kgpbc6cOfaYMWPcHgNnmDBhgj1jxoxW+yZPnmxPmzbNpYkgyV6/fn1iu7m52c7Ozraff/75xL7jx4/bwWDQXr58uRsjpqQzz0t7PvzwQ1uSfeDAgQ4fP2WuOJ3p1AcCZ2ZmujwJCgoKNGHCBN16661ujwJJr7/+ukaOHKl7771X/fv314gRI7RixQq3x0p5Y8aM0TvvvKOamhpJ0u7du7V161bdcccdLk+GU2pra1VXV6fx48cn9vn9fo0dO1bbtm1zcTKcKRaLyefzXdCV9KS8c7jX2batwsJCjRkzRvn5+W6Pk9JeeeUVVVdXd8qno8PM/v37tWzZMhUWFurXv/61PvzwQ82cOVN+v18PP/yw2+OlrDlz5igWi2nw4MFKS0tTU1OTFi9erAceeMDt0fD/Tn24/ZkfaD9gwAAdOHDAjZHQjuPHj2vu3LmaOnXqBb3RdkqG0+OPP66PP/5YW7dudXuUlHbw4EHNmjVLb731lnr27On2OPh/zc3NGjlypIqKiiRJI0aM0J49e7Rs2TLCyUVr167V6tWrVVZWpqFDh2rXrl2aPXu2cnJyNH36dLfHw2nOfA9C27Z5X0KPaGxs1JQpU9Tc3KyXX375go6RcuH0xBNP6PXXX1dlZaUuv/xyt8dJaTt37lR9fb2uu+66xL6mpiZVVlaqpKRE8XhcaWlpLk6YmgYOHKhwONxq35AhQ/Tqq6+6NBEk6Ve/+pXmzp2rKVOmSJKGDRumAwcOqLi4mHDyiOzsbEktV54GDhyY2F9fX9/mKhQ6X2Njo+677z7V1tZq8+bNF/yxbilzj5Nt23r88ce1bt06bd68Wbm5uW6PlPJuueUWffLJJ9q1a1fiMXLkSD344IPatWsX0eSS0aNHt3mrjpqaGs98SHeqOnbsmC65pPVv2WlpabwdgYfk5uYqOztb5eXliX0nTpxQRUWFRo0a5eJkOBVNn3/+ud5++21lZWVd8LFS5opTQUGBysrK9NprrykjIyPxWnQwGFSvXr1cni41ZWRktLnHrE+fPsrKyuLeMxc9+eSTGjVqlIqKinTffffpww8/VGlpqUpLS90eLaVNnDhRixcv1qBBgzR06FB99NFHWrp0qWbMmOH2aCnlyJEj2rdvX2K7trZWu3btUmZmpgYNGqTZs2erqKhIeXl5ysvLU1FRkXr37q2pU6e6OHX3d67zkpOTo3vuuUfV1dXauHGjmpqaEg2QmZmp9PT0ji12QX/XrwuS1O5j5cqVbo+G0/B2BN7wxhtv2Pn5+bbf77cHDx5sl5aWuj1SyrMsy541a5Y9aNAgu2fPnvZVV11lz58/347H426PllK2bNnS7p8l06dPt2275S0JFi5caGdnZ9t+v9++6aab7E8++cTdoVPAuc5LbW3tWRtgy5YtHV6Lz6oDAAAwlDL3OAEAAFwswgkAAMAQ4QQAAGCIcAIAADBEOAEAABginAAAAAwRTgAAAIYIJwAAAEOEEwAAgCHCCQAAwBDhBAAAYIhwAgAAMPR/6ZpMYj+to8MAAAAASUVORK5CYII=\n",
      "text/plain": [
       "Graphics object consisting of 1 graphics primitive"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E = EllipticCurve(GF(13), [-3, 7])\n",
    "E.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "european-phase",
   "metadata": {},
   "source": [
    "Wenn im Folgenden über elliptische Kurven gesprochen wird, bezieht sich dies stets auf elliptische Kurven über endlichen Feldern"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "young-underground",
   "metadata": {},
   "source": [
    "## Der Generator"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "overall-cleanup",
   "metadata": {},
   "source": [
    "Auf jeder elliptischen Kurve $E$ existiert zudem ein Punkt $g \\in E$, der mithilfe der Skalarmultiplikation jeden anderen Punkt auf der Kurve \"generiert\". Dieser Punkt wird Generator oder Generatorpunkt genannt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "english-silly",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generator: (6 : 4 : 1)\n",
      "Alle Punkte auf E: [(0 : 1 : 0), (0 : 1 : 1), (0 : 6 : 1), (1 : 0 : 1), (3 : 1 : 1), (3 : 6 : 1), (4 : 1 : 1), (4 : 6 : 1), (5 : 2 : 1), (5 : 5 : 1), (6 : 3 : 1), (6 : 4 : 1)]\n",
      "Die Sklaramultiplikation auf den Generator mit unterschiedlichen Skalaren: \n",
      "[0](6 : 4 : 1) generiert den Punkt (0 : 1 : 0)\n",
      "[1](6 : 4 : 1) generiert den Punkt (6 : 4 : 1)\n",
      "[2](6 : 4 : 1) generiert den Punkt (3 : 6 : 1)\n",
      "[3](6 : 4 : 1) generiert den Punkt (0 : 6 : 1)\n",
      "[4](6 : 4 : 1) generiert den Punkt (5 : 5 : 1)\n",
      "[5](6 : 4 : 1) generiert den Punkt (4 : 1 : 1)\n",
      "[6](6 : 4 : 1) generiert den Punkt (1 : 0 : 1)\n",
      "[7](6 : 4 : 1) generiert den Punkt (4 : 6 : 1)\n",
      "[8](6 : 4 : 1) generiert den Punkt (5 : 2 : 1)\n",
      "[9](6 : 4 : 1) generiert den Punkt (0 : 1 : 1)\n",
      "[10](6 : 4 : 1) generiert den Punkt (3 : 1 : 1)\n",
      "[11](6 : 4 : 1) generiert den Punkt (6 : 3 : 1)\n"
     ]
    }
   ],
   "source": [
    "E = EllipticCurve(GF(7), [5, 1])\n",
    "generator_point = E.gens()[0]\n",
    "\n",
    "print(\"Generator: \" + str(generator_point))\n",
    "\n",
    "all_points_on_E = [point for point in E]\n",
    "print(\"Alle Punkte auf E: \" + str(all_points_on_E))\n",
    "\n",
    "print(\"Die Sklaramultiplikation auf den Generator mit unterschiedlichen Skalaren: \")\n",
    "for i in range(E.order()):\n",
    "    print(\"[\"+str(i)+\"]\"+str(generator_point) + \" generiert den Punkt \" + str(i*generator_point))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "geographic-lewis",
   "metadata": {},
   "source": [
    "## Elliptische Kurven in der asymetrischen Kryptographie"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "maritime-insulin",
   "metadata": {},
   "source": [
    "Elliptische Kurven und deren Eigenschaften werden exzessiv für kryptographische Anwendungen benutzt. So basiert der asymetrische Teil aller herkömmlichen TLS-Verschlüsselungen auf elliptschen Kurven _[4]_. Auch WhatsApp, Facebook, SSH und Giropay verwenden beispielsweise elliptische Kurven als Schlüsselverteilungsalgorithmus. Der Ablauf ist dabei wie folgt:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "moving-center",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "narrow-governor",
   "metadata": {},
   "source": [
    "Zunächst einigen sich Alice und Bob auf eine elliptische Kurve $E$ und deren Generatorpunkt $g$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "suffering-juice",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(6 : 4 : 1)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAkwAAAGFCAYAAAAPa6wiAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8li6FKAAAYdElEQVR4nO3dfYxVd50/8PcIdFQcpoKwBRmQ1EY6BdquHRWo2ier6HZbXR/qU/FhTVhH+kCMDe4m1qhMjXET3bJjwQSLphKTLn2wS2l1C60aFOp2rbRRKo1QQ9UamUtJ9prS+/tjfkXZ2n65M3fmzty+XsnJzLmc8z2fexjgzfmeez5ttVqtFgAAntULml0AAMBYJzABABQITAAABQITAECBwAQAUCAwAQAUCEwAAAUCEwBAwagHplqtlkqlEs/LBADGi1EPTIcOHUpnZ2cOHTo02ocGABgSU3IAAAV1B6bf/OY3+cAHPpBp06blxS9+cc4444zcd999I1EbAMCYMLGejf/4xz9m6dKlOffcc7Nly5bMmDEjv/rVr3LiiSeOVH0AAE1XV2D64he/mK6urmzYsOHoa694xSuOe///+q/k1lvrOSLwfPb448m//3tSqyW9vcnLXtbsilrTQw8l3/xmMn364Hk+4YRmVwRjT1utjo+rdXd3581vfnMeffTRbN++PS9/+cvz8Y9/PB/72MeK+951V/KWtyRPPVVJ0pnPfW4g//IvU4ZTO9DC/vSn5G//Ntm9e3D91FOT//7vpL29uXW1mn37ktNPTw4eHFx/17uS73ynuTXBWFTXPUx79+5Nf39/TjnllGzdujUrVqzI5Zdfno0bNz7rPtVqNZVKJf/xH5X/H5YqSZItW4ZVN9Di9u79c1hKBq+C7N3bvHpa1b33/jksJclttzWvFhjL6pqSe+qpp3LWWWdlzZo1SZIzzzwzu3fvTn9/fy677LK/uk9fX18++9nPPuP1+fOHUC3wvDFrVnLiiX/+x7yzc/A1Gmv+/OQFL0ieempwvbu7ufXAWFXXFaaZM2em+//8aTr11FOzb9++Z91n9erVGRgYyMGDA7n66oGcccb+JMnnPjeEaoHnjSlTkttvT845J3njGwe/7+xsdlWt59WvTjZuTBYvTv7+75Obbmp2RTA21XUP0/ve977s378/995779HXrrrqqvz4xz/Oj370o+Mao1KppLOzMwMDA5kyxT1MAMDYV9cVpquuuio7duzImjVr8vDDD+fGG2/MunXr0tvbO1L1AQA0XV1XmJLku9/9blavXp09e/Zk3rx5WbVq1XF9Su5prjABAONN3YFpuAQmAGC80UsOAKBAYAIAKBCYAAAKBCYAgAKBCQCgYNQC09q1a9Pd3Z2enp7ROiQAQEN4rAAAQIEpOQCAAoEJAKBAYAIAKBCYAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACrVEAAAq0RgEAKDAlBwBQIDABABQITAAABQITAECBwAQAUCAwAQAUCEwAAAUCEwBAgcAEAFCgNQoAQIHWKAAABabkAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACgQkAoEBgAgAoEJgAAAoEJgCAAr3kAAAK9JIDACgwJQcAUCAwAQAUCEwAAAUCEwBAgcAEAFBQV2C65ppr0tbWdsxy0kknjVRtAABjwsR6dzjttNPyve997+j6hAkTGloQALSiWi357W+TadOSSZOaXQ31qntKbuLEiTnppJOOLtOnTx+JugCgZRw8mLzmNcnMmcncuckDDzS7IupVd2Das2dPZs2alXnz5uXSSy/N3r17n3P7arWaSqVyzAIAzydf+Uqya9fg9wcOJFdf3dx6qF9dgem1r31tNm7cmK1bt2b9+vV57LHHsmTJkvzhD3941n36+vrS2dl5dOnq6hp20QAwnlSrx67/7/82pw6GblitUQ4fPpyTTz45n/rUp7Jq1aq/uk21Wk31L35SKpVKurq6tEYB4Hlj//5k6dLBr5MnJ7fdlpx7brOroh513/T9lyZPnpyFCxdmz549z7pNe3t72tvbh3MYABjXurqSn/98cJk3b/BeJsaXYT2HqVqt5qGHHspMv/MA8JymTEmWLBGWxqu6AtMnP/nJbN++PY888kh+/OMf553vfGcqlUqWL18+UvUBADRdXVNyjz76aN773vfm8ccfz/Tp0/O6170uO3bsyNy5c0eqPgCAphvWTd9DUalU0tnZ6aZvAGDc0EsOAKBAYAIAKBCYAAAKBCYAgIJRC0xr165Nd3d3enp6RuuQAAAN4VNyAAAFpuQAAAoEJgCAAoEJAKBAYAIAKBCYAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACveQAAAr0kgMAKDAlBwBQIDABABQITAAABQITAECBwAQAUCAwAQAUCEwAAAUCEwBAgcAEAFCgNQoAQIHWKAAABabkAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACgQkAoEBgAgAoEJgAAAq0RgEAKNAaBQCgwJQcAECBwAQAUCAwAQAUCEwAAAUCEwBAwbACU19fX9ra2nLllVc2qh4AgDFnyIFp586dWbduXRYtWtTIegAAxpwhBaYnnngi73//+7N+/fq89KUvbXRNAAB1O3Ikufba5H3vS264obFjDykw9fb25m1ve1suuOCCxlYDADBEn/lMsnp18u1vJx/6UPKd7zRu7In17rBp06b89Kc/zc6dO49r+2q1mmq1enS9UqnUe0gAgKIf/OCZ6+9+d2PGrusK0/79+3PFFVfkW9/6Vl74whce1z59fX3p7Ow8unR1dQ2pUACA57J48XOvD0ddveRuvvnmvP3tb8+ECROOvnbkyJG0tbXlBS94QarV6jG/lvz1K0xdXV16yQEADfXkk4P3MP3P/yRvfnPyj//YuLHrCkyHDh3Kr3/962Ne+/CHP5z58+fn6quvzoIFC4pjaL4LAIw3dd3D1NHR8YxQNHny5EybNu24whIAwHjkSd8AAAV1Tck1gik5AGC8cYUJAKBAYAIAKBCYAAAKBCYAgAKBCQCgYNQC09q1a9Pd3Z2enp7ROiQAQEN4rAAAQIEpOQCAAoEJAKBAYAIAKBCYAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACrVEAAAq0RgEAKDAlBwBQIDABABQITAAABQITAECBwAQAUCAwAQAUCEwAAAUCEwBAgcAEAFCgNQoAQIHWKAAABabkAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACgQkAoEBgAgAoEJgAAAoEJgCAAr3kAAAK9JIDACgwJQcAUCAwAQAUCEwAAAUCEwBAgcAEAFBQV2Dq7+/PokWLMmXKlEyZMiWLFy/Oli1bRqo2AIAxoa7ANHv27Fx77bXZtWtXdu3alfPOOy8XX3xxdu/ePVL1AQAct9//Ptm5Mzl0qLHjDvs5TFOnTs2XvvSlfPSjHz2u7T2HCQAYCT/8YfLWtyaVSjJnTnLvvYNfG2HI9zAdOXIkmzZtyuHDh7N48eJn3a5araZSqRyzAAA02uc+NxiWkmTfvuTf/q1xY9cdmB544IG85CUvSXt7e1asWJHNmzenu7v7Wbfv6+tLZ2fn0aWrq2tYBQMA/DWTJh27fsIJjRu77im5P/3pT9m3b18OHjyYm266KV//+tezffv2Zw1N1Wo11Wr16HqlUklXV5cpOQCgoX7+8+TCC5MDB5JFi5Lvfz952csaM/aw72G64IILcvLJJ+f6668/ru3dwwQAjJRqdfDG75kzkwkTGjfuxOEOUKvVjrmCBADQLO3tyezZjR+3rsD06U9/OsuWLUtXV1cOHTqUTZs2Zdu2bbnjjjsaXxkAwBhRV2D67W9/mw9+8IM5cOBAOjs7s2jRotxxxx1505veNFL1AQA03bDvYaqXe5gAgPFGLzkAgAKBCQCgQGACACgQmAAACkYtMK1duzbd3d3p6ekZrUMCADSET8kBABSYkgMAKBCYAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACgQkAoEBgAgAoEJgAAAr0kgMAKNBLDgCgwJQcAECBwAQAUCAwAQAUCEwAAAUCEwBAgcAEAFAgMAEAFAhMAAAFAhMAQIHWKAAABVqjAAAUmJIDACgQmAAACgQmAIACgQkAoEBgAgAoEJgAAAoEJgCAAoEJAKBAYAIAKNAaBQCgQGsUAIACU3IAAAUCEwBAgcAEAFAgMAEAFAhMAAAFdQWmvr6+9PT0pKOjIzNmzMgll1ySX/ziFyNVGwDAmFBXYNq+fXt6e3uzY8eO3HXXXXnyySdz4YUX5vDhwyNVHwBA0w3rOUy///3vM2PGjGzfvj1veMMbjmsfz2EC4PlozZrkP/8zWbAg+fKXk8mTm10R9Zg4nJ0HBgaSJFOnTn3WbarVaqrV6tH1SqUynEMCwLizYUPyz/88+P0Pfzj49Wtfa1491G/IN33XarWsWrUqZ599dhYsWPCs2/X19aWzs/Po0tXVNdRDAsC49POfP/c6Y9+QA9MnPvGJ/OxnP8u3v/3t59xu9erVGRgYOLrs379/qIcEgHHpLW9J2tr+vP7WtzavFoZmSFNyK1euzK233pp77rkns2fPfs5t29vb097ePqTiAKAVvOlNydatyR13JAsXJh/6ULMrol513fRdq9WycuXKbN68Odu2bcspp5xS9wHd9A0AjDd1XWHq7e3NjTfemFtuuSUdHR157LHHkiSdnZ150YteNCIFAgA0W11XmNr+cgL2L2zYsCEfOs7ri64wAQDjTV1XmIbxyCYAgHFLLzkAgAKBCQCgQGACACgQmAAACgQmAICCUQtMa9euTXd3d3p6ekbrkAAADVHXc5gawXOYAIDxxpQcAECBwAQAUCAwAQAUCEwAAAUCEwBAgcAEAFAgMAEAFAhMAAAFAhMAQIHWKAAABVqjAAAUmJIDACgQmAAACgQmAIACgQkAoEBgAgAoEJgAAAoEJgCAAoEJAKBAYAIAKNAaBQCgQGsUAIACU3IAAAUCEwBAgcAEAFAgMAEAFAhMAAAFAhMAQIHABABQIDABABQITAAABQITAECBXnIAAAV6yQEAFJiSAwAoEJgAAAoEJgCAAoEJAKCg7sB0zz335KKLLsqsWbPS1taWm2++eSTqAgAYM+oOTIcPH87pp5+e6667biTqAQAYcybWu8OyZcuybNmyIR3s0UeTu+8e0q7A89CRI8mddw5+f+GFyYQJza2nVR06lHz/+8n06cnSpc2uBsamUbuH6cEHk4ULk8suG1y//fbROjIwHtVqyT/8Q/LWtw4ub3/74Gs0VqWSvO51g+f37LOTz3ym2RXB2DTigalaraZSqaS/v5KDBytJKkmSr31tpI8MjGe/+lVyyy1/Xr/ttmTPnubV06q2bBn8D+3T/vVfm1cLjGUjHpj6+vrS2dmZ667rTNKZpCtJcuKJI31kYDzr6Dh2Cm7ChERzgMZ76Uufex0YNOKBafXq1RkYGMiBAwO54IKBJPuTJF/4wkgfGRjP/uZvkuuvTyZPHlz6+5OTTmp2Va3nwguTK69MJk0aPL/f/GazK4KxaVi95Nra2rJ58+Zccsklx73PwEAlJ56olxzAWFKrJW1tza4Cxq66PyX3xBNP5OGHHz66/sgjj+T+++/P1KlTM2fOnOL+/kACjD3+bobnVvcVpm3btuXcc899xuvLly/PN77xjeL+lUolnZ2uMAEA48ewpuSGQmACAMYbveQAAAoEJgCAAoEJAKBAYAIAKBCYAAAKRi0wrV27Nt3d3enp6RmtQwIANITHCgAAFJiSAwAoEJgAAAoEJgCAAoEJAKBAYAIAKBCYAAAKBCYAgAKBCQCgQGACACjQGgUAoEBrFACAAlNyAAAFAhMAQIHABABQIDABABQITAAABQITAECBwAQAUCAwAQAUCEwAAAUCEwBAgV5yAAAFeskBABSYkgMAKBCYAAAKBCYAgAKBCQCgQGACACgQmAAACgQmAIACgQkAoEBgAgAo0BoFAKBAaxQAgAJTcgAABQITAECBwAQAUCAwAQAUCEwAAAUCEwBAgcAEAFAgMLWYxx9P/u7vkjlzkhUrkiefbHZFADD+TWzEILVaLYcOHfqrv1atVlOtVo+uP71dpVJpxKH5P3p7k9tvH/z++uuTefOSf/qn5tYEAGNZR0dH2trannObhjzp++mndwMAjDfH032kIYGpnitMBw4cyGte85o8+OCDefnLXz6s4/b09GTnzp3DGqNR44yVWm64Ibn88kqSrkyatD9btkzJcNr3jZX3NRbHqVQq6erqyv79+4fd5mcsva+xNo7zPDrjOM+jM06rnuexVMtQzvHxXGFqyJRcW1tb3b/xHR0dw/5hmTBhQkP60TVinLFSy8qVydy5ycUXJ9u2TcmSJa3xvsbqOEkyZcqUlvn5GavjJM7zaIyTOM+jMU7Seud5LNXytEac4780rm/67u3tHTPjjKVazjln8OuCBcMeaky9r7E4TqOMtfc11sZplLH2vsbaOI0y1t7XWBunUcbS+xpLtYyUhkzJ1ePRRx89eqls9uzZo3no542n7yk7njlZhs55Hh3O8+hwnkeH8zzyRuocT7jmmmuuadhox6FareZLX/pSVq9encmTJ4/moZ9XJkyYkHPOOScTJzZk1pVn4TyPDud5dDjPo8N5HnkjcY5H/QqTdA0AjDfj+h4mAIDRMOpXmJ5+BMHxfIQPAGAsGPXABAAw3piSAwAoEJhazD333JOLLroos2bNSltbW26++eZml9Ry+vr60tPTk46OjsyYMSOXXHJJfvGLXzS7rJbT39+fRYsWHX343OLFi7Nly5Zml9XS+vr60tbWliuvvLLZpbSUa665Jm1tbccsJ510UrPLakm/+c1v8oEPfCDTpk3Li1/84pxxxhm57777GjK2wNRiDh8+nNNPPz3XXXdds0tpWdu3b09vb2927NiRu+66K08++WQuvPDCHD58uNmltZTZs2fn2muvza5du7Jr166cd955ufjii7N79+5ml9aSdu7cmXXr1mXRokXNLqUlnXbaaTlw4MDR5YEHHmh2SS3nj3/8Y5YuXZpJkyZly5YtefDBB/PlL385J554YkPG9xCIFrNs2bIsW7as2WW0tDvuuOOY9Q0bNmTGjBm577778oY3vKFJVbWeiy666Jj1L3zhC+nv78+OHTty2mmnNamq1vTEE0/k/e9/f9avX5/Pf/7zzS6nJU2cONFVpRH2xS9+MV1dXdmwYcPR117xilc0bHxXmGCYBgYGkiRTp05tciWt68iRI9m0aVMOHz6cxYsXN7ucltPb25u3ve1tueCCC5pdSsvas2dPZs2alXnz5uXSSy/N3r17m11Sy7n11ltz1lln5V3veldmzJiRM888M+vXr2/Y+AITDEOtVsuqVaty9tlnZ0EjmvdxjAceeCAveclL0t7enhUrVmTz5s3p7u5udlktZdOmTfnpT3+avr6+ZpfSsl772tdm48aN2bp1a9avX5/HHnssS5YsyR/+8Idml9ZS9u7dm/7+/pxyyinZunVrVqxYkcsvvzwbN25syPim5GAYPvGJT+RnP/tZfvCDHzS7lJb0qle9Kvfff38OHjyYm266KcuXL8/27duFpgbZv39/rrjiitx555154Qtf2OxyWtZf3iaxcOHCLF68OCeffHJuuOGGrFq1qomVtZannnoqZ511VtasWZMkOfPMM7N79+709/fnsssuG/b4rjDBEK1cuTK33npr7r77bo2kR8gJJ5yQV77ylTnrrLPS19eX008/PV/5yleaXVbLuO+++/K73/0ur371qzNx4sRMnDgx27dvz1e/+tVMnDgxR44caXaJLWny5MlZuHBh9uzZ0+xSWsrMmTOf8Z+pU089Nfv27WvI+K4wQZ1qtVpWrlyZzZs3Z9u2bZk3b16zS3reqNVqqVarzS6jZZx//vnP+LTWhz/84cyfPz9XX311JkyY0KTKWlu1Ws1DDz2U17/+9c0upaUsXbr0GY94+eUvf5m5c+c2ZHyBqcU88cQTefjhh4+uP/LII7n//vszderUzJkzp4mVtY7e3t7ceOONueWWW9LR0ZHHHnssSdLZ2ZkXvehFTa6udXz605/OsmXL0tXVlUOHDmXTpk3Ztm3bMz6lyNB1dHQ84967yZMnZ9q0ae7Ja6BPfvKTueiiizJnzpz87ne/y+c///lUKpUsX7682aW1lKuuuipLlizJmjVr8u53vzs/+clPsm7duqxbt64xB6jRUu6+++5akmcsy5cvb3ZpLeOvnd8ktQ0bNjS7tJbykY98pDZ37tzaCSecUJs+fXrt/PPPr915553NLqvlvfGNb6xdccUVzS6jpbznPe+pzZw5szZp0qTarFmzau94xztqu3fvbnZZLem2226rLViwoNbe3l6bP39+bd26dQ0bWy85AIACN30DABQITAAABQITAECBwAQAUCAwAQAUCEwAAAUCEwBAgcAEAFAgMAEAFAhMAAAFAhMAQIHABABQ8P8AMm8v1ALyosoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "Graphics object consisting of 1 graphics primitive"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E = EllipticCurve(GF(7), [5, 1])\n",
    "generator_point = E.gens()[0]\n",
    "\n",
    "print(generator_point)\n",
    "E.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "retained-commitment",
   "metadata": {},
   "source": [
    "Dann generiert sowohl Alice als auch Bob eine zufällige Zahl $k$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "still-probability",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "k_Alice = randint(1, E.order())\n",
    "print(k_Alice)\n",
    "\n",
    "k_Bob = randint(1, E.order())\n",
    "print(k_Bob)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sought-telescope",
   "metadata": {},
   "source": [
    "Mithilfe dieser Zahl $k$ berechnen Alice und Bob jeweils einen Punkt $P$ auf der elliptischen Kurve, wobei $$P = [k]g$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "attractive-vitamin",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1 : 0 : 1)\n",
      "(6 : 4 : 1)\n"
     ]
    }
   ],
   "source": [
    "P_Alice = generator_point * k_Alice\n",
    "print(P_Alice)\n",
    "\n",
    "P_Bob = generator_point * k_Bob\n",
    "print(P_Bob)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fixed-price",
   "metadata": {},
   "source": [
    "Nun übermitteln beide ihren Punkt $P$ an die jeweils andere Partei, sodass Alice und Bob danach sowohl $P_A$ als auch $P_B$ halten.\n",
    "Schließlich berechnen sie nun damit ihr gemeinsames Geheimnis $S$, wobei \n",
    "1. Alice: $$\\ S = k_A * P_B$$\n",
    "1. Bob: $$\\ S = k_B * P_A$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "incorporate-america",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1 : 0 : 1)\n",
      "(1 : 0 : 1)\n"
     ]
    }
   ],
   "source": [
    "S_Alice = k_Alice * P_Bob\n",
    "print(S_Alice)\n",
    "\n",
    "S_Bob = k_Bob * P_Alice\n",
    "print(S_Bob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ongoing-purpose",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S_Alice == S_Bob"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abstract-evening",
   "metadata": {},
   "source": [
    "Beide erhalten durch diese Berechnung immer denselben Punkt und können diesen nun z.B. zur Herleitung eines symetrischen Schlüssels nutzen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "separate-issue",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d2468be8d744bfe3dd8099b828778d32b36c17b5406b0a78e69341f748bf6672\n",
      "d2468be8d744bfe3dd8099b828778d32b36c17b5406b0a78e69341f748bf6672\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "import hashlib\n",
    "\n",
    "symmetric_key_Alice = hashlib.sha256(str.encode(str(S_Alice))).hexdigest()\n",
    "symmetric_key_Bob = hashlib.sha256(str.encode(str(S_Bob))).hexdigest()\n",
    "\n",
    "print(symmetric_key_Alice)\n",
    "print(symmetric_key_Bob)\n",
    "print(symmetric_key_Alice == symmetric_key_Bob)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "simplified-recycling",
   "metadata": {},
   "source": [
    "Selbstverständlich sind die in diesem Beispiel verwendeten Parameter viel zu niedrig gewählt, um eine kryptographische Sicherheit zu gewährleisten. Ein reales Beispiel würde wie folgt aussehen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "genuine-congo",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "***************************************\n",
      "Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663\n",
      "Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663\n",
      "(78696708153184819567544810616103055619645698255331501928390144358423314934016 : 98197484079477709298865125717672581729054831664614472341666166473053965684281 : 1)\n",
      "***************************************\n",
      "42956184598832547792949270197027374667270579501835603623613540984994606618267\n",
      "47692210690214431202537199854715086077584216781677078706738465564234285081721\n",
      "***************************************\n",
      "(38295126938078941939976222689116143927950187545104350356450481690684232840859 : 80982991530678690881206303256208595697922177426248038727863566703100242377420 : 1)\n",
      "(44020634773345752709749907823136109644309741515504242932025317738699769307487 : 56039836954962905420888318058881171722666489065579159867480979385254588470177 : 1)\n",
      "***************************************\n",
      "(23201413120982876294469315546122632497616120532863789331410594049101662509778 : 17865770870461279352579889639962116507308123793961105930478034059382188361490 : 1)\n",
      "(23201413120982876294469315546122632497616120532863789331410594049101662509778 : 17865770870461279352579889639962116507308123793961105930478034059382188361490 : 1)\n",
      "True\n",
      "***************************************\n",
      "e1c6aadaab44f221f88826df4de9ee754c347cc8b9e8111f48d3c1fffc2ca6d9\n",
      "e1c6aadaab44f221f88826df4de9ee754c347cc8b9e8111f48d3c1fffc2ca6d9\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "import hashlib\n",
    "\n",
    "K = GF(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f)\n",
    "E = EllipticCurve(K, [0, 7])\n",
    "generator_point = E.gens()[0]\n",
    "\n",
    "print(\"***************************************\")\n",
    "print(K)\n",
    "print(E)\n",
    "print(generator_point)\n",
    "\n",
    "print(\"***************************************\")\n",
    "k_Alice = randint(1, E.order())\n",
    "print(k_Alice)\n",
    "\n",
    "k_Bob = randint(1, E.order())\n",
    "print(k_Bob)\n",
    "\n",
    "print(\"***************************************\")\n",
    "P_Alice = generator_point * k_Alice\n",
    "print(P_Alice)\n",
    "\n",
    "P_Bob = generator_point * k_Bob\n",
    "print(P_Bob)\n",
    "\n",
    "print(\"***************************************\")\n",
    "S_Alice = k_Alice * P_Bob\n",
    "print(S_Alice)\n",
    "\n",
    "S_Bob = k_Bob * P_Alice\n",
    "print(S_Bob)\n",
    "\n",
    "print(S_Alice == S_Bob)\n",
    "\n",
    "print(\"***************************************\")\n",
    "symmetric_key_Alice = hashlib.sha256(str.encode(str(S_Alice))).hexdigest()\n",
    "print(symmetric_key_Alice)\n",
    "\n",
    "symmetric_key_Bob = hashlib.sha256(str.encode(str(S_Bob))).hexdigest()\n",
    "print(symmetric_key_Bob)\n",
    "\n",
    "print(symmetric_key_Alice == symmetric_key_Bob)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "equivalent-tunisia",
   "metadata": {},
   "source": [
    "## Elliptische Kurven im Projektiven Raum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "flying-sixth",
   "metadata": {},
   "source": [
    "Wenn Sie das obige Beispiel aufmerksam ausgeführt haben, sollte Ihnen aufgefallen sein, dass die Punkte der elliptschen Kurve nicht in der $x,y$ Koordinatenform: $P = (x_P, y_P)$ dargestellt werden.\n",
    "SageMath verwendet zur Darstellung von Punkten die mathematisch und algorithmisch effizientere Darstellungsform der Projektivkoordinaten. Dabei besitzt jeder Punkt nicht zwei sondern drei Variablen _[3]_: $$P_{Projektiv} = (x : y : z)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "liberal-customs",
   "metadata": {},
   "source": [
    "Um dies zu verstehen müssen wir den Projektiven Raum $\\mathbb{P}$ betrachten"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "trained-nicaragua",
   "metadata": {},
   "source": [
    "Der projektive Raum $\\mathcal{P}^3$ besitzt 3 Dimensionen.\n",
    "Der Kern dieses Raumes besteht dabei aus seiner sog. Äquvivalenzrelation $\\sim$, wobei alle Punkte $P = (x : y : z)$, die auf derselben Geraden durch den Ursprung $(0 : 0: 0)$ liegen, äquivalent zueinander sind _[1]_:\n",
    "$$P_1 = (x : y : z) \\ ; \\ P_2 = (a*x : a*y : a*z) \\ ; \\ P_1 \\sim P_2$$ "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "applied-northeast",
   "metadata": {},
   "source": [
    "Um affine elliptische Kurven in Weierstraßform in ihre Projektivfrom umzuwandeln, muss die Gleichung entsprechend angepasst werden\n",
    "$$E_{Affin}: y^2 = x^3 + ax + b \\rightarrow E_{Projektiv}: y^2z = x^3 + axz^2 + bz^3$$\n",
    "Wenn wir nun $z = 1$ setzen erhalten wir wieder die affine Weierstraßform: $$z = 1$$ $$[y^21 = x^3 + ax1^2 + b1^3] \\rightarrow [y^2 = x^3 + ax + b]$$ \n",
    "Genau diese Methode wurde auch bei den Punkten im obigen kryptographischen Beispiel angewandt. \n",
    "So können auch alle bisher bekannten Punkte in affiner Form in Projektivform umgewandelt werden: $P_{Affin} = (x, y) \\rightarrow P_{Projektiv} = (x : y : 1)$ \n",
    "Ein Vorteil der projektiven Form ist, dass der Punkt im Unendlichen darstellbar wird. Stellen wir dazu die Frage, welche Punkte durch die projektive Form nicht darstellbar sind. Dies sind alle Punkte, die auf der Geraden $x = 1$ liegen, da diese niemals einen Schnittpunkt mit einer der Äquivalenzgeraden besitzen _[3]_. \n",
    "Daher wird der Punkt im Unendlichen mit $\\mathcal{O} = (0 : 1 : 0)$ notiert"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "finnish-poker",
   "metadata": {},
   "source": [
    "Die Projektivform wird zumeist in der Praxis gewählt, da mit ihr deutlich effizienter gerechnet werden kann. Dazu ein kurzes Bespiel:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "colonial-decline",
   "metadata": {},
   "source": [
    "Die Formel zur Punktdopplung (Skalarmultiplikation mit $k=2$) eines Punktes $P_1 = (x_1, y_1)$ in affiner Form _[1]_ :$$\\lambda = \\frac{3x_1^2+a}{2y_1}$$ </br> $$x_2=\\lambda^2 - 2x_1$$ $$y_2 = \\lambda(x_1-x_2) - y_1$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "relative-soldier",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 3)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def point_doubling_affine(x_1, y_1, a):\n",
    "    lambda_ = ((3 * x_1) + a) / (2 * y_1)\n",
    "    x_2 = (lambda_ ** 2) - 2 * x\n",
    "    return (x_2, lambda_ * (x_1 - x_2) - y_1)\n",
    "\n",
    "K.<i> = GF(7)\n",
    "E = EllipticCurve(K, [5, 1])\n",
    "\n",
    "random_point = E.random_point()\n",
    "x = random_point[0]\n",
    "y = random_point[1]\n",
    "\n",
    "point_doubling_affine(x, y, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "elder-sacramento",
   "metadata": {},
   "source": [
    "Die Formel zur Punktdopplung eines Punktes $P_1 = (x : y : z)$ in projektiver Form:\n",
    "$$\\lambda = az^2 + 3x^2 $$ $$\\sigma = yz$$ $$\\rho = xy\\sigma$$ $$\\psi = \\lambda^2 - 8\\rho$$\n",
    "$$x_2 = 2\\psi\\sigma$$ $$y_2 = \\lambda(4\\rho-\\psi)-8y_1^2\\sigma^2$$ $$z_2 = 8\\sigma^3$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "local-cheat",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(6 : 4 : 1)\n",
      "(3 : 6 : 1)\n"
     ]
    }
   ],
   "source": [
    "K.<i> = GF(7)\n",
    "E = EllipticCurve(K, [5, 1])\n",
    "\n",
    "random_point = E.random_point()\n",
    "\n",
    "print(random_point)\n",
    "print(random_point * 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "experimental-specification",
   "metadata": {},
   "source": [
    "Auf den ersten Blick scheint die Formel zur Punktdopplung mit affinen Koordinaten simpler zu sein. Das soll jedoch nicht darüber hinwegtäuschen, dass die zweite Formel mit projektiven Koordinaten um Magnituden schneller ist. Dies ist in der Division begründet, wobei die erste, affine Formel stets $(2y_1)^{-1}$ berechnen muss. Die Inversion eines Elementes eines endlichen Felds über diesem Feld ist äußerst kostspielig (in Bezug auf Rechenzeit) und muss daher in der Praxis mit allen Mittel vermieden werden. Die zweite projektive Formel benötigt dabei keine Inversion. \n",
    "Dies ist die Begründung warum in der Praxis zumeist projektive Koordinaten verwendet werden."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exposed-state",
   "metadata": {},
   "source": [
    "Die folgende Tabelle listet die Anzahl der nötigen Operationen für den jeweiligen Algorithmus _[3]_\n",
    "\n",
    "| Typ       | Addition | Subtraktion | Multiplikation | Inversion |\n",
    "|-----------|----------|-------------|----------------|-----------|\n",
    "| Affin     | 1        | 3           | 6              | 1         |\n",
    "| Projektiv | 1        | 3           | 19             | 0         |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "involved-local",
   "metadata": {},
   "source": [
    "## Montgomery Kurven"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "qualified-alpha",
   "metadata": {},
   "source": [
    "Wie bereits erwähnt stellen elliptische Kurven eine unverzichtbare Grundlage der modernen Kryptographie dar. Daher wird seit deren Entdeckung für die Kryptographie stetig an Optimierungen geforscht. Die wohl wichtigste und meistbenutzte Optimierung wird nun im Folgenden besprochen."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "instructional-pricing",
   "metadata": {},
   "source": [
    "Elliptische Kurven können durch mehrere Formen dargestellt werden. Die wohl einfachste Form wird als Weierstraßform bezeichnet und wurde bis jetzt auch in diesem Notebook durchgehend verwendet: $$E_{Weierstrass}: y^2 = x^2 + ax + b \\ ; \\ a, b \\in \\mathbb{K}$$ \n",
    "Elliptische Kurven können jedoch auch mittels der sogenannten Montgomeryform dargestellt werden: $$E_{Montgomery}: By^2 = x^3 + Ax^2 + x \\ ; \\ A, B \\in \\mathbb{K}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "medieval-jumping",
   "metadata": {},
   "source": [
    "Jede Montgomerykurve mit $B \\neq 0$ kann auch wieder in eine Weierstraßform gebracht werden. Daraus folgt, dass die Montgomeryform lediglich eine weitere (jedoch besondere) Darstellungsweise einer elliptischen Kurve ist. Die Formeln zur Transformation lauten dabei _[3]_: $$\\psi:(y^2 = x^2 + ax + b) \\rightarrow (By^2 = x^3 + Ax^2 + x)$$ $$\\psi(A, B): (a = \\frac{3 - A^2}{3B^2}) \\ , \\ (b = \\frac{2A^3-9A}{27B^3})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "present-receiver",
   "metadata": {},
   "source": [
    "Umgekehrt kann jedoch, aufgrund der besonderen Eigenschaften der Montgomerykurven, nicht jede Weierstrasskurve in eine Montgomerykurve umgewandelt werden. Auf die Bedingungen für eine solche Transformation wird hier verzichtet. In Referenz _[5]_ können die genauen Abbildungsvorschriften nachgelesen werden. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "direct-witness",
   "metadata": {},
   "source": [
    "Zusätzlich zu dieser veränderten Kurvengleichung wird auch eine neue Punktform eingeführt. Diese ist im Grunde eine projektive Punktform, wobei die $y$-Koordinate vernachlässigt wird. Die Montgomerykoordinatenform lautet daher: $P_{Montgomery} = (x : z)$, wobei die gleiche Transformation von affinen Koordinaten angewandt wird. Dabei gilt: $$(x, y) \\rightarrow (x/z : z) \\ ; \\ z \\neq 0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alive-skill",
   "metadata": {},
   "source": [
    "Dabei ist zu beachten, dass bei dieser Punktform die Information über die $y$ Koordinate verloren geht. Somit sind die affinen Punkte $P_1 = (x, y) \\ ; \\ P_2 = (x, -y)$ gemäß ihrer Montgomerypunktform äqvivalent. \n",
    "Die Punktdopplung kann somit auf Montgomeryform angepasst werden. Die explizite Formel zur Punktdopplung unter Verwendung einer Montgomerykurve mit dem Punkt $P_1 = (x_1 : z_1)$ in Montgomerypunktform lautet dabei: \n",
    "$$[2](x_1 : z_1) = [2]P_1 = P_2 = (x_2 : z_2)$$\n",
    "$$x_2 = (x_1^2 - z_1)^2$$\n",
    "$$z_2 = 4x_1(x_1^2 + Ax_1 + z_1)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hazardous-harvest",
   "metadata": {},
   "source": [
    "Für diesen Punktdopplungsalgorithmus sind folgende Operationen nötig:\n",
    "\n",
    "| Typ        | Addition | Subtraktion | Multiplikation | Inversion |\n",
    "|------------|----------|-------------|----------------|-----------|\n",
    "| Montgomery | 2        | 1           | 6              | 0         |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "pleased-optimization",
   "metadata": {},
   "source": [
    "Der Zusammenschluss der Montgomerykurve und der Montgomerypunktform wird auch als Montgomeryarithmetik bezeichnet. Die Montgomeryarithmetik ist dabei die schnellste derzeit bekannte Form der Arithmeitk auf elliptischen Kurven. Die berühmte Montgomerykurve *Curve25519* wird zum Beispiel in den kryptographischen Systemen von WhatsApp, Tor, GPG und SSH verwendet"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "expressed-realtor",
   "metadata": {},
   "source": [
    "## Referenzen\n",
    "_[1]_ Understanding Cryptography; Paar Christof, Pelzl Jan; 2010 Springer\\\n",
    "_[2]_ An Elementary Proof Of The Group Law For Elliptic Curve; Friedl Stefan; 2017 De Gruyter\\\n",
    "_[3]_ Elliptische Kurven in der Kryptographie; Werner Anette; 2002 Springer\\\n",
    "_[4]_ Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS); Blake-Wilson S., Bolyard N.; 2006 The Internet Society\\\n",
    "_[5]_ Montgomery Curve; https://en.wikipedia.org/wiki/Montgomery_curve#Equivalence_with_Weierstrass_curves; 2021 The Wikipedia Foundation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alert-campaign",
   "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
}