Created
February 18, 2024 11:51
-
-
Save hellman/409ba128c67d6887c9a130c19b66f01a to your computer and use it in GitHub Desktop.
Revisions
-
hellman created this gist
Feb 18, 2024 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,207 @@ { "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 }