{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Tutorial\n", "\n", "## Isogenies\n", "\n", "Construct an isogeny from a generator of the kernel" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "12" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E = EllipticCurve(GF(11), [1, 0])\n", "g = E.gens()[0]\n", "g.order()" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0 : 0 : 1)" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "kernel = 6*g\n", "kernel" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11 to Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "I = E.isogeny(kernel)\n", "I" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "%display latex" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\$\\displaystyle \\left(\\frac{x^{2} + 1}{x}, \\frac{x^{2} y - y}{x^{2}}\\right)\$" ], "text/latex": [ "$\\displaystyle \\left(\\frac{x^{2} + 1}{x}, \\frac{x^{2} y - y}{x^{2}}\\right)$" ], "text/plain": [ "((x^2 + 1)/x, (x^2*y - y)/x^2)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "I.rational_maps()" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\$\\displaystyle y^2 = x^{3} + 7 x \$" ], "text/latex": [ "$\\displaystyle y^2 = x^{3} + 7 x $" ], "text/plain": [ "Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F = I.codomain()\n", "F" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We observe that the image curve has the same number of points, but not the same group structure" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\$\\displaystyle \\newcommand{\\ZZ}{\\Bold{Z}}\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{\\ZZ}{2\\ZZ} \\oplus \\frac{\\ZZ}{6\\ZZ}\$" ], "text/latex": [ "$\\displaystyle \\newcommand{\\ZZ}{\\Bold{Z}}\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{\\ZZ}{2\\ZZ} \\oplus \\frac{\\ZZ}{6\\ZZ}$" ], "text/plain": [ "Additive abelian group isomorphic to Z/6 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 7*x over Finite Field of size 11" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F.abelian_group()" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\$\\displaystyle \\newcommand{\\ZZ}{\\Bold{Z}}\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{\\ZZ}{12\\ZZ}\$" ], "text/latex": [ "$\\displaystyle \\newcommand{\\ZZ}{\\Bold{Z}}\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\frac{\\ZZ}{12\\ZZ}$" ], "text/plain": [ "Additive abelian group isomorphic to Z/12 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 11" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.abelian_group()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "%display plain" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The same example over the rationals" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Elliptic Curve defined by y^2 = x^3 + x over Rational Field" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E = EllipticCurve([1,0])\n", "E" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(0 : 0 : 1)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P = E.lift_x(0)\n", "P" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.order()" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "J = E.isogeny(P)\n", "F = J.codomain()\n", "F" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In (very) limited cases, Sage can compute the isogeny given the image curve and the degree" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "JJ = E.isogeny(None, codomain=F, degree=2)\n", "J == JJ" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Complex multiplication\n", "\n", "Sage capabilities around complex multiplications, and quadratic imaginary orders in particular, are a bit limited, but still useful." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Elliptic Curve defined by y^2 = x^3 + x over Rational Field" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E = EllipticCurve([1,0])\n", "E" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Test whether a curve has complex multiplication" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.has_cm()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Get the \"CM discriminant\", i.e. the discriminant of the order $\\mathcal{O}$ isomorphic to $\\mathrm{End}(E)$" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-4" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.cm_discriminant()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(ordinary) curves over finite fields and the Frobenius endomorphism" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 101" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E = EllipticCurve(GF(101), [1,2])\n", "E" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.j_invariant()" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.is_ordinary()" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.is_supersingular()" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^2 - 2*x + 101" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "chi = E.frobenius_polynomial()\n", "chi" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-400" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "chi.discriminant()" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.trace_of_frobenius()" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Order in Number Field in phi with defining polynomial x^2 - 2*x + 101" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "O = E.frobenius_order()\n", "O" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "O.is_maximal()" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-400" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "O.discriminant()" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Number Field in phi with defining polynomial x^2 - 2*x + 101" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K = O.number_field()\n", "K" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Gaussian Integers in Number Field in phi with defining polynomial x^2 - 2*x + 101" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "OK = K.maximal_order()\n", "OK" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-4" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "OK.discriminant()" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K.class_number()" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "OK.class_number()" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Class group of order 1 of Number Field in phi with defining polynomial x^2 - 2*x + 101" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K.class_group()" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "O.class_number()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Hilbert class polynomials\n", "\n", "The Hilbert class polynomial $H(-D)$ is the polynomial with coefficients in $ℤ$ whose roots are the $j$-invariants with CM by (the order of discriminant) $-D$." ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 - 1938773508354872717845384224*x^3 + 12869286863161864184636279443710336*x^2 - 19075061455767889406477974994607212544*x + 87448873738295790450948276123544550117376" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "H = hilbert_class_polynomial(-400)\n", "H" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "H.is_irreducible()" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + 7) * (x + 24) * (x + 64) * (x + 97)" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "H.change_ring(GF(101)).factor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exercises" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1\n", "\n", "Consider the curve" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [], "source": [ "E = EllipticCurve(GF(127), [97, 46])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "List all isogenies with kernel of size 43 (i.e., of degree 43) defined over $𝔽_{127}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We check the order of the curve. Necessarily $E(𝔽_{127}) \\simeq ℤ/129ℤ$." ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3 * 43" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factor(E.order())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We take a random point $P$ of order 43 and construct the isogeny $E → E/〈P〉$." ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "43\n" ] }, { "data": { "text/plain": [ "Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 + 97*x + 46 over Finite Field of size 127 to Elliptic Curve defined by y^2 = x^3 + 38*x + 16 over Finite Field of size 127" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ord = 1\n", "while ord != 43:\n", " P = 3*E.random_element()\n", " ord = P.order()\n", " print(ord)\n", "E.isogeny(P)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There is at least one $𝔽_{127}$-rational isogeny of degree 43, however there may be more. Indeed, an isogeny is rational if and only if $π(\\ker φ) = \\ker φ$.\n", "\n", "By studying the factorization of the division polynomial, we see it splits completely in $𝔽_{127^7}$. We move to the next question." ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(43) * (x + 5) * (x + 11) * (x + 13) * (x + 14) * (x + 16) * (x + 19) * (x + 28) * (x + 49) * (x + 56) * (x + 69) * (x + 72) * (x + 76) * (x + 81) * (x + 85) * (x + 92) * (x + 93) * (x + 95) * (x + 112) * (x + 113) * (x + 116) * (x + 125) * (x^7 + 46*x^5 + 110*x^4 + 27*x^3 + 12*x^2 + 41*x + 105) * (x^7 + 81*x^5 + 94*x^4 + 81*x^3 + 108*x^2 + 92*x + 6) * (x^7 + 123*x^5 + 36*x^4 + 62*x^3 + 57*x^2 + 96*x + 54) * (x^7 + 3*x^6 + 15*x^5 + 104*x^4 + 109*x^3 + 84*x^2 + 47*x + 82) * (x^7 + 3*x^6 + 67*x^5 + 44*x^4 + 81*x^3 + 71*x^2 + 60*x + 52) * (x^7 + 3*x^6 + 101*x^5 + 74*x^4 + 102*x^3 + 68*x^2 + 118*x + 5) * (x^7 + 5*x^6 + 35*x^5 + 46*x^4 + 49*x^3 + 80*x^2 + 70*x + 18) * (x^7 + 5*x^6 + 45*x^5 + 25*x^4 + 109*x^3 + 70*x^2 + 50*x + 41) * (x^7 + 5*x^6 + 95*x^5 + 126*x^4 + 118*x^3 + 11*x^2 + 79*x + 3) * (x^7 + 6*x^6 + 35*x^5 + 48*x^4 + 103*x^3 + 113*x^2 + 39*x + 64) * (x^7 + 7*x^6 + 41*x^5 + 29*x^4 + 23*x^3 + 123*x^2 + 116*x + 5) * (x^7 + 8*x^6 + 33*x^5 + 18*x^4 + 106*x^3 + 102*x^2 + 118*x + 90) * (x^7 + 9*x^6 + 55*x^5 + 36*x^4 + 71*x^3 + 111*x^2 + 74*x + 79) * (x^7 + 12*x^6 + 55*x^5 + 3*x^4 + 56*x^3 + 107*x^2 + 68*x + 124) * (x^7 + 13*x^6 + 48*x^5 + 29*x^4 + 46*x^3 + 43*x^2 + 102*x + 28) * (x^7 + 13*x^6 + 63*x^5 + 26*x^4 + 15*x^3 + 114*x^2 + 74*x + 4) * (x^7 + 14*x^6 + 53*x^5 + 54*x^4 + 43*x^3 + 18*x^2 + 108*x + 99) * (x^7 + 14*x^6 + 79*x^5 + 51*x^4 + 34*x^3 + 70*x^2 + 115*x + 81) * (x^7 + 15*x^6 + 107*x^5 + 86*x^4 + 111*x^3 + 120*x^2 + 94*x + 32) * (x^7 + 17*x^6 + 43*x^5 + 91*x^4 + 28*x^3 + 75*x^2 + 57*x + 30) * (x^7 + 17*x^6 + 53*x^5 + 10*x^4 + 19*x^3 + 97*x^2 + 16*x + 80) * (x^7 + 18*x^6 + 76*x^5 + 10*x^4 + 90*x^3 + 69*x^2 + 95*x + 27) * (x^7 + 18*x^6 + 103*x^5 + 68*x^4 + 30*x^3 + 84*x^2 + 103*x + 14) * (x^7 + 20*x^6 + 103*x^5 + 70*x^4 + 51*x^3 + 66*x^2 + 65*x + 48) * (x^7 + 21*x^6 + 25*x^5 + 22*x^4 + 56*x^3 + 90*x^2 + 10*x + 26) * (x^7 + 23*x^6 + 87*x^5 + 75*x^4 + 121*x^3 + 109*x^2 + 81*x + 113) * (x^7 + 27*x^6 + 50*x^5 + 57*x^4 + 86*x^3 + 107*x^2 + 44*x + 90) * (x^7 + 27*x^6 + 92*x^5 + 96*x^4 + 102*x^3 + 98*x^2 + 8*x + 110) * (x^7 + 30*x^6 + 45*x^5 + 77*x^4 + 66*x^3 + 63*x^2 + 110*x + 49) * (x^7 + 31*x^6 + 116*x^5 + 89*x^4 + 46*x^3 + 67*x^2 + 10*x + 28) * (x^7 + 32*x^6 + 59*x^5 + 83*x^3 + 36*x^2 + 99*x + 24) * (x^7 + 33*x^6 + 119*x^5 + 75*x^4 + 16*x^3 + 104*x^2 + 59*x + 123) * (x^7 + 35*x^6 + 32*x^5 + 114*x^4 + 114*x^3 + 2*x^2 + 27*x + 35) * (x^7 + 36*x^6 + 41*x^5 + 23*x^4 + 50*x^3 + 26*x^2 + 61*x + 11) * (x^7 + 38*x^6 + 34*x^5 + 86*x^4 + 74*x^3 + 51*x^2 + 28*x + 51) * (x^7 + 40*x^6 + 53*x^5 + 81*x^4 + 8*x^3 + 40*x^2 + 91*x + 105) * (x^7 + 42*x^6 + 35*x^5 + 6*x^4 + 25*x^3 + 113*x^2 + 57*x + 108) * (x^7 + 42*x^6 + 120*x^5 + 19*x^4 + 16*x^3 + 95*x^2 + 94*x + 126) * (x^7 + 45*x^6 + 60*x^5 + 92*x^4 + 54*x^3 + 101*x^2 + 34*x + 20) * (x^7 + 45*x^6 + 66*x^5 + 8*x^4 + 29*x^3 + 69*x^2 + 86*x + 115) * (x^7 + 47*x^6 + 63*x^5 + 44*x^4 + 104*x^3 + 115*x^2 + 49*x + 9) * (x^7 + 49*x^6 + 11*x^5 + 75*x^4 + 97*x^3 + 6*x^2 + 70*x + 78) * (x^7 + 49*x^6 + 18*x^5 + 112*x^4 + 51*x^3 + 43*x^2 + 30*x + 18) * (x^7 + 49*x^6 + 19*x^5 + 116*x^4 + 78*x^3 + 30*x^2 + 40*x + 125) * (x^7 + 49*x^6 + 43*x^5 + 81*x^4 + 28*x^3 + 54*x^2 + 29*x + 61) * (x^7 + 49*x^6 + 120*x^5 + 120*x^4 + 31*x^3 + 98*x^2 + 62*x + 7) * (x^7 + 50*x^6 + 45*x^5 + 111*x^4 + 45*x^3 + 82*x^2 + 94*x + 78) * (x^7 + 51*x^6 + 23*x^5 + 124*x^4 + 58*x^3 + 24*x + 39) * (x^7 + 53*x^6 + 96*x^5 + 112*x^4 + 53*x^3 + 23*x^2 + 79*x + 40) * (x^7 + 53*x^6 + 115*x^5 + 78*x^4 + 112*x^3 + 62*x^2 + 63*x + 39) * (x^7 + 57*x^6 + 92*x^5 + 68*x^4 + 18*x^3 + 50*x^2 + 97*x + 110) * (x^7 + 57*x^6 + 121*x^5 + 117*x^4 + 60*x^3 + 57*x^2 + 53*x + 31) * (x^7 + 60*x^6 + 71*x^5 + 59*x^4 + 6*x^3 + 54*x^2 + 35*x + 70) * (x^7 + 61*x^6 + 103*x^5 + 71*x^4 + 90*x^3 + 63*x^2 + 64*x + 111) * (x^7 + 63*x^6 + 18*x^5 + 20*x^4 + 26*x^3 + 59*x + 20) * (x^7 + 63*x^6 + 35*x^5 + 10*x^4 + 46*x^3 + 37*x^2 + 57*x + 80) * (x^7 + 63*x^6 + 79*x^5 + 50*x^4 + 89*x^3 + 3*x^2 + 18*x + 45) * (x^7 + 63*x^6 + 113*x^5 + 111*x^4 + 86*x^3 + 22*x^2 + 3*x + 67) * (x^7 + 64*x^6 + 26*x^5 + 109*x^4 + 17*x^3 + 46*x^2 + 68*x + 88) * (x^7 + 65*x^6 + 76*x^5 + 47*x^4 + 49*x^3 + 41*x^2 + 10*x + 1) * (x^7 + 65*x^6 + 81*x^5 + 15*x^4 + 78*x^3 + 123*x^2 + 17*x + 69) * (x^7 + 65*x^6 + 87*x^5 + 91*x^4 + 31*x^3 + 42*x^2 + 14*x + 46) * (x^7 + 67*x^6 + 70*x^5 + 83*x^4 + 109*x^3 + 98*x^2 + 123*x + 24) * (x^7 + 69*x^6 + 112*x^5 + 5*x^4 + 31*x^3 + 45*x^2 + 14*x + 125) * (x^7 + 70*x^6 + 62*x^4 + 86*x^3 + 79*x^2 + 55*x + 89) * (x^7 + 70*x^6 + 65*x^5 + 40*x^4 + 57*x^3 + 62*x^2 + 35*x + 66) * (x^7 + 70*x^6 + 114*x^5 + 2*x^3 + 50*x^2 + 75*x + 54) * (x^7 + 71*x^6 + 30*x^5 + 13*x^4 + 85*x^3 + 56*x^2 + 13*x + 29) * (x^7 + 71*x^6 + 72*x^5 + 32*x^4 + 22*x^3 + 113*x^2 + 114*x + 6) * (x^7 + 73*x^6 + 3*x^5 + 24*x^4 + 26*x^3 + x^2 + 52*x + 108) * (x^7 + 73*x^6 + 5*x^5 + 28*x^4 + 125*x^3 + 46*x^2 + 69*x + 43) * (x^7 + 74*x^6 + 97*x^5 + 112*x^4 + 47*x^3 + 29*x^2 + 26*x + 116) * (x^7 + 74*x^6 + 102*x^5 + 55*x^4 + 14*x^3 + 69*x^2 + 82*x + 14) * (x^7 + 74*x^6 + 107*x^5 + 115*x^4 + 119*x^3 + 16*x^2 + 35*x + 35) * (x^7 + 75*x^6 + 10*x^5 + 16*x^4 + 24*x^3 + 92*x^2 + 51*x + 2) * (x^7 + 75*x^6 + 65*x^5 + 67*x^4 + 4*x^3 + 45*x^2 + 40*x + 122) * (x^7 + 76*x^6 + 3*x^5 + 120*x^4 + 97*x^3 + 94*x^2 + 107*x + 63) * (x^7 + 76*x^6 + 49*x^5 + 74*x^4 + 81*x^3 + 44*x^2 + 92*x + 117) * (x^7 + 76*x^6 + 56*x^5 + 110*x^4 + 30*x^3 + 28*x^2 + 81*x + 67) * (x^7 + 77*x^6 + 29*x^5 + 100*x^4 + 120*x^3 + 55*x^2 + 86*x + 68) * (x^7 + 77*x^6 + 41*x^5 + 27*x^4 + 45*x^3 + 12*x^2 + 24*x + 67) * (x^7 + 77*x^6 + 49*x^5 + 85*x^4 + 94*x^3 + 27*x^2 + 37*x + 89) * (x^7 + 77*x^6 + 75*x^5 + 23*x^4 + 29*x^3 + 70*x^2 + 68*x + 1) * (x^7 + 78*x^6 + 25*x^5 + 25*x^4 + 93*x^3 + 116*x^2 + 67*x + 50) * (x^7 + 78*x^6 + 91*x^5 + 103*x^4 + 64*x^3 + 6*x^2 + 85*x + 79) * (x^7 + 79*x^6 + 29*x^5 + x^4 + 38*x^3 + 99*x^2 + 111*x + 4) * (x^7 + 81*x^6 + 37*x^5 + 28*x^4 + 117*x^3 + 93*x^2 + 63*x + 97) * (x^7 + 82*x^6 + 113*x^5 + 112*x^4 + 18*x^3 + 20*x^2 + 66*x + 52) * (x^7 + 83*x^6 + 58*x^5 + 7*x^4 + 35*x^3 + 10*x^2 + 38*x + 86) * (x^7 + 84*x^6 + 98*x^5 + 13*x^4 + 126*x^3 + 17*x^2 + 28*x + 50) * (x^7 + 85*x^6 + 28*x^5 + 52*x^4 + 92*x^3 + 109*x^2 + 105*x + 91) * (x^7 + 85*x^6 + 117*x^5 + 50*x^4 + 114*x^3 + 69*x^2 + 113*x + 113) * (x^7 + 87*x^6 + 15*x^5 + 101*x^4 + 45*x^3 + 112*x^2 + 119*x + 22) * (x^7 + 87*x^6 + 110*x^5 + 30*x^4 + 4*x^3 + 120*x^2 + 21*x + 71) * (x^7 + 88*x^6 + 16*x^5 + 100*x^4 + 61*x^3 + 39*x^2 + 23*x + 112) * (x^7 + 89*x^6 + 55*x^5 + 21*x^4 + 81*x^3 + 26*x^2 + 91*x + 5) * (x^7 + 90*x^6 + 24*x^5 + 63*x^4 + 68*x^3 + 16*x^2 + 41*x + 51) * (x^7 + 91*x^6 + 82*x^5 + 125*x^4 + 49*x^3 + 10*x^2 + 52*x + 63) * (x^7 + 91*x^6 + 100*x^5 + 43*x^4 + 84*x^3 + 44*x^2 + 85*x + 58) * (x^7 + 94*x^6 + 96*x^5 + 15*x^4 + 26*x^3 + 66*x^2 + 80*x + 59) * (x^7 + 94*x^6 + 108*x^5 + 40*x^4 + 112*x^3 + 12*x^2 + 37*x + 118) * (x^7 + 98*x^6 + 71*x^5 + 77*x^4 + x^3 + 15*x^2 + 9*x + 102) * (x^7 + 99*x^6 + 64*x^5 + 12*x^4 + 78*x^3 + 24*x^2 + 27*x + 116) * (x^7 + 102*x^6 + 121*x^5 + 5*x^4 + 41*x^3 + 91*x^2 + 119*x + 94) * (x^7 + 103*x^6 + 41*x^5 + 56*x^4 + 23*x^3 + 46*x^2 + 27*x + 118) * (x^7 + 103*x^6 + 114*x^5 + 110*x^4 + 56*x^3 + 29*x^2 + 111*x + 110) * (x^7 + 104*x^6 + 46*x^5 + 115*x^4 + 44*x^3 + 55*x^2 + 3*x + 85) * (x^7 + 104*x^6 + 73*x^5 + 80*x^4 + 115*x^3 + 31*x^2 + 125*x + 18) * (x^7 + 104*x^6 + 87*x^5 + 51*x^4 + 98*x^3 + 27*x^2 + 71*x + 37) * (x^7 + 105*x^6 + 31*x^5 + 26*x^4 + 117*x^3 + 31*x^2 + 59*x + 104) * (x^7 + 105*x^6 + 88*x^5 + 86*x^4 + 86*x^3 + 26*x^2 + 26*x + 108) * (x^7 + 106*x^6 + 78*x^5 + 119*x^4 + x^3 + 41*x^2 + 72*x + 41) * (x^7 + 108*x^6 + 21*x^5 + 116*x^4 + 50*x^3 + 21*x^2 + 21*x + 58) * (x^7 + 108*x^6 + 45*x^5 + x^4 + 41*x^3 + 43*x^2 + 81*x + 98) * (x^7 + 108*x^6 + 63*x^5 + 93*x^4 + 13*x^3 + 115*x^2 + 80*x + 116) * (x^7 + 108*x^6 + 103*x^5 + 73*x^4 + 17*x^3 + 70*x^2 + 29*x + 56) * (x^7 + 109*x^6 + 73*x^5 + 81*x^4 + 86*x^3 + 34*x^2 + 28*x + 106) * (x^7 + 110*x^6 + 56*x^5 + 126*x^4 + 78*x^3 + 23*x^2 + 47*x + 65) * (x^7 + 110*x^6 + 64*x^5 + 60*x^4 + 31*x^3 + 3*x^2 + 115*x + 5) * (x^7 + 113*x^6 + 18*x^5 + 42*x^4 + 27*x^3 + 54*x^2 + 86*x + 43) * (x^7 + 114*x^6 + 3*x^5 + 10*x^4 + 60*x^3 + 83*x^2 + 121*x + 91) * (x^7 + 114*x^6 + 89*x^5 + 10*x^4 + 39*x^3 + 96*x^2 + 80*x + 76) * (x^7 + 116*x^6 + 43*x^5 + 70*x^4 + 126*x^3 + 94*x^2 + 105*x + 59) * (x^7 + 116*x^6 + 91*x^5 + 70*x^4 + 3*x^3 + 43*x^2 + 69*x + 114) * (x^7 + 119*x^6 + 66*x^5 + 73*x^4 + 41*x^3 + 14*x^2 + 84*x + 79) * (x^7 + 121*x^6 + 26*x^5 + 103*x^4 + 84*x^3 + 112*x^2 + 74*x + 58) * (x^7 + 123*x^6 + 87*x^5 + 24*x^4 + 37*x^3 + 123*x^2 + 51*x + 22) * (x^7 + 124*x^6 + 8*x^5 + 33*x^4 + 96*x^3 + 2*x^2 + 16*x + 70) * (x^7 + 126*x^6 + 46*x^5 + 45*x^4 + 80*x^3 + 71*x^2 + 120*x + 81)" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.division_polynomial(43).factor()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How many isogenies of degree 43 does the curve have over $𝔽_{127^7}$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We verify that $E[43] ⊂ E(𝔽_{127^7})$" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3 * 43^2 * 2017 * 47627959" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EE = E.change_ring(GF(127^7))\n", "EE.order().factor()" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Additive abelian group isomorphic to Z/12392461536087 + Z/43 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 97*x + 46 over Finite Field in z7 of size 127^7" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EE.abelian_group()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We take a basis of $E[43]$" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(43, 43)" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P, Q = EE.gens()\n", "P = (12392461536087 // 43) * P\n", "P.order(), Q.order()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For each of the cyclic subgroups $G ⊂ E[43]$, we print the $j$-invariant of $E/G$." ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "113*z7^6 + 28*z7^5 + 89*z7^4 + 15*z7^3 + 93*z7^2 + 2*z7 + 120" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "EE.isogeny(Q).codomain().j_invariant()" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[70,\n", " 70,\n", " 44*z7^5 + 112*z7^4 + 21*z7^3 + 6*z7^2 + 53*z7 + 111,\n", " 13*z7^6 + 9*z7^5 + 41*z7^4 + 71*z7^3 + 57*z7^2 + 23*z7 + 6,\n", " 111*z7^6 + 95*z7^5 + 75*z7^4 + 85*z7^3 + 114*z7^2 + 38*z7 + 9,\n", " 40*z7^6 + 21*z7^5 + 64*z7^4 + 40*z7^3 + 31*z7^2 + 51*z7 + 16,\n", " 82*z7^6 + 2*z7^5 + 116*z7^4 + 2*z7^3 + 63*z7^2 + 80*z7 + 19,\n", " 87*z7^6 + 25*z7^5 + 88*z7^4 + 21*z7^3 + 119*z7^2 + 29*z7 + 27,\n", " 116*z7^6 + 83*z7^5 + 102*z7^4 + 21*z7^3 + 23*z7^2 + 90*z7 + 37,\n", " 69*z7^6 + 14*z7^5 + 120*z7^4 + 32*z7^3 + 98*z7^2 + 109*z7 + 37,\n", " 24*z7^6 + 29*z7^5 + 23*z7^4 + 83*z7^3 + 35*z7^2 + 111*z7 + 39,\n", " 8*z7^6 + 37*z7^5 + 35*z7^4 + 123*z7^3 + 19*z7^2 + 80*z7 + 40,\n", " 88*z7^6 + 18*z7^5 + 77*z7^4 + 16*z7^3 + 54*z7^2 + 8*z7 + 45,\n", " 16*z7^6 + 126*z7^5 + 75*z7^4 + 26*z7^3 + 126*z7^2 + 14*z7 + 45,\n", " 14*z7^6 + 117*z7^5 + 115*z7^4 + 20*z7^3 + 44*z7^2 + 42*z7 + 50,\n", " 8*z7^6 + 36*z7^5 + 53*z7^4 + 44*z7^3 + 2*z7^2 + 25*z7 + 51,\n", " 110*z7^6 + 22*z7^5 + 30*z7^4 + 104*z7^3 + 91*z7^2 + 88*z7 + 53,\n", " 51*z7^6 + 46*z7^5 + 34*z7^4 + 86*z7^3 + 60*z7^2 + 79*z7 + 54,\n", " 86*z7^6 + 67*z7^5 + 41*z7^4 + 119*z7^3 + 56*z7^2 + 125*z7 + 56,\n", " 16*z7^6 + 76*z7^5 + 12*z7^4 + 125*z7^3 + 84*z7^2 + 101*z7 + 60,\n", " 97*z7^6 + z7^5 + 40*z7^4 + 59*z7^3 + 121*z7^2 + 18*z7 + 70,\n", " 97*z7^6 + 6*z7^5 + 19*z7^4 + 94*z7^3 + 63*z7^2 + 51*z7 + 70,\n", " 54*z7^6 + 66*z7^5 + 105*z7^4 + 39*z7^3 + z7^2 + 75*z7 + 80,\n", " 125*z7^6 + 88*z7^5 + 89*z7^4 + 52*z7^3 + 49*z7^2 + 42*z7 + 82,\n", " 56*z7^6 + 49*z7^5 + 70*z7^4 + 88*z7^3 + 126*z7^2 + 111*z7 + 82,\n", " 34*z7^6 + 111*z7^5 + 13*z7^4 + 9*z7^3 + 87*z7^2 + 70*z7 + 84,\n", " 25*z7^6 + 41*z7^5 + 27*z7^4 + 33*z7^3 + 69*z7^2 + 43*z7 + 85,\n", " 76*z7^6 + 88*z7^5 + 85*z7^4 + 60*z7^3 + 35*z7^2 + 83*z7 + 87,\n", " 21*z7^6 + 53*z7^5 + 61*z7^4 + 122*z7^3 + 61*z7^2 + 36*z7 + 88,\n", " 124*z7^6 + 43*z7^5 + 91*z7^4 + 38*z7^3 + 63*z7^2 + 49*z7 + 91,\n", " 63*z7^6 + 115*z7^5 + 5*z7^4 + 46*z7^3 + 34*z7^2 + 5*z7 + 94,\n", " 64*z7^6 + 73*z7^5 + 7*z7^4 + 118*z7^3 + 27*z7^2 + 37*z7 + 96,\n", " 73*z7^6 + 93*z7^5 + 24*z7^4 + 60*z7^3 + 22*z7^2 + 119*z7 + 101,\n", " 53*z7^6 + 8*z7^5 + 77*z7^4 + 28*z7^3 + 82*z7^2 + 30*z7 + 103,\n", " 88*z7^6 + 11*z7^5 + 92*z7^4 + 62*z7^3 + 72*z7^2 + 100*z7 + 107,\n", " 48*z7^6 + 115*z7^5 + 23*z7^4 + 92*z7^3 + 50*z7^2 + 12*z7 + 108,\n", " 3*z7^6 + 15*z7^5 + 47*z7^4 + z7^3 + 106*z7^2 + 96*z7 + 110,\n", " 30*z7^6 + 105*z7^5 + 37*z7^4 + 96*z7^3 + 60*z7^2 + 22*z7 + 113,\n", " 71*z7^6 + 16*z7^5 + 15*z7^4 + 104*z7^3 + 42*z7^2 + 12*z7 + 114,\n", " 35*z7^6 + 58*z7^5 + 83*z7^4 + 86*z7^3 + 45*z7^2 + 73*z7 + 115,\n", " 33*z7^6 + 41*z7^5 + 15*z7^4 + 92*z7^3 + 125*z7^2 + 71*z7 + 118,\n", " 108*z7^6 + 68*z7^5 + 72*z7^4 + 51*z7^3 + 101*z7^2 + 79*z7 + 118,\n", " 110*z7^6 + 14*z7^4 + 56*z7^3 + 51*z7^2 + 31*z7 + 125]" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sorted([EE.isogeny(P + i*Q).codomain().j_invariant() for i in range(43)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We find twice $j = 70 ∈ 𝔽_{127}$ in the list, indicating there are two distinct isogenies to this curve. It is not difficult to prove that these isogenies must be $𝔽_{127}$-rational, while clearly all other isogenies to curves defined over $𝔽_{127^7}$ cannot be. However there is a simpler command to ask Sage to compute all rational isogenies for us, which confirms what we just found." ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 + 97*x + 46 over Finite Field of size 127 to Elliptic Curve defined by y^2 = x^3 + 38*x + 16 over Finite Field of size 127,\n", " Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 + 97*x + 46 over Finite Field of size 127 to Elliptic Curve defined by y^2 = x^3 + 100*x + 8 over Finite Field of size 127]" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.isogenies_prime_degree(43)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We could have predicted this using more theory. The Frobenius endomorphism has two eigenvalues modulo 43." ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(41, 1), (1, 1)]" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.frobenius_polynomial().change_ring(GF(43)).roots()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$λ = 1$ corresponds to the subgroup of $𝔽_{127}$-rational points of order 43" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 + 97*x + 46 over Finite Field of size 127 to Elliptic Curve defined by y^2 = x^3 + 38*x + 16 over Finite Field of size 127" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.isogeny(3*E.gens()[0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$λ = -2$ corresponds to a subgroup $G$ such that $π(P) = -2P$ for each $P ∈ G$. We know these points are defined over $𝔽_{127^7}$, we can find them by iterating over all points of order $43$ and testing the condition.\n", "\n", "A trick to get one such point faster is to obeserve that $(π + 2)(π - 1)(P) = 0$ for every $P ∈ E[43]$, thus if $Q = (π - 1)(P)$ then $(π + 2)(Q) = 0$." ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Isogeny of degree 43 from Elliptic Curve defined by y^2 = x^3 + 97*x + 46 over Finite Field in z7 of size 127^7 to Elliptic Curve defined by y^2 = x^3 + 100*x + 8 over Finite Field in z7 of size 127^7" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Q = EE.point([P[0]^127, P[1]^127])\n", "Q = Q - P\n", "EE.isogeny(Q)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2\n", "\n", "Give the list of all elliptic curves defined over $ℚ$ with complex multiplication\n", "\n", "(may require checking [Wikipedia](https://en.wikipedia.org/wiki/Class_number_problem))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 3\n", "\n", "Find a prime $p$ and an elliptic curve $E/𝔽_p$ such that $\\#E(𝔽_p) = 101$.\n", "\n", "Hint: try to find a solution to $p+1-t = 101$, then compute the discriminant of the Frobenius and use complex multiplication theory." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Use the previously found curve to construct an isogeny of degree $101^{10}$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 4\n", "\n", "Let $ω ∈ ℂ$ be a cube root of unity, the ring $ℤ[ω]$ is also known as the Eisenstein integers. Determine all elliptic curves with complex multiplication by $ℤ[ω]$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 5\n", "\n", "Prove that $-163$ is not a square modulo all odd primes $< 41$. \n", "\n", "Hint: Let $E/ℚ$ be an elliptic curve with complex multiplication by (an order of discriminant) $-D$. Its reduction modulo $p$ is ordinary if and only if $-D$ is a square modulo $p$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 6\n", "\n", "Find an elliptic curve $E/𝔽_{1613}$ and two distinct isogenies of degree $2311$ from $E$\n", "\n", "Note: the challenge here is to make the computation run in a couple of seconds..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 10.1", "language": "sage", "name": "sagemath" }, "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.11.5" } }, "nbformat": 4, "nbformat_minor": 4 }