{ "cells": [ { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "# For an elliptic curve, with notation as in the paper,\n", "# this block of code computes the preimage of a divisor \n", "# under the map Frac(\\overline{R}) \\rightarrow \\Div^0(\\overline}{E})\n", "# if such a preimage exists.\n", "\n", "def lineBetweenPoints(P, Q):\n", " a1, b1 = P.xy()\n", " a2, b2 = Q.xy()\n", " if (a1 == a2):\n", " return (x-a1)\n", " return ((b2-b1)/(a2-a1))*(x-a1) - (y-b1)\n", "\n", "def lineTangentTo(P, E):\n", " a, b = P.xy()\n", " if (P.order() == 2):\n", " return (x-a)\n", " defining_array = E.a_invariants()\n", " a1 = defining_array[0]\n", " a2 = defining_array[1]\n", " a3 = defining_array[2]\n", " a4 = defining_array[3]\n", " a6 = defining_array[4]\n", " slope = (3*a^2 + 2*a2*a - a1*b + a4)/(2*b + a1*a+a3)\n", " return slope*(x-a) - (y-b)\n", "\n", "class Divisor:\n", " def __init__(self, E, dict, base_point):\n", " self.E = E\n", " self.base_point = base_point\n", " self.dict = {}\n", " for key, value in dict.items():\n", " if value != 0:\n", " self.dict[key] = value\n", "\n", " def __add__(self, another_divisor):\n", " new_dict = {}\n", " for key, value in self.dict.items():\n", " if value is not 0:\n", " new_dict[key] = value\n", "\n", " for key, value in another_divisor.dict.items():\n", " if key in new_dict.keys() and new_dict[key] + value is not 0:\n", " new_dict[key] = new_dict[key] + value\n", " elif value is not 0:\n", " new_dict[key] = value\n", " return Divisor(self.E, new_dict, base_point)\n", "\n", " def __sub__(self, another_divisor):\n", " new_dict = {}\n", " for key, value in self.dict.items():\n", " if value is not 0:\n", " new_dict[key] = value\n", "\n", " for key, value in another_divisor.dict.items():\n", " if key in new_dict.keys() and new_dict[key] - value is not 0:\n", " new_dict[key] = new_dict[key] - value\n", " elif value is not 0:\n", " new_dict[key] = -value\n", " return Divisor(self.E, new_dict, base_point)\n", "\n", " def __eq__(self, another_divisor):\n", " if (self.E is not another_divisor.E):\n", " return False\n", " elif self.dict == another_divisor.dict:\n", " return True\n", " else:\n", " return False\n", "\n", " def __ne__(self, another_divisor):\n", " return not (self == another_divisor)\n", "\n", " def coeff(self, point):\n", " return self.dict[point]\n", "\n", " def support(self):\n", " return self.dict.keys()\n", "\n", " def getMNPQ(self):\n", " m = 0\n", " n = 0\n", " P = None\n", " Q = None\n", " for point in self.support():\n", " if (self.coeff(point) > 0 and point != base_point):\n", " P = point\n", " m = self.coeff(point)\n", " elif (self.coeff(point) < 0 and point != base_point):\n", " Q = point\n", " n = -self.coeff(point)\n", " return m, n, P, Q\n", "\n", " def getPair(self, comparisonOperator, equalityOperator):\n", " points = set()\n", " for point in self.support():\n", " if point != base_point and (comparisonOperator(self.coeff(point), 0)):\n", " points.add(point)\n", " for P in points:\n", " for Q in points:\n", " if (P != Q and equalityOperator(P,-Q)):\n", " return (P,Q)\n", "\n", " def existsPair(self, comparisonOperator, equalityOperator):\n", " points = set()\n", " for point in self.support():\n", " if point != base_point and (comparisonOperator(self.coeff(point), 0)):\n", " points.add(point)\n", " for P in points:\n", " for Q in points:\n", " if (P != Q and equalityOperator(P,-Q)):\n", " return True\n", " return False\n", "\n", "def interpolate(D, base_point, E):\n", " # start with rational function 1\n", " # while D is not 0\n", " rational_function = 1\n", " E = D.E\n", " zero_divisor = Divisor(E,{},base_point)\n", " while (D != zero_divisor):\n", " #print \"loop\"\n", " #print D.dict\n", " #print rational_function\n", " # if P, Q have coefficients > 0 and P != -Q, subtract (
+ + + + - n + <-2P> - 3<0>) and multiply rational function by tangent line at P\n",
" if m >= 2 and P.order() != 2:\n",
" #print \"case 5\"\n",
" if P.order() == 3:\n",
" # -2P = P\n",
" sub_divisor = Divisor(E, {P:3, base_point:-3}, base_point)\n",
" else:\n",
" sub_divisor = Divisor(E, {P:2, (-2*P):1, base_point:-3}, base_point)\n",
" D = D - sub_divisor\n",
" rational_function = rational_function*lineTangentTo(P, E)\n",
" # else if m >= 2 and P of order 2, then subtract (2 - 2<0>) and multiply rational function by tangent line at P\n",
" elif m >= 2 and P.order() == 2:\n",
" #print \"case 6\"\n",
" sub_divisor = Divisor(E, {P:2,base_point:-2}, base_point)\n",
" D = D - sub_divisor\n",
" rational_function = rational_function*lineTangentTo(P, E)\n",
" # else if n >=2 and Q not of order 2, then add (2 + <-(P+Q)> - 3<0>) and multiply rational function by line between P and Q\n",
" if D.existsPair(operator.gt, operator.ne):\n",
" #print \"case 1\"\n",
" P, Q = D.getPair(operator.gt, operator.ne)\n",
" sub_divisor = Divisor(E, {P : 1, Q : 1, -(P+Q) : 1, base_point: -3}, base_point)\n",
" D = D - sub_divisor\n",
" rational_function = rational_function*lineBetweenPoints(P,Q)\n",
" # else if P, Q have coefficients > 0 and P=-Q subtract (
- 2<0>) and multiply rational function by line between P and Q\n",
" elif D.existsPair(operator.gt, operator.eq):\n",
" #print \"case 2\"\n",
" P, Q = D.getPair(operator.gt, operator.eq)\n",
" sub_divisor = Divisor(E, {P:1,Q:1, base_point: -2}, base_point)\n",
" D = D - sub_divisor\n",
" rational_function = rational_function*lineBetweenPoints(P,Q)\n",
" # else if P, Q have coefficients < 0 and P != -Q, add (
+ <-(P+Q)> - 3<0>) and divide rational function by line between P and Q\n",
" elif D.existsPair(operator.lt, operator.ne):\n",
" #print \"case 3\"\n",
" P, Q = D.getPair(operator.lt, operator.ne)\n",
" add_divisor = Divisor(E, {P:1,Q:1,-(P+Q):1,base_point:-3}, base_point)\n",
" D = D+add_divisor\n",
" rational_function = rational_function/lineBetweenPoints(P,Q)\n",
" # else if P, Q have coefficients < 0 and P=-Q add (
- 2<0>) and divide rational function by line between P and Q\n",
" elif D.existsPair(operator.lt, operator.eq):\n",
" #print \"case 4\"\n",
" P, Q = D.getPair(operator.lt, operator.eq)\n",
" add_divisor = Divisor(E, {P:1,Q:1,base_point:-2}, base_point)\n",
" D = D+add_divisor\n",
" rational_function = rational_function/lineBetweenPoints(P,Q)\n",
" # else if D is of form m
+ o<0> (o may be positive or negative, m >= 0, n>= 0)\n",
" else:\n",
" m, n, P, Q = D.getMNPQ()\n",
" # if m >= 2 and P not order 2, then subtract (2
+ <-2Q> - 3<0>) and divide rational function by tangent line at Q\n",
" elif n >=2 and Q.order() != 2:\n",
" #print \"case 7\"\n",
" if Q.order() == 3:\n",
" # -2Q = Q\n",
" add_divisor = Divisor(E, {Q:3, base_point: -3}, base_point)\n",
" else:\n",
" add_divisor = Divisor(E, {Q:2, (-2*Q):1, base_point: -3}, base_point)\n",
" D = D + add_divisor\n",
" rational_function = rational_function/lineTangentTo(Q, E)\n",
" # else if n >= 2 and Q of order 2, then add (2
- 2<0>) and divide rational function by tangent line at Q\n",
" elif n >=2 and Q.order() == 2:\n",
" #print \"case 8\"\n",
" add_divisor = Divisor(E, {Q:2, base_point:-2}, base_point)\n",
" D = D + add_divisor\n",
" rational_function = rational_function/lineTangentTo(Q, E)\n",
" # else if m=n=1, add (
+ <-Q> - 2<0>) and divide rational function by line through Q and -Q\n",
" elif m==1 and n==1:\n",
" #print \"case 9\"\n",
" add_divisor = Divisor(E, {Q:1, -Q:1, base_point:-2}, base_point)\n",
" D = D + add_divisor\n",
" rational_function = rational_function/lineBetweenPoints(Q,-Q)\n",
" else:\n",
" print \"cannot interpolate the following divisor\"\n",
" print D.dict\n",
" print rational_function\n",
" return None\n",
" return rational_function"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Example 1: computing the units of the Fermat 3-curve\n",
"from sage.modules.free_module_integer import IntegerLattice\n",
"from itertools import product\n",
"\n",
"# construct the curve\n",
"a = PolynomialRing(RationalField(), 'a').gen()\n",
"K. = NumberField(a^2 + a + 1)\n",
"R.