alcoholic to elliptic

alcecc.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 203,
   "id": "67d3c30f-ea10-4fed-82b2-f57f3ce34ce9",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:50.780668Z",
     "iopub.status.busy": "2024-12-30T18:42:50.778630Z",
     "iopub.status.idle": "2024-12-30T18:42:50.791718Z",
     "shell.execute_reply": "2024-12-30T18:42:50.788828Z",
     "shell.execute_reply.started": "2024-12-30T18:42:50.780556Z"
    }
   },
   "outputs": [],
   "source": [
    "from vuln import *\n",
    "base = normalize(base)\n",
    "zero = normalize(zero)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7b654f1-c878-4596-a263-18dee1e7da43",
   "metadata": {},
   "source": [
    "Interpolate the curve:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "id": "8c3beeee-e536-4df5-8233-ffdc2fddb23a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:43:02.674567Z",
     "iopub.status.busy": "2024-12-30T18:43:02.674045Z",
     "iopub.status.idle": "2024-12-30T18:43:03.075747Z",
     "shell.execute_reply": "2024-12-30T18:43:03.074938Z",
     "shell.execute_reply.started": "2024-12-30T18:43:02.674545Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Vector space of degree 55 and dimension 1 over Finite Field of size 1349317116055496347935183323829721306283718936287\n",
       "Basis matrix:\n",
       "1 x 55 dense matrix over Finite Field of size 1349317116055496347935183323829721306283718936287"
      ]
     },
     "execution_count": 204,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deg = 9  # total degree\n",
    "monos = []\n",
    "for i in range(deg + 1):\n",
    "    for j in range(deg + 1 - i):\n",
    "        monos.append((i, j))\n",
    "\n",
    "gen = base\n",
    "pt = gen\n",
    "data = []\n",
    "for i in range(2, len(monos)+5):\n",
    "    pt = normalize(add(pt, gen))\n",
    "    # first 2 affine coordinates (since normalized)\n",
    "    xs = pt[1:3]\n",
    "    row = [\n",
    "        prod(x**e for x, e in zip(xs, es))\n",
    "        for es in monos\n",
    "    ]\n",
    "    data.append(row)\n",
    "\n",
    "mat = matrix(GF(p), data)\n",
    "rk = mat.right_kernel()\n",
    "rk"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eff5a9e2-0398-4246-9723-9d698e823a3a",
   "metadata": {},
   "source": [
    "We have 1 relation. Let's reconstruct the polynomial:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "id": "88e0fd47-6dcd-4d96-b65c-d398e71cfdd5",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:43:14.161046Z",
     "iopub.status.busy": "2024-12-30T18:43:14.160447Z",
     "iopub.status.idle": "2024-12-30T18:43:14.169249Z",
     "shell.execute_reply": "2024-12-30T18:43:14.168374Z",
     "shell.execute_reply.started": "2024-12-30T18:43:14.160993Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1290422967115358566266590777853979389598846205666*x^9 + 577379728613493404559030761507813969909021892646*x^8*y + 1243591010103894033874931036346746932772777061809*x^7*y^2 + 802820083981430427359276555319159610338384321310*x^6*y^3 + 1232868555484873001243395461503072086003412440799*x^5*y^4 + 1137483247688794514748538208782775965405225990619*x^4*y^5 + 1098058599413970905114088603603094763519900428362*x^3*y^6 + 521491890352857306282988928668018529753246687918*x^2*y^7 + 1260410534149648293496028865098499989940595729366*x*y^8 + 842782215788949538115688200389919742540609803787*y^9 + 148652987333517774706626469674067058579773949330*x^8 + 704072252718806103236352463412377087321883390307*x^7*y + 969550413402677076033559674669970647059658559811*x^6*y^2 + 914504036011531344190663463577438459411937411774*x^5*y^3 + 1033218420556944139578595749588116845242280409381*x^4*y^4 + 184031932531709285127717045341600269148663709973*x^3*y^5 + 522977194194553309971023227001628408398393067665*x^2*y^6 + 526942879502285241403569507339108847069792634647*x*y^7 + 17009683443167968083917508140397063144005599766*y^8 + 1206984109122888717952309707979157801919379180440*x^7 + 666646221516501167407644038840016851578513381070*x^6*y + 951883726405392312011964097975105374209885276989*x^5*y^2 + 645823893885258859236272557206945939990660011679*x^4*y^3 + 652478917929683952185569824651099051781512339594*x^3*y^4 + 1147786275280675470977066928226574352664312025618*x^2*y^5 + 511780223753123772491966598541792472900715927890*x*y^6 + 1242714503544177641576865227346261839104821592387*y^7 + 1119608915578092664931027342305520214618342542817*x^6 + 219465047216145355211916063856654026557709438956*x^5*y + 440868630139328723390887666440338107454072029138*x^4*y^2 + 884841851333430383561092868693582396236627016059*x^3*y^3 + 1074014609963442522186489331612835495173528091285*x^2*y^4 + 632915613590123123726310817491414055711594675603*x*y^5 + 360153763588701435270187378411040859528860441053*y^6 + 1312967192351481772025312036859334531188871704480*x^5 + 370542169622946669850165726450244003690345761279*x^4*y + 656709532575879601531214822345460775013507981650*x^3*y^2 + 511896697232660276092068265004006902231292911556*x^2*y^3 + 1070096180258818183515005064468343611321309367240*x*y^4 + 263411577279111351351767233648575110516269742212*y^5 + 713108719042207102637623462493952328733444108683*x^4 + 1060825606481194737492064176412987247144297085300*x^3*y + 822052194696345751139804593504655648005104702647*x^2*y^2 + 1114929232706754066135276260250399322468687032746*x*y^3 + 195141015153221254035344067042632562110836626787*y^4 + 1015616695064203722876228358981056451279442812366*x^3 + 282436498401508215802299272916904057251062041895*x^2*y + 271013532598523925647618619209267801341794393684*x*y^2 + 1311804110854716862303352250687716364825835352313*y^3 + 313489185139358333253607840927329962919747187302*x^2 + 30541526957092351611848006450395151067734672851*x*y + 1011318165555535557007129300549155976507803763648*y^2 + 379343306669746198394996028074861013023099496937*x + 902827703943354025101323492246819516991375781791*y + 1\n",
      "[x^9, x^8*y, x^7*y^2, x^6*y^3, x^5*y^4, x^4*y^5, x^3*y^6, x^2*y^7, x*y^8, y^9, x^8, x^7*y, x^6*y^2, x^5*y^3, x^4*y^4, x^3*y^5, x^2*y^6, x*y^7, y^8, x^7, x^6*y, x^5*y^2, x^4*y^3, x^3*y^4, x^2*y^5, x*y^6, y^7, x^6, x^5*y, x^4*y^2, x^3*y^3, x^2*y^4, x*y^5, y^6, x^5, x^4*y, x^3*y^2, x^2*y^3, x*y^4, y^5, x^4, x^3*y, x^2*y^2, x*y^3, y^4, x^3, x^2*y, x*y^2, y^3, x^2, x*y, y^2, x, y, 1]\n"
     ]
    }
   ],
   "source": [
    "xs = PolynomialRing(GF(p), names=\"x, y\").gens()\n",
    "for sol in rk.matrix():\n",
    "    assert len(sol) == len(monos)\n",
    "    poly = []\n",
    "    for c, es in zip(sol, monos):\n",
    "        mono = prod(x**e for x, e in zip(xs, es))\n",
    "        poly.append(c * mono)\n",
    "    poly = sum(poly)\n",
    "    print(poly)\n",
    "    print(poly.monomials())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "feee9778-9c7b-429f-9d4b-e88b4d45bb41",
   "metadata": {},
   "source": [
    "Sample lines until we get all roots in a small extension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "id": "f29a53dc-c36f-424a-8c90-d1767f44f31b",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:43:26.514414Z",
     "iopub.status.busy": "2024-12-30T18:43:26.513321Z",
     "iopub.status.idle": "2024-12-30T18:43:27.200799Z",
     "shell.execute_reply": "2024-12-30T18:43:27.199791Z",
     "shell.execute_reply.started": "2024-12-30T18:43:26.514316Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6, [1, 1, 2, 2, 2, 2, 3, 3, 3, 6])"
      ]
     },
     "execution_count": 208,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x, y = poly.parent().gens()\n",
    "O = Ox, Oy = zero[1:3]\n",
    "\n",
    "while True:\n",
    "    lines = []\n",
    "    for _ in range(3):\n",
    "        a = GF(p).random_element()\n",
    "        b = GF(p).random_element()\n",
    "        lines.append(a*x + b*y - a*Ox - b*Oy)\n",
    "        f = prod(lines)\n",
    "    \n",
    "    res = poly.sylvester_matrix(f, y).det()\n",
    "    degs = [fac.degree() for fac, _ in factor(res.univariate_polynomial())]\n",
    "    #print(lcm(degs), degs)\n",
    "    if lcm(degs) <= 6:\n",
    "        break\n",
    "lcm(degs), degs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "id": "342a8458-0697-4483-9b27-1e12c8a4b813",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:43:28.712971Z",
     "iopub.status.busy": "2024-12-30T18:43:28.712314Z",
     "iopub.status.idle": "2024-12-30T18:43:30.877682Z",
     "shell.execute_reply": "2024-12-30T18:43:30.877068Z",
     "shell.execute_reply.started": "2024-12-30T18:43:28.712941Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 209,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "roots = []\n",
    "rng = GF(p**lcm(degs))\n",
    "for rx, _ in res.univariate_polynomial().roots(ring=rng):\n",
    "    for ry, _ in f.change_ring(rng).subs(x=rx).univariate_polynomial().roots():\n",
    "        if poly(rx, ry) == 0:\n",
    "            #print(\"root\", rx, ry)\n",
    "            assert f(rx, ry) == 0\n",
    "            assert poly(rx, ry) == 0\n",
    "            roots.append((rx, ry))\n",
    "len(roots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "id": "c7d5bb84-00ef-438d-898f-23ec7faed224",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:03.795576Z",
     "iopub.status.busy": "2024-12-30T18:42:03.795025Z",
     "iopub.status.idle": "2024-12-30T18:42:03.804016Z",
     "shell.execute_reply": "2024-12-30T18:42:03.803080Z",
     "shell.execute_reply.started": "2024-12-30T18:42:03.795531Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 194,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "assert f(Ox, Oy) == 0\n",
    "assert poly(Ox, Oy) == 0\n",
    "roots.remove(O)\n",
    "len(roots)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "id": "13e43147-7cf8-43bd-8a3d-892fca4f922a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:04.378144Z",
     "iopub.status.busy": "2024-12-30T18:42:04.376675Z",
     "iopub.status.idle": "2024-12-30T18:42:04.386287Z",
     "shell.execute_reply": "2024-12-30T18:42:04.385120Z",
     "shell.execute_reply.started": "2024-12-30T18:42:04.378043Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (6, 0), (6, 1), (6, 2), (6, 3), (7, 0), (7, 1), (7, 2), (8, 0), (8, 1), (9, 0)]\n"
     ]
    }
   ],
   "source": [
    "monos = []\n",
    "deg = 10\n",
    "for i in range(deg):\n",
    "    for j in range(deg-i):\n",
    "        monos.append((i,j))\n",
    "print(monos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "id": "a42b2f47-473e-4961-a7a8-c1b424ef2da2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:04.894055Z",
     "iopub.status.busy": "2024-12-30T18:42:04.893114Z",
     "iopub.status.idle": "2024-12-30T18:42:04.905189Z",
     "shell.execute_reply": "2024-12-30T18:42:04.903874Z",
     "shell.execute_reply.started": "2024-12-30T18:42:04.893961Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 196,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(monos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "id": "f7bc7e89-ddd0-4e45-ac39-8da23a58f51e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:05.597508Z",
     "iopub.status.busy": "2024-12-30T18:42:05.596174Z",
     "iopub.status.idle": "2024-12-30T18:42:05.937193Z",
     "shell.execute_reply": "2024-12-30T18:42:05.936311Z",
     "shell.execute_reply.started": "2024-12-30T18:42:05.597406Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(24, 55, ':', 24)"
      ]
     },
     "execution_count": 197,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat = []\n",
    "for rx, ry in roots:\n",
    "    row = []\n",
    "    for ex, ey in monos:\n",
    "        row.append(rx**ex * ry**ey)\n",
    "    mat.append(row)\n",
    "mat = matrix(rng, mat)\n",
    "mat.nrows(), mat.ncols(), \":\", mat.rank()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "id": "943cf444-9a48-44e6-a4eb-de49fbcc492d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:06.900769Z",
     "iopub.status.busy": "2024-12-30T18:42:06.899790Z",
     "iopub.status.idle": "2024-12-30T18:42:07.079384Z",
     "shell.execute_reply": "2024-12-30T18:42:07.078697Z",
     "shell.execute_reply.started": "2024-12-30T18:42:06.900658Z"
    }
   },
   "outputs": [],
   "source": [
    "def row2func(row):\n",
    "    func = []\n",
    "    #print(row)\n",
    "    for coef, (ex, ey) in zip(row, monos):\n",
    "        func.append(coef * X**ex * Y**ey)\n",
    "    return sum(func)\n",
    "\n",
    "X,Y = rng['X,Y'].gens()\n",
    "rk = mat.right_kernel()\n",
    "for row in rk.matrix():\n",
    "    func = row2func(row)\n",
    "    #print(func.monomials())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "id": "5d930613-6f95-4970-b67d-6d54f2f94460",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:07.673050Z",
     "iopub.status.busy": "2024-12-30T18:42:07.672487Z",
     "iopub.status.idle": "2024-12-30T18:42:07.714635Z",
     "shell.execute_reply": "2024-12-30T18:42:07.713976Z",
     "shell.execute_reply.started": "2024-12-30T18:42:07.673004Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1024503049567184828221036818093981269892340451889*z6^5 + 846226262361345178767282546042721349806339093812*z6^4 + 1209598363721775499099263048184232012414798210279*z6^3 + 859012850873176582919818119561667407385708421529*z6^2 + 751596135068701825781055976327490109476969014919*z6 + 150369789309333405336940617665477506879771692878,\n",
       " 86017141173972623381424974040803816027659395918*z6^5 + 589644167898116502001553300271284407500106012283*z6^4 + 1220764599324148976202673642729123972360287144170*z6^3 + 411447882563551219418104083197450927163939257467*z6^2 + 1073905787946608490141335910313324704150035198943*z6 + 556169367678216389540621684606088349259470829753)"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g = row2func(rk.random_element())\n",
    "h = row2func(rk.random_element())\n",
    "g(*O), h(*O)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "id": "8aae4930-f5ab-4424-971f-570eeba1bb5d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:08.467937Z",
     "iopub.status.busy": "2024-12-30T18:42:08.467040Z",
     "iopub.status.idle": "2024-12-30T18:42:13.332803Z",
     "shell.execute_reply": "2024-12-30T18:42:13.332214Z",
     "shell.execute_reply.started": "2024-12-30T18:42:08.467851Z"
    }
   },
   "outputs": [],
   "source": [
    "vg = g(*O)\n",
    "vh = h(*O)\n",
    "\n",
    "cx = g - vg / vh * h\n",
    "cy = h\n",
    "cz = f\n",
    "\n",
    "assert cx(*O) == 0\n",
    "assert cy(*O) != 0\n",
    "assert cz(*O) == 0\n",
    "\n",
    "def morph(pt):\n",
    "    return cx(*pt), cy(*pt), cz(*pt)\n",
    "\n",
    "points = []\n",
    "for i in range(1, 100):\n",
    "    pt = scalarmul(base, i)\n",
    "    pt = normalize(pt)\n",
    "    pt = pt[1:3]\n",
    "    points.append(morph(pt))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "id": "4eef07f0-1539-42ef-b46e-8d4e90e90ca3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:13.964430Z",
     "iopub.status.busy": "2024-12-30T18:42:13.963610Z",
     "iopub.status.idle": "2024-12-30T18:42:17.916790Z",
     "shell.execute_reply": "2024-12-30T18:42:17.916190Z",
     "shell.execute_reply.started": "2024-12-30T18:42:13.964364Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "99 81 81\n"
     ]
    }
   ],
   "source": [
    "ms = []\n",
    "deg = 9\n",
    "for ey in range(deg):\n",
    "    for ex in range(deg):\n",
    "        ms.append((ex, ey))\n",
    "\n",
    "mat = []\n",
    "for px, py, pz in points:\n",
    "    px /= pz\n",
    "    py /= pz\n",
    "    row = []\n",
    "    for ex, ey in ms:\n",
    "        row.append(px**ex * py**ey)\n",
    "    mat.append(row)\n",
    "mat = matrix(mat)\n",
    "print(mat.nrows(), mat.ncols(), mat.rank())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "id": "215187aa-fb6b-4c32-83b9-58f8ba448db2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-30T18:42:23.569231Z",
     "iopub.status.busy": "2024-12-30T18:42:23.568474Z",
     "iopub.status.idle": "2024-12-30T18:42:23.787854Z",
     "shell.execute_reply": "2024-12-30T18:42:23.787192Z",
     "shell.execute_reply.started": "2024-12-30T18:42:23.569145Z"
    }
   },
   "outputs": [],
   "source": [
    "for root in roots:\n",
    "    assert g(*root) == h(*root) == 0\n",
    "    assert poly(*root) == 0\n",
    "    assert f(*root) == 0\n",
    "    assert root[0] != Ox"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageConda",
   "language": "sage",
   "name": "sageconda"
  },
  "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.12.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}