Benchmark isogeny.is_cyclic

Benchmark_is_cyclic.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3fcac589-d69e-4c06-a4fe-c3efd7ab0854",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-02-18T11:51:05.924349Z",
     "iopub.status.busy": "2024-02-18T11:51:05.924222Z",
     "iopub.status.idle": "2024-02-18T11:51:05.927283Z",
     "shell.execute_reply": "2024-02-18T11:51:05.926975Z",
     "shell.execute_reply.started": "2024-02-18T11:51:05.924334Z"
    }
   },
   "outputs": [],
   "source": [
    "from sage.all import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a0967265-aa0c-42ea-b3f1-6584a40130dd",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-02-18T11:51:05.928242Z",
     "iopub.status.busy": "2024-02-18T11:51:05.927971Z",
     "iopub.status.idle": "2024-02-18T11:51:05.935811Z",
     "shell.execute_reply": "2024-02-18T11:51:05.935472Z",
     "shell.execute_reply.started": "2024-02-18T11:51:05.928228Z"
    }
   },
   "outputs": [],
   "source": [
    "def get_isogeny(degs):\n",
    "    E0 = EllipticCurve(GF((2**64+51)**2), [4, 0])\n",
    "    # randomize starting point\n",
    "    E0 = choice(E0.isogenies_prime_degree(17)).codomain()\n",
    "    full = choice(E0.isogenies_prime_degree(degs[0]))\n",
    "    for d in degs[1:]:\n",
    "        cands = full.codomain().isogenies_prime_degree(d)\n",
    "        shuffle(cands)\n",
    "        for phi in cands:\n",
    "            full2 = phi * full\n",
    "            if full2.is_cyclic():\n",
    "                full = full2\n",
    "                break\n",
    "            else:\n",
    "                pass\n",
    "        else:\n",
    "            raise\n",
    "    return full"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25b585ce-4c92-4d2e-8cb5-d126294d3785",
   "metadata": {},
   "source": [
    "Here \"factoring\"/prime testing, `phi.degree()` and j-invariant computations are dominating (with optimizations):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "643ab9e3-1eab-464f-ae35-cda37abbe700",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-02-18T11:51:05.936608Z",
     "iopub.status.busy": "2024-02-18T11:51:05.936335Z",
     "iopub.status.idle": "2024-02-18T11:51:45.409404Z",
     "shell.execute_reply": "2024-02-18T11:51:45.408973Z",
     "shell.execute_reply.started": "2024-02-18T11:51:05.936594Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12.8 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "13 µs ± 153 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "12.9 µs ± 321 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "4.76 ms ± 74.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "4.66 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "phi = get_isogeny([2, 2, 2, 2, 3, 3, 3, 3])\n",
    "%timeit phi.is_cyclic()\n",
    "%timeit phi.is_cyclic(_check_j=True, _reduce_kernel=True)\n",
    "%timeit phi.is_cyclic(_check_j=True, _reduce_kernel=False)\n",
    "%timeit phi.is_cyclic(_check_j=False, _reduce_kernel=True)\n",
    "%timeit phi.is_cyclic(_check_j=False, _reduce_kernel=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4e3b479-1256-4911-b296-1b7b7e8da4a6",
   "metadata": {},
   "source": [
    "Intermediate case:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d3226ef2-63de-4206-b44c-16094e8138ab",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-02-18T11:51:45.410290Z",
     "iopub.status.busy": "2024-02-18T11:51:45.410063Z",
     "iopub.status.idle": "2024-02-18T11:52:04.913744Z",
     "shell.execute_reply": "2024-02-18T11:52:04.913064Z",
     "shell.execute_reply.started": "2024-02-18T11:51:45.410265Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.9 ms ± 252 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "3.81 ms ± 291 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "3.56 ms ± 166 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "6.33 ms ± 341 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "5.88 ms ± 339 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "phi = get_isogeny([2, 2, 2, 3, 2, 3, 3, 3])\n",
    "%timeit phi.is_cyclic()\n",
    "%timeit phi.is_cyclic(_check_j=True, _reduce_kernel=True)\n",
    "%timeit phi.is_cyclic(_check_j=True, _reduce_kernel=False)\n",
    "%timeit phi.is_cyclic(_check_j=False, _reduce_kernel=True)\n",
    "%timeit phi.is_cyclic(_check_j=False, _reduce_kernel=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "141dbbda-25fa-4c3d-b430-2e64a71596aa",
   "metadata": {},
   "source": [
    "Worst case (no j-invariant checks):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "2eddb52c-f5fd-40ae-b539-a57cc54ce5e8",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-02-18T11:52:04.914415Z",
     "iopub.status.busy": "2024-02-18T11:52:04.914292Z",
     "iopub.status.idle": "2024-02-18T11:52:38.211456Z",
     "shell.execute_reply": "2024-02-18T11:52:38.211013Z",
     "shell.execute_reply.started": "2024-02-18T11:52:04.914402Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.26 ms ± 228 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "8.26 ms ± 175 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "8.17 ms ± 145 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "8.22 ms ± 136 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n",
      "7.76 ms ± 106 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "phi = get_isogeny([2, 3, 2, 2, 3, 3, 2, 3])\n",
    "%timeit phi.is_cyclic()\n",
    "%timeit phi.is_cyclic(_check_j=True, _reduce_kernel=True)\n",
    "%timeit phi.is_cyclic(_check_j=True, _reduce_kernel=False)\n",
    "%timeit phi.is_cyclic(_check_j=False, _reduce_kernel=True)\n",
    "%timeit phi.is_cyclic(_check_j=False, _reduce_kernel=False)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageDev",
   "language": "python",
   "name": "sagedev"
  },
  "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}