View notebook: http://nbviewer.ipython.org/gist/stefan2904/f9e6aaf1e8734325877d

simple_ecc_vis1.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:22c35a963d3b398d5ac56cb10d0092b00a6909776cd4ed3381dceb7d88ac3be9"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Simple Elliptic Curve Visualization"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Curve Equation:\n",
      " y^2 = x^3 + a*x + b"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Curve Parameter:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "a = 2\n",
      "b = 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Field Order:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "p = 5"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Setup:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "import numpy as np\n",
      "import matplotlib.pyplot as plt\n",
      "from math import sqrt"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Draw Elliptic Curve:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "y, x = np.ogrid[-5:5:100j, -5:5:100j]\n",
      "plt.contour(x.ravel(), y.ravel(), pow(y, 2) - pow(x, 3) - x * a - b, [0])\n",
      "plt.grid()\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD7CAYAAABKfn7LAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHpFJREFUeJzt3Xd8VGW+BvDnl4QqTUGliDeuCFLUQCwgIEGpUap0JA4l\nAdELuHrXBWVxxYLreukoSDAgSxEIgSDEggQQpAkRlWK7KFVElN6See8fAQ8ihJCZOe87532+nw+f\nz04ymfnts2d/HJ45mRGlFIiIKHxE6B6AiIiuDBc3EVGY4eImIgozXNxERGGGi5uIKMxwcRMRhZmo\nUD+BiPB6QyKiAlBKycW+7soZt1JK+59hw4Zpn8GUP8yCWYQ6iwkT1qFu3cnIzs7R/t9LdxYF/ZOX\nkJ9xm2LHjh26RzAGs3AwC0ewsti16zD+8Y9MLF/uQ2RkeLaxph8X4ZkqERlJKYV+/RbhiSfuQo0a\n1+oex7OsOeP2+Xy6RzAGs3AwC0cwsnj77Szs3n0EqakNAx9II9OPC7lclxLwE4ioUD8HEen344+H\nEBs7CR9/nIDbbrte9zhhT0SgdL44aYLMzEzdIxiDWTiYhSOQLJRSSExMx6BB93hiaZt+XFizuIko\ndN5+OwsHDhzH3/5WX/coVmBVQkQB2bkztyL56KME3H57+J9tm4JVCRGFhN+v0LPnAgwaVJdL20XW\nLG7TOys3MQsHs3AUJIuxY9fixIlsz1Ukph8X1lwOSETBtX37AQwfvgJr1vRBVJQ154BGYMdNRFcs\nO9uPBg2mICHhDvTvf5fucTyJHTcRBdW//rUKV11VGP363al7FCtZs7hN76zcxCwczMKR3yzWr9+N\n0aPXIiWlDSIiLnpCGPZMPy6sWdxEFLijR0+je/dUjB8fj8qVS+sex1rsuIko3/r2TcepUzlISWmr\nexTPy6vj5lUlRJQvixZ9jQ8++B6ff95P9yjWC0pVIiKRIrJJRNKD8XihYHpn5SZm4WAWjryy2Lfv\nKJKS0pGS0galShVxbyhNTD8ugtVxDwSwBQA7ESKP8fsVevSYjz596qBRo2jd4xCC0HGLyA0AUgC8\nBOCvSqlWF3yfHTdRGPvXv1YhPf1rLFv2KH/RxkWh7rhHAvgfAKWC8FhEZJANG/bg3/9ejQ0bkri0\nDRLQ4haRhwDsV0ptEpG4S93P5/MhOjoaAFCmTBnExMQgLi737ue6pFDfPvc1t57P5NtZWVkYNGiQ\nMfPovD1q1Cgtx6OJty/8/8qxY6fRtu0IPPZYbdx4Y2nt87l5+9zX3M4/JSUFAH7fl5cSUFUiIi8D\n6AEgG0BR5J51z1NKJZx3HyOqkszMzN/Dsh2zcDALx/lZKKWQkJCGqKgIvP12G72DaWDCcZFXVRK0\n67hFpBGAp9lxE4W/yZM3YvTotVi7tg+KFy+kexwruXkdNzc0UZj78sv9GDx4KVas8HFpGyporzYo\npZYrpVoH6/GC7fzuynbMwsEsHJmZmTh+/Aw6dZqD115riurVr9U9kjamHxd8mZiIfjdgwBLUqVMB\nPl+M7lEoD3yvEiICALz11mcYNWot1qzpjZIlvf/bkabje5UQUZ42btyLIUM+xief9OTSDgPWVCWm\nd1ZuYhYOZgH89ttJdOw4B/37l0O1auV0j2ME048LnnETWUwphV69FiA+vgoaNy6uexzKJ3bcRBZ7\n+eWVWLBgO1as8KFIEZ7HmYQdNxH9yeLF32D8+PVYvz6RSzvMsOO2ELNw2JrFd98dRM+eC/Duux1Q\nsWJJAPZmcTGmZ2HN4iaiXMePn0H79u9i6ND7UL/+jbrHoQJgx01kEaUUunadh0KFIjFtWluIePNT\n2r2AHTcRAQBeeGE5fvjhEJYte5RLO4xZU5WY3lm5iVk4bMoiNXUrkpM3Yf78ziha9M/nbDZlcTmm\nZ8EzbiILfPHFT+jbdxGWLOmO8uVL6B6HAsSOm8jjfvrpKOrWTcaLLzZG9+636x6H8imvjtuaqoTI\nRsePn0GrVjORkHA7l7aHWLO4Te+s3MQsHF7Owu9XSEiYj2rVyuH55+Mue38vZ3GlTM+CHTeRRw0d\n+jH27TuKpUsTeAWJx7DjJvKg5OSNeOmllVi7tg+uvfYq3eNQAfA6biKLLFr0NZ57bhlWrPBxaXsU\nO24LMQuH17JYt243evVagAULuuCWW8pe0c96LYtAmJ6FNYubyOu+//5XtG07C1OmtMHdd1fSPQ6F\nEDtuIg/Ys+cIGjZ8G089VQ/9+9+lexwKAl7HTeRhBw+eQLNm76B379pc2pawZnGb3lm5iVk4wj2L\nY8dO46GHZqBFiyoYPLhBQI8V7lkEk+lZWLO4ibzm9OkcdOw4B1WrlsVrrzXltdoWYcdNFIbOnMld\n2iKCd9/tgEKFInWPREHG67iJPCQ7249u3VKhFLi0LWVNVWJ6Z+UmZuEItyz8foU+fRbi8OFTePfd\nDihcOHhLO9yyCCXTs+AZN1GYyMnxIzExHd9//yuWLOnOT2a3GDtuojCQk+OHz7cAe/YcwcKFXXDV\nVYV1j0Qhxo6bKIxlZ/uRkDAfP/98HOnpXVG8eCHdI5Fm7LgtxCwcpmdx+nQOHnkkFb/8cgILF3YJ\n6dI2PQs3mZ6FNYubKNwcO3YarVvPxIkT2UhL64xixXimTbnYcRMZ6NChk4iPn4GqVcvirbdaISqK\n51i24XuVEIWRn346igcemIY6dcojObk1lzb9ScBHhIhUFpFlIvKViHwpIgOCMViwmd5ZuYlZOEzL\nYtu2A6hXLxkPPVQVY8a0RESEe7/GbloWOpmeRTCuKjkD4EmlVJaIlADwmYh8qJTaGoTHJrLGp5/u\nRLt2szFiRBP4fDG6xyGDBb3jFpE0AGOVUkvP3mbHTXQZ8+dvRVLSIkyb1hYtW96iexwygGvXcYtI\nNIDaANYG83GJvEophVde+QQTJqzHkiXdceedFXWPRGEgaK96nK1J5gIYqJQ6GqzHDRbTOys3MQuH\nzixOnsxGjx7zkZq6FWvX9tG+tHlcOEzPIihn3CJSCMA8ANOVUmkXft/n8yE6OhoAUKZMGcTExCAu\nLg6AE1Cob5/j1vOZfDsrK8uoeXTezsrK0vL81arFomPHOYiM/AEvvtgQlSqVMiIP3s69fY6bz5+Z\nmYmUlBQA+H1fXkrAHbfkvnv7VAC/KKWevMj32XETnWflyh/Qpcs8JCXVwdChjVy9coTCR14ddzAW\ndwMAKwBsBnDuwQYrpTLOfp+Lmwi5ffYbb2zAP/+5HFOntkWLFlV0j0QGC+kv4CilPlFKRSilYpRS\ntc/+yQj0cYPtwn8C2YxZONzK4vDhU+jePRUTJqzH6tW9jFzaPC4cpmfBX8kiCrHPPtuD2rUnonTp\nIli3LhE333yN7pEozPG9SohC5Fw18vzzmRg/Ph4dO9bUPRKFEb4fN5HLdu8+jJ49F+DQoVP45JNe\nqFq1rO6RyEOsqUpM76zcxCwcocgiLW0b6tSZhIYNb8SqVeGztHlcOEzPgmfcREGyf/8xDByYgXXr\ndiMtrTPq1auseyTyKHbcREEwf/5WPPbYe+jR43b885+N+fFiFDB23EQhsmvXYfz1r+9j06Z9SE3t\njHvv5Vk2hR47bgsxC0dBs/D7FSZMWI+YmDdx663lsHlzv7Bf2jwuHKZnwTNuoiu0adNe/Pd/L4Hf\nr7ByZU9Ur36t7pHIMuy4ifLp0KGTGDJkKebO3Yrhwxujd+/aiIy05h+t5DJ+5iRRAJRS+M9/NqNm\nzQk4c8aPrVsfR1JSLJc2aWPNkWd6Z+UmZuG4XBYbN+5F/fpTMHLkGsye3QGTJrXCNdcUc2c4l/G4\ncJieBTtuoov49dcTeP75TMye/RVefvkB+HwxfPtVMgY7bqLz5OT4kZy8CUOHLkP79rdi+PD7Ua5c\ncd1jkYV4HTdRPmRl7cNjj72HiAhBRkZ31K5dQfdIRBfFjttCzMKRmZmJw4dPYdCgDDRr9g569ozB\nypU9rVzaPC4cpmdhzeImupg1a3ahZs0JOHLkFL76qj+SkmLZZZPx2HGTlQ4ePIEnn3wfK1f+gMmT\nW+P++2/SPRLRH/A6bqLzvP/+t7jttjdQunQRbN78GJc2hR1rFrfpnZWbbM0iO9uPwYM/Qu/eCzF9\nejuMGdMSGzas1j2WMWw9Li7G9Cx4VQlZYc+eI+jceS6KFy+EjRv74rrrrtI9ElGBseMmz/v8831o\n1WomEhPr4Nln7+OLjxQWeB03WeuDD77DI4+kYty4eHTqxA/rJW9gx20hW7JIT9+OHj3mIzW18yWX\nti1Z5AezcJieBc+4yZMWL/4GffqkY9Girrjrrkq6xyEKKnbc5DkbN+5F8+bTkZ7eFXXr3qB7HKIC\n4XXcZI2ffz6G9u1n4803H+TSJs+yZnGb3lm5yatZ+P0KXbrMQ/fut+Hhh2vk62e8mkVBMAuH6VlY\ns7jJ+8aPX4eTJ7PxwguNdY9CFFLsuMkTdu8+jDvueBOrVvVCtWrldI9DFLC8Om4ubvKEJ55YjGLF\novDaa810j0IUFHxxEuZ3Vm7yWhZ79x7BjBlf4Omn773in/VaFoFgFg7Ts7BmcZN3TZz4Gbp1uw3X\nX19C9yhErmBVQmFNKYWbbx6DOXM6Ija2ou5xiIKGVQl51rp1u1GkSBTq1LHvo8bIXtYsbtM7Kzd5\nKYvMzB1o3vxmiBTsHf+8lEWgmIXD9CwCXtwi0kJEtonINyLyTDCGIsqvlSt/RMOGN+oeg8hVAXXc\nIhIJYDuAJgB2A1gPoKtSaut592HHTSFTpcoYvPdeN167TZ4Tyo77bgDfKqV2KKXOAJgFoE2Aj0mU\nL36/wq5dh3HjjaV1j0LkqkAXdyUAO8+7vevs14xjemflJq9kceLEGURECIoVK1Tgx/BKFsHALBym\nZxHo+3HnqwPx+XyIjo4GAJQpUwYxMTGIi4sD4AQU6tvnuPV8Jt/Oysoyap5Abvv9/4fMzMwC/3xW\nVpZR/31424zb57j5/JmZmUhJSQGA3/flpQTacdcF8LxSqsXZ24MB+JVSr553H3bcFBKnT+egRImX\ncfLkc/wcSfKcUHbcGwDcIiLRIlIYQGcACwN8TKJ8KVw4EtdcUwz79h3VPQqRqwJa3EqpbABPAHgf\nwBYAs8+/osQkF/4TyGZeyuKmm67Gd98dLPDPeymLQDELh+lZBHwdt1JqiVKqmlKqilLqlWAMRZRf\n99xTCatX77z8HYk8hO9VQmEtNXUrJk36DBkZj+gehSio+F4l5FlNmvwFa9bswoEDx3WPQuQaaxa3\n6Z2Vm7yURalSRRAffwtmzfqyQD/vpSwCxSwcpmdhzeIm70pMrIOxY9chJ8evexQiV7DjprCnlEL9\n+lMwcOA96Ny5lu5xiIKCHTd5mohg2LBGGDp0GU6dytY9DlHIWbO4Te+s3OTFLJo3r4KaNa/D8OEr\nrujnvJhFQTELh+lZWLO4yfsmTIjHW29txKpVP+oehSik2HGTpyxe/A0SE9Oxfn0iKlYsqXscogJj\nx03WiI+/Bf3734n27Wfj+PEzuschCglrFrfpnZWbvJ7FkCENUbVqWbRvPxsnT+b9YqXXs7gSzMJh\nehbWLG6yh4hgypQ2KF26KNq1m40TJ3jmTd7Cjps8KzvbD58vDd9//ysWLuyKcuWK6x6JKN/YcZOV\noqIiMG1aOzRq9F+oVy8ZX3/9i+6RiILCmsVtemflJpuyiIgQvPJKEzzzTH00aDAFc+du+cP3bcri\ncpiFw/QsrFncZLc+fepg8eLueOaZj9C//3uXfdGSyGTsuMkqhw6dRGJiOrZtO4CpU9uidu0Kukci\nuqi8Om4ubrKOUgrTp2/G009/iKSkOnjuuftQpEiU7rGI/oAvTsL8zspNtmchIujR4w5kZfXFsmWZ\nuPPOt/Dpp/z4M9uPi/OZngVPM8haFSqUxPDhjfHTT9eiQ4c5iI+vghEjmqBsWV42SGZjVUKE3O77\nH/9YhlmzvsKrrzZBQsIdiIi46L9SiVzBjpsonzZu3Iu+fRchKioCY8e2xJ13VtQ9ElmKHTfM76zc\nxCwcF2ZRp04FrF3bB0lJddCq1UwkJaXj4METeoZzGY8Lh+lZWLO4ifIrIkLQs2dtbNv2OAoXjkSN\nGuMxceIGfqYlGYNVCdFlZGXtw8CBGTh06CQmTnwI99xzg+6RyALsuIkCpJTCzJlf4qmnPkDbttXw\n4ov38+oTCil23DC/s3ITs3DkNwsRQbdut2HLlv6IiopA9erjkZy8EV46KeFx4TA9C2sWN1EwXH11\nMYwdG48PPuiBN97YgGbNpuPbbw/qHossw6qEqICys/0YNWoNRoz4BAMG3IPBgxugUKFI3WORR7Dj\nJgqhnTsPISlpEfbvP4apU9uiVq3rdI9EHsCOG+Z3Vm5iFo5gZFG5cmksXtwNffvGonHjqRg2bBlO\nn84JfDiX8bhwmJ6FNYubKJREBElJscjK6osNG/aifv0p7L4pZFiVEAWZUgrjxq3DCy+swIsvNkZS\nUixE+L4ndGXYcRNpsGXLz0hImI+KFUti6tS2uPrqYrpHojDCjhvmd1ZuYhaOUGZRo8a1WL26N/7y\nl6sRGzsJa9fuCtlzBQOPC4fpWQS0uEXkNRHZKiKfi0iqiJQO1mBEXlC4cCRGjWqB119vhtatZ+HV\nVz/x1C/tkB4BVSUi0hTAUqWUX0RGAIBS6u8X3IdVCRFyLxvs0GEOoqPLIDm5NUqUKKx7JDJYyKoS\npdSHSqlzb5m2FgDffYfoEipXLo3ly3246qpCqFt3Mr7++hfdI1GYCmbH3QvA4iA+XlCZ3lm5iVk4\n3M6iaNEoJCe3xsCB96BBgylYvPgbV58/LzwuHKZncdnFLSIfisgXF/nT6rz7PAvgtFJqRkinJfIA\nEUFiYiwWLOiC3r0XYvToNey96Ypc9sOClVJN8/q+iPgAxAN44FL38fl8iI6OBgCUKVMGMTExiIuL\nA+D8zcbb7t4+x5R5dN0+9zUdz1+vXmWMHFkNgwfPxpYtP2PcuHisWrVSWx5xcXHa//ew+XZmZiZS\nUlIA4Pd9eSmBvjjZAsDrABoppQ5c4j58cZIoD0eOnEK3bqk4fvwMUlM7oXTporpHIgOE8jrusQBK\nAPhQRDaJyIQAHy9kLjzTtBmzcJiQRcmSRZCW1hm33loWjRqlYO/eI1rmMCELU5ieRaBXldyilPov\npVTts3/6B2swIptERkZg3Lh4dOpUE/feOwVffbVf90hkMP7KO5Fhpk/fjL/+9X2kpXXBvfdW1j0O\nacL3KiEKMxkZ36JHj/mYPbsD7r//Jt3jkAZ8rxKY31m5iVk4TM2iRYsqmDOnI7p0mYvU1K2uPKep\nWehgehaXvRyQiPSIi4tGRsYjePDBGTh69DQSEu7QPRIZglUJkeG2bv0ZTZq8g5dfvh+PPhqjexxy\nSV5VCc+4iQxXvfq1WLo0AU2aTENOjkKvXrV1j0SaseO2ELNwhEsWt95aDh9//CiGDcvEm29uCMlz\nhEsWbjA9C55xE4WJqlXLYvlyH+LiUlC0aBR8PtYmtmLHTRRmtm8/gMaNp2LkyObo3LmW7nEoRNhx\nE3lItWrlkJHxCJo1ewdRURF4+OEaukcil7HjthCzcIRrFrfffj0yMh7B448vxpIlwXlP73DNIhRM\nz8KaxU3kNTEx5TF/fmckJKTh00936h6HXMSOmyjMLVnyDXy+BVi6NAG1al2nexwKEv7KO5GHtWx5\nC0aNao7mzafj228P6h6HXGDN4ja9s3ITs3B4JYuuXW/DsGGN0KLFdPz887ECPYZXsggG07OwZnET\neV1SUiw6daqJ1q1n4fjxM7rHoRBix03kIUopPPpoGn777SRSUzsjKornZuGKHTeRJUQEkye3xqlT\nOejf/z1+erxHWbO4Te+s3MQsHF7MonDhSMyd2xHr1+/B669/mu+f82IWBWV6FtYsbiKblCxZBAsX\ndsHIkWuwcOF23eNQkLHjJvKwdet248EHZyAjoztiYyvqHoeuADtuIkvdfXclTJr0EFq3noUffzyk\nexwKEmsWt+mdlZuYhcOGLNq1q44nn6yLdu1m53mZoA1Z5JfpWVizuIls9tRT9VC9ejn07r2QV5p4\nADtuIkucOHEG992XgnbtbsWQIQ11j0OXwY6biFCsWCGkpXXGG29sQGrqVt3jUACsWdymd1ZuYhYO\n27KoVKkU0tI6o2/fRdi27cAfvmdbFnkxPQtrFjcR5YqNrYhXX22Cdu1m4/DhU7rHoQJgx01kqX79\nFmH//mOYO7cTIiIuWqWSRuy4iehPRo9ugX37juKll1boHoWukDWL2/TOyk3MwmFzFkWKRGHevE6Y\nOPEzZGR8a3UWFzI9C2sWNxH9WYUKJfGf/7SHz5eG/fuP6h6H8okdNxFhxIhPsHDhdmRm+lC4cKTu\ncQh5d9xc3EQEv1+hTZtZuOmmMhgzpqXucQh8cRKA+Z2Vm5iFg1nkiogQJCVdg8WLv8HMmV/oHkc7\n048LaxY3EeWtZMkimDOnIwYMyMB33/HT4k0WcFUiIk8BeA1AOaXUn/7XZlVCFF5Gj16Dd97ZjFWr\neqFIkSjd41grZFWJiFQG0BTAD4E8DhGZY8CAe3DDDaXwzDMf6R6FLiHQquR/AfwtGIOEmumdlZuY\nhYNZOM5lISJ4++02WLBgu7VvRmX6cVHgxS0ibQDsUkptDuI8RGSAq68uhnff7YB+/Rbxk3MMlGeB\nJSIfAih/kW89C2AwgGbn3/1Sj+Pz+RAdHQ0AKFOmDGJiYhAXFwfA+ZuNt929fY4p8+i6fe5rpsyj\n83ZcXNwfbt91VyW0bVsUrVq9go0bX0ZkZIRR83rtdmZmJlJSUgDg9315KQV6cVJEagFYCuD42S/d\nAGA3gLuVUvsvuC9fnCQKU36/QtOm76Bx42g899x9usexStBfnFRKfamUul4pdZNS6iYAuwDUuXBp\nm+TCM02bMQsHs3BcLIuICMG0aW0xbtw6rFr1o/tDaWL6cRGs67h5Sk3kUZUqlcLkya3RrVsqfv31\nhO5xCPyVdyLKpwEDluDAgeOYMeNh3aNYgb/yTkQBGzGiCTZt2odZs77UPYr1rFncpndWbmIWDmbh\nuFwWxYsXwvTp7TBgwBLs3OntSwRNPy6sWdxEFLjY2IoYNKguEhLSkJPj1z2OtdhxE9EVycnx44EH\npqFFiyr4+98b6B7Hs/h+3EQUVD/+eAixsZOwbNmjqFXrOt3jeBJfnIT5nZWbmIWDWTiuJIsbbyyN\nESMeQELCfJw5kxO6oTQx/biwZnETUXD16lUbFSqUxPDh/JR4t7EqIaIC27v3CGrXnoi0tC6oW/cG\n3eN4CqsSIgqJChVKYvz4ePToMR/Hj5/RPY41rFncpndWbmIWDmbhKGgWDz9cA3fdVRHPPfdxcAfS\nyPTjwprFTUShM2ZMS8yc+SVWr96pexQrsOMmoqCYN28Lhgz5GJs29UXx4oV0jxP2eB03Ebmia9d5\nKF/+Kowc2UL3KGGPL07C/M7KTczCwSwcwchi3LiWmD37KyxfviPgx9LJ9OPCmsWdlZWlewRjMAsH\ns3AEI4uyZYtjwoQHkZiYjpMns4MwlR6mHxfWLO7ffvtN9wjGYBYOZuEIVhZt296KO+4ojxdeWB6U\nx9PB9OPCmsVNRO4ZO7YlkpM3YePGvbpH8SRrFveOHTt0j2AMZuFgFo5gZlG+fAn8+99N8dZbnwXt\nMd1k+nHhylUlIX0CIiKP0nY5IBERBZc1VQkRkVdwcRMRhRnrFreIPCUifhG5RvcsuojIayKyVUQ+\nF5FUESmteya3iUgLEdkmIt+IyDO659FFRCqLyDIR+UpEvhSRAbpn0k1EIkVkk4ik657lUqxa3CJS\nGUBTAD/onkWzDwDUVErdAeBrAIM1z+MqEYkEMA5ACwA1AHQVkep6p9LmDIAnlVI1AdQF8LjFWZwz\nEMAWAMa+AGjV4gbwvwD+pnsI3ZRSHyqlzn1E91oAtr0D/t0AvlVK7VBKnQEwC0AbzTNpoZTap5TK\nOvufjwLYCqCi3qn0EZEbAMQDmAzgold0mMCaxS0ibQDsUkpt1j2LYXoBWKx7CJdVAnD++4/uOvs1\nq4lINIDayP3L3FYjAfwPAP/l7qhTlO4BgklEPgRQ/iLfeha5dUCz8+/uylCa5JHFEKVU+tn7PAvg\ntFJqhqvD6WfsP4F1EZESAOYCGHj2zNs6IvIQgP1KqU0iEqd7nrx4anErpZpe7OsiUgvATQA+FxEg\ntxr4TETuVkrtd3FE11wqi3NExIfcfxI+4MpAZtkNoPJ5tysj96zbSiJSCMA8ANOVUmm659HoXgCt\nRSQeQFEApURkmlIqQfNcf2LlL+CIyP8BiFVKHdQ9iw4i0gLA6wAaKaUO6J7HbSISBWA7cv/S2gNg\nHYCuSqmtWgfTQHLPZKYC+EUp9aTueUwhIo0APK2UaqV7louxpuO+gH1/W/3RWAAlAHx49rKnCboH\ncpNSKhvAEwDeR+7VA7NtXNpn1QfwCIDGZ4+FTWf/YieD94SVZ9xEROHM1jNuIqKwxcVNRBRmuLiJ\niMIMFzcRUZjh4iYiCjNc3EREYYaLm4gozHBxExGFmf8HY9oiPUvgyNwAAAAASUVORK5CYII=\n",
       "text": [
        "<matplotlib.figure.Figure at 0x7f661d5bd750>"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Draw Elliptic Curve over Finite field of (prime) order n:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(0, p):\n",
      "    y2 = (pow(i, 3) + i * a + b) % p\n",
      "    y = sqrt(y2)\n",
      "    if y % 1 == 0:\n",
      "        y =  prime_mod_sqrt(y2, p)\n",
      "        for yy in y:\n",
      "            print '(%d, %d)' % (i, yy)\n",
      "            plt.plot(i, yy, 'ro')\n",
      "print '(Inf)'\n",
      "\n",
      "plt.axis([-1, 5, -1, 5])\n",
      "plt.grid()\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(0, 1)\n",
        "(0, 4)\n",
        "(1, 3)\n",
        "(1, 2)\n",
        "(3, 3)\n",
        "(3, 2)\n",
        "(Inf)\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAEACAYAAACqOy3+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAEOFJREFUeJzt3G9sXQd5x/Hv0wQa/lsaqB0jkidrk2BiMtPUTcDKRVPi\n0rAxpE0bEkLeC14xO5oYQmva8YJWvNgLooSX/PHYJpjExLRi0ThALi6aVNStEX/SbmAtUsNagwRs\nqpCrUp69sJO6bZo4Odc+5zzn+5Es33N9c/38dNonNz+f68hMJEn9c0PbA0iSro8LXJJ6ygUuST3l\nApeknnKBS1JPucAlqaf2N32CiDgP/B/wNPBUZt7S9DklSVfXeIEDCYwy88cTeC5J0g5NqkKJCT2P\nJGmHJrHAE/hKRDwYEe+fwPNJknZgEhXKWzLzsYh4DXA6Ih7JzPsn8LySpCtovMAz87Gtzz+KiC8C\ntwCXFnhE+MtWJOk6ZOYV6+lGFUpEvDQiXrF1+2XAYeDblxmi7MdHPvKR1mcwn9nMV+9jJ5q+Ar8J\n+GJEXHyuf8zMlYbP2Svnz59ve4RdVTlf5WxgviFotMAz87+B2QnNIkm6Br4Ts6H5+fm2R9hVlfNV\nzgbmG4LYaddy3d8gInf7e0hSNRFB7uYPMQXj8bjtEXZV5XyVs4H5hsAFLkk9ZYUiSR1khSJJhbnA\nG6rew1XOVzkbmG8IXOCS1FN24JLUQXbgklSYC7yh6j1c5XyVs4H5hsAFLkk9ZQcuSR1kBy5JhbnA\nG6rew1XOVzkbmG8IXOCS1FN24JLUQXbgklSYC7yh6j1c5XyVs4H5hsAFLkk9ZQcuSR1kBy5JhbnA\nG6rew1XOVzkbmG8IXOCS1FN24JLUQXbgklSYC7yh6j1c5XyVs4H5hsAFLkk9NZEOPCL2AQ8CFzLz\nD57zNTtwSbpGe9mBHwXOAW5qSdojjRd4RLwOuB34JHDFvy0qWV1e5s65OeZnZ7lzbo7V5eW2R9oV\nlXvGytnAfEOwfwLP8XHgQ8ArJ/BcvbC6vMypo0e5Z22NMTACjq2tAXDrkSMtTiZpSBp14BHxTuAd\nmfmBiBgBHxxCB37n3Bx3r6w87/675ub46H33tTCRpGp20oE3fQX+ZuAPI+J24ADwyoj4bGa+b/uD\n5ufnmZ6eBmBqaorZ2VlGoxHwzD+D+nR8YX39Urbx1ucRsG9joxPzeeyxx/07Ho/HLC0tAVzal1eV\nmRP5AN4G3HuZ+7OaY4cPZ0Im5Jmtzwl559xc26NN3JkzZ9oeYddUzpZpvr7b2p1X3LuTvg68Vlfy\nAg4vLnJsZuZZ990xM8OhhYWWJpI0RP4ulOu0urzM6ZMn2bexwdMHDnBoYcEfYEqamJ104C5wSeog\nf5nVHrj4Q4iqKuernA3MNwQucEnqKSsUSeogKxRJKswF3lD1Hq5yvsrZwHxD4AKXpJ6yA5ekDrID\nl6TCXOANVe/hKuernA3MNwQucEnqKTtwSeogO3BJKswF3lD1Hq5yvsrZwHxD4AKXpJ6yA5ekDrID\nl6TCXOANVe/hKuernA3MNwQucEnqKTtwSeogO3BJKswF3lD1Hq5yvsrZwHxD4AKXpJ6yA5ekDrID\nl6TCXOANVe/hKuernA3MNwQucEnqKTtwSeogO3BJKqzRAo+IAxHxQEScjYhzEfGxSQ3WF9V7uMr5\nKmcD8w3B/iZ/ODM3IuLtmfmziNgPfCMi3pqZ35jQfGrJ6vIyKydOcGF9na/cdBOHFxe59ciRtsfS\nDnjuhqPRAgfIzJ9t3XwxsA/4cdPn7JPRaNT2CBO3urzMqaNHuWdt7dJ9x7ZuV1oEnrt+q3j+rlXj\nDjwiboiIs8A6cCYzzzUfS21aOXHiWQsA4J61NU6fPNnSRNopz92wTOIV+C+A2Yh4FXAqIkaZOd7+\nmPn5eaanpwGYmppidnb20t+eF3usvh4fP368VJ7xeMyF9XUuOg7MAiNg38ZGJ+ab1PH2DrUL80zi\n+ML6OmM2z9cz6TbPXRfm8/xdOc/S0hLApX15VZk5sQ/gLuCvnnNfVnbmzJm2R5i4Y4cPZ0Im5Jmt\nzwl559xc26NNlOeu3yqev+22ducVd27Tq1BeHRFTW7dfAhwCHmrynH1z8W/SSg4vLnJsZgbYfCUH\ncMfMDIcWFlqbaTd47vqt4vm7Vo3eyBMRbwT+js0u/Qbg7zPzb5/zmGzyPdSO1eVlTp88yb6NDZ4+\ncIBDCwvlfghWleeuhp28kcd3YjY0Ho9LvxKonK9yNjBf3/lOTEkqzFfgktRBvgKXpMJc4A1tvxa1\nosr5KmcD8w2BC1ySesoOXJI6yA5ckgpzgTdUvYernK9yNjDfELjAJamn7MAlqYPswCWpMBd4Q9V7\nuMr5KmcD8w2BC1ySesoOXJI6yA5ckgpzgTdUvYernK9yNjDfELjAJamn7MAlqYPswCWpMBd4Q9V7\nuMr5KmcD8w2BC1ySesoOXJI6yA5ckgpzgTdUvYernK9yNjDfELjAJamn7MAlqYPswCWpMBd4Q9V7\nuMr5KmcD8w1BowUeEQcj4kxEfDcivhMRi5MaTJJ0ZY068Ii4Gbg5M89GxMuBfwf+KDMf3vYYO/Ae\nWl1eZuXECfY/+SQ/v/FGDi8ucuuRI22PpR3w3NWwkw58f5NvkJmPA49v3X4iIh4GXgs8fMU/qE5b\nXV7m1NGj3LO2dum+Y1u3XQTd5rkblol14BExDbwJeGBSz9kHFXu4lRMnLi2A8dZ996ytcfrkydZm\n2g2eu36reP6uVaNX4Bdt1SdfAI5m5hPP/fr8/DzT09MATE1NMTs7y2g0Ap45CX09Pnv2bKfmmcTx\nhfV1Ljq79XkE7NvY6MR8Hr/w8YX1dcZsni94Zonv29joxHwev/DxeDxmaWkJ4NK+vJrG14FHxIuA\nLwFfzszjl/m6HXjP3Dk3x90rK8+7/665OT56330tTKSd8tzVsevXgUdEAJ8Czl1ueaufDi8ucmxm\n5ln33TEzw6GFhZYm0k557oal6VUobwVWgW8BF5/orzPzvm2PKf0KfDweX/rnUCWry8ucPnmSRx9/\nnIM338yhhYVyPwTz3PVb1fN30V5chfINfDNQSbceOcKtR46U/5+kIs/dcPi7UCSpg/xdKJJUmAu8\noYuXAVVVOV/lbGC+IXCBS1JP2YFLUgfZgUtSYS7whqr3cJXzVc4G5hsCF7gk9ZQduCR1kB24JBXm\nAm+oeg9XOV/lbGC+IXCBS1JP2YFLUgfZgUtSYS7whqr3cJXzVc4G5hsCF7gk9ZQduCR1kB24JBXm\nAm+oeg9XOV/lbGC+IXCBS1JP2YFLUgfZgUtSYS7whqr3cJXzVc4G5hsCF7gk9ZQduCR1kB24JBXm\nAm+oeg9XOV/lbGC+IXCBS1JPNe7AI+LTwBHgh5n5xst83Q5ckq7RTjrwSSzw3wOeAD47pAW+urzM\nyokT7H/ySX5+440cXlzk1iNH2h5LUhF78kPMzLwf+EnT5+mT1eVlTh09yt0rK4y+/nXuXlnh1NGj\nrC4vtz3axFXuGStnA/MNgR34dVg5cYJ71taedd89a2ucPnmypYkkDdH+vfgm8/PzTE9PAzA1NcXs\n7Cyj0Qh45m/RPh1fWF9/Vr4xMAL2bWx0Yr5JHl+8ryvzTPJ4NBp1ah7zDTvfeDxmaWkJ4NK+vJqJ\nvJEnIqaBe4fSgd85N8fdKyvPu/+uuTk+et99LUwkqRrfyLNLDi8ucmxmBth89Q1wx8wMhxYWWptp\nt1x8hVBR5WxgviFoXKFExOeAtwG/FBGPAn+TmZ9pPFmHXbza5K6TJ3n08cf56s03c9vCglehSNpT\n/i4USeogKxRJKswF3lD1Hq5yvsrZwHxD4AKXpJ6yA5ekDrIDl6TCXOANVe/hKuernA3MNwQucEnq\nKTtwSeogO3BJKswF3lD1Hq5yvsrZwHxD4AKXpJ6yA5ekDrIDl6TCXOANVe/hKuernA3MNwQucEnq\nKTtwSeogO3BJKswF3lD1Hq5yvsrZwHxD4AKXpJ6yA5ekDrIDl6TCXOANVe/hKuernA3MNwQucEnq\nKTtwSeogO3BJKswF3lD1Hq5yvsrZwHxD4AKXpJ6yA5ekDtqTDjwibouIRyLiexHx4abPJ0namUYL\nPCL2AZ8AbgPeALwnIl4/icH6onoPVzlf5WxgviFo+gr8FuD7mXk+M58CPg+8q/lYkqSradSBR8Qf\nA3OZ+f6t4/cCv5OZC9seYwcuSddoLzpwN7MktWR/wz//A+DgtuODwIXnPmh+fp7p6WkApqammJ2d\nZTQaAc/0WH09Pn78eKk8Q8q3vUPtwjzmG3a+8XjM0tISwKV9eTVNK5T9wH8Cvw/8D/BN4D2Z+fC2\nx5SuUMbj8aWTUVHlfJWzgfn6bicVSuPrwCPiHcBxYB/wqcz82HO+XnqBS9Ju2JMFvoMhXOCSdI38\nZVZ7YHsPV1HlfJWzgfmGwAUuST1lhSJJHWSFIkmFucAbqt7DVc5XORuYbwhc4JLUU3bgktRBduCS\nVJgLvKHqPVzlfJWzgfmGwAUuST1lBy5JHWQHLkmFucAbqt7DVc5XORuYbwhc4JLUU3bgktRBduCS\nVJgLvKHqPVzlfJWzgfmGwAUuST1lBy5JHWQHLkmFucAbqt7DVc5XORuYbwhc4JLUU3bgktRBduCS\nVJgLvKHqPVzlfJWzgfmGwAUuST1lBy5JHWQHLkmFXfcCj4g/iYjvRsTTEfFbkxyqT6r3cJXzVc4G\n5huCJq/Avw28G1id0Cy9dPbs2bZH2FWV81XOBuYbgv3X+wcz8xHY7GmG7Kc//WnbI+yqyvkqZwPz\nDYEduCT11BVfgUfEaeDmy3zpjsy8d3dG6pfz58+3PcKuqpyvcjYw3xA0vowwIs4AH8zM/3iBr3sN\noSRdh6tdRnjdHfhzvOA3udoAkqTr0+QywndHxKPA7wLLEfHlyY0lSbqaXX8npiRpd+zJVSgV3/QT\nEbdFxCMR8b2I+HDb80xSRHw6ItYj4tttz7IbIuJgRJzZ+m/yOxGx2PZMkxQRByLigYg4GxHnIuJj\nbc80aRGxLyIeiohyF1NExPmI+NZWvm9e6bF7dRlhqTf9RMQ+4BPAbcAbgPdExOvbnWqiPsNmtqqe\nAv4yM3+DzQrwA5XOX2ZuAG/PzFngN4G3R8RbWx5r0o4C54CKFUICo8x8U2becqUH7skCz8xHMvO/\n9uJ77ZFbgO9n5vnMfAr4PPCulmeamMy8H/hJ23Pslsx8PDPPbt1+AngYeG27U01WZv5s6+aLgX3A\nj1scZ6Ii4nXA7cAnucIFFD23o1y+kef6/Arw6LbjC1v3qWciYhp4E/BAu5NMVkTcEBFngXXgTGae\na3umCfo48CHgF20PsksS+EpEPBgR77/SAyd1GeHQ3vRT8Z9tgxMRLwe+ABzdeiVeRmb+ApiNiFcB\npyJilJnjlsdqLCLeCfwwMx+KiFHb8+ySt2TmYxHxGuB0RDyy9a/i55nYAs/MQ5N6rh74AXBw2/FB\nNl+Fqyci4kXAPwP/kJn/0vY8uyUz/zciloHfBsYtjzMJbwb+MCJuBw4Ar4yIz2bm+1qea2Iy87Gt\nzz+KiC+yWdledoG3UaFU6KweBH4tIqYj4sXAnwL/2vJM2qHY/A1snwLOZebxtueZtIh4dURMbd1+\nCXAIeKjdqSYjM+/IzIOZ+avAnwFfq7S8I+KlEfGKrdsvAw6zeRHIZe3VZYSl3vSTmT8H/gI4xeZP\nwv8pMx9ud6rJiYjPAf8G/HpEPBoRf972TBP2FuC9bF6d8dDWR6Wrbn4Z+NpWB/4AcG9mfrXlmXZL\ntTrzJuD+befuS5m58kIP9o08ktRTXoUiST3lApeknnKBS1JPucAlqadc4JLUUy5wSeopF7gk9ZQL\nXJJ66v8BWzmCllDDTc4AAAAASUVORK5CYII=\n",
       "text": [
        "<matplotlib.figure.Figure at 0x7f661d44d550>"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Helper function:\n",
      "SQRT mod p is nontrivial, so we ask the Internet:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# via http://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root\n",
      "def legendre_symbol(a, p):\n",
      "    \"\"\"\n",
      "    Legendre symbol\n",
      "    Define if a is a quadratic residue modulo odd prime\n",
      "    http://en.wikipedia.org/wiki/Legendre_symbol\n",
      "    \"\"\"\n",
      "    ls = pow(a, (p - 1)/2, p)\n",
      "    if ls == p - 1:\n",
      "        return -1\n",
      "    return ls\n",
      "\n",
      "def prime_mod_sqrt(a, p):\n",
      "    \"\"\"\n",
      "    Square root modulo prime number\n",
      "    Solve the equation\n",
      "        x^2 = a mod p\n",
      "    and return list of x solution\n",
      "    http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm\n",
      "    \"\"\"\n",
      "    a %= p\n",
      "\n",
      "    # Simple case\n",
      "    if a == 0:\n",
      "        return [0]\n",
      "    if p == 2:\n",
      "        return [a]\n",
      "\n",
      "    # Check solution existence on odd prime\n",
      "    if legendre_symbol(a, p) != 1:\n",
      "        return []\n",
      "\n",
      "    # Simple case\n",
      "    if p % 4 == 3:\n",
      "        x = pow(a, (p + 1)/4, p)\n",
      "        return [x, p-x]\n",
      "\n",
      "    # Factor p-1 on the form q * 2^s (with Q odd)\n",
      "    q, s = p - 1, 0\n",
      "    while q % 2 == 0:\n",
      "        s += 1\n",
      "        q //= 2\n",
      "\n",
      "    # Select a z which is a quadratic non resudue modulo p\n",
      "    z = 1\n",
      "    while legendre_symbol(z, p) != -1:\n",
      "        z += 1\n",
      "    c = pow(z, q, p)\n",
      "\n",
      "    # Search for a solution\n",
      "    x = pow(a, (q + 1)/2, p)\n",
      "    t = pow(a, q, p)\n",
      "    m = s\n",
      "    while t != 1:\n",
      "        # Find the lowest i such that t^(2^i) = 1\n",
      "        i, e = 0, 2\n",
      "        for i in xrange(1, m):\n",
      "            if pow(t, e, p) == 1:\n",
      "                break\n",
      "            e *= 2\n",
      "\n",
      "        # Update next value to iterate\n",
      "        b = pow(c, 2**(m - i - 1), p)\n",
      "        x = (x * b) % p\n",
      "        t = (t * b * b) % p\n",
      "        c = (b * b) % p\n",
      "        m = i\n",
      "\n",
      "    return [x, p-x]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}