# Ticket #16115: ell_curve_isogeny.py

File ell_curve_isogeny.py, 138.3 KB (added by , 6 years ago) |
---|

Line | |
---|---|

1 | r""" |

2 | Isogenies |

3 | |

4 | An isogeny `\varphi: E_1\to E_2` between two elliptic curves `E_1` and |

5 | `E_2` is a morphism of curves that sends the origin of `E_1` to the |

6 | origin of `E_2`. Such a morphism is automatically a morphism of group |

7 | schemes and the kernel is a finite subgroup scheme of `E_1`. Such a |

8 | subscheme can either be given by a list of generators, which have to |

9 | be torsion points, or by a polynomial in the coordinate `x` of the |

10 | Weierstrass equation of `E_1`. |

11 | |

12 | The usual way to create and work with isogenies is illustrated with |

13 | the following example:: |

14 | |

15 | sage: k = GF(11) |

16 | sage: E = EllipticCurve(k,[1,1]) |

17 | sage: Q = E(6,5) |

18 | sage: phi = E.isogeny(Q) |

19 | sage: phi |

20 | Isogeny of degree 7 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 11 to Elliptic Curve defined by y^2 = x^3 + 7*x + 8 over Finite Field of size 11 |

21 | sage: P = E(4,5) |

22 | sage: phi(P) |

23 | (10 : 0 : 1) |

24 | sage: phi.codomain() |

25 | Elliptic Curve defined by y^2 = x^3 + 7*x + 8 over Finite Field of size 11 |

26 | sage: phi.rational_maps() |

27 | ((x^7 + 4*x^6 - 3*x^5 - 2*x^4 - 3*x^3 + 3*x^2 + x - 2)/(x^6 + 4*x^5 - 4*x^4 - 5*x^3 + 5*x^2), (x^9*y - 5*x^8*y - x^7*y + x^5*y - x^4*y - 5*x^3*y - 5*x^2*y - 2*x*y - 5*y)/(x^9 - 5*x^8 + 4*x^6 - 3*x^4 + 2*x^3)) |

28 | |

29 | The functions directly accessible from an elliptic curve ``E`` over a |

30 | field are ``isogeny`` and ``isogeny_codomain``. |

31 | |

32 | The most useful functions that apply to isogenies are |

33 | |

34 | - ``codomain`` |

35 | - ``degree`` |

36 | - ``domain`` |

37 | - ``dual`` |

38 | - ``rational_maps`` |

39 | - ``kernel_polynomial`` |

40 | |

41 | .. Warning:: |

42 | |

43 | Only cyclic, separable isogenies are implemented (except for [2]). Some |

44 | algorithms may need the isogeny to be normalized. |

45 | |

46 | AUTHORS: |

47 | |

48 | - Daniel Shumow <shumow@gmail.com>: 2009-04-19: initial version |

49 | |

50 | - Chris Wuthrich : 7/09: changes: add check of input, not the full list is needed. |

51 | 10/09: eliminating some bugs. |

52 | |

53 | """ |

54 | |

55 | #***************************************************************************** |

56 | # Copyright (C) 2009 Daniel Shumow <shumow@gmail.com> |

57 | # |

58 | # Distributed under the terms of the GNU General Public License (GPL) |

59 | # http://www.gnu.org/licenses/ |

60 | #***************************************************************************** |

61 | |

62 | from copy import deepcopy, copy |

63 | |

64 | from sage.categories import homset |

65 | |

66 | from sage.categories.morphism import Morphism |

67 | |

68 | from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing |

69 | from sage.rings.polynomial.polynomial_ring import polygen |

70 | from sage.rings.all import Integer, ZZ |

71 | from sage.rings.laurent_series_ring import LaurentSeriesRing |

72 | from sage.rings.polynomial.all import is_Polynomial |

73 | from sage.schemes.elliptic_curves.all import EllipticCurve |

74 | from sage.schemes.elliptic_curves.all import is_EllipticCurve |

75 | |

76 | from sage.rings.number_field.number_field_base import is_NumberField |

77 | |

78 | from sage.rings.rational_field import is_RationalField, QQ |

79 | |

80 | from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

81 | |

82 | from sage.sets.set import Set |

83 | |

84 | from sage.misc.cachefunc import cached_function |

85 | |

86 | # |

87 | # Private function for parsing input to determine the type of |

88 | # algorithm |

89 | # |

90 | def isogeny_determine_algorithm(E, kernel, codomain, degree, model): |

91 | r""" |

92 | Helper function that allows the various isogeny functions to infer |

93 | the algorithm type from the parameters passed in. |

94 | |

95 | If ``kernel`` is a list of points on the EllipticCurve `E`, then |

96 | we assume the algorithm to use is Velu. |

97 | |

98 | If ``kernel`` is a list of coefficients or a univariate polynomial |

99 | we try to use the Kohel's algorithms. |

100 | |

101 | EXAMPLES: |

102 | |

103 | This helper function will be implicitly called by the following examples:: |

104 | |

105 | sage: R.<x> = GF(5)[] |

106 | sage: E = EllipticCurve(GF(5), [0,0,0,1,0]) |

107 | sage: phi = EllipticCurveIsogeny(E, x+3) |

108 | sage: phi2 = EllipticCurveIsogeny(E, [GF(5)(3),GF(5)(1)]) |

109 | sage: phi == phi2 |

110 | True |

111 | sage: phi3 = EllipticCurveIsogeny(E, E((2,0)) ) |

112 | sage: phi3 == phi2 |

113 | True |

114 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_determine_algorithm |

115 | sage: isogeny_determine_algorithm(E, x+3, None, None, None) |

116 | 'kohel' |

117 | sage: isogeny_determine_algorithm(E, [3, 1], None, None, None) |

118 | 'kohel' |

119 | sage: isogeny_determine_algorithm(E, E((2,0)), None, None, None) |

120 | 'velu' |

121 | |

122 | """ |

123 | |

124 | kernel_is_list = (type(kernel) == list) |

125 | |

126 | if not kernel_is_list and kernel in E : |

127 | kernel = [kernel] |

128 | kernel_is_list = True |

129 | |

130 | if (is_Polynomial(kernel) or ( kernel_is_list) and (kernel[0] in E.base_ring()) ): |

131 | algorithm = "kohel" |

132 | elif (kernel_is_list) and (kernel[0] in E): # note that if kernel[0] is on an extension of E this condition will be false |

133 | algorithm = "velu" |

134 | else: |

135 | raise ValueError, "Invalid Parameters to EllipticCurveIsogeny constructor." |

136 | |

137 | return algorithm |

138 | |

139 | |

140 | def isogeny_codomain_from_kernel(E, kernel, degree=None): |

141 | r""" |

142 | This function computes the isogeny codomain given a kernel. |

143 | |

144 | INPUT: |

145 | |

146 | - ``E`` - The domain elliptic curve. |

147 | |

148 | - ``kernel`` - Either a list of points in the kernel of the isogeny, or a |

149 | kernel polynomial (specified as a either a univariate |

150 | polynomial or a coefficient list.) |

151 | |

152 | - ``degree`` - an integer, (default:``None``) optionally specified degree |

153 | of the kernel. |

154 | |

155 | OUTPUT: |

156 | |

157 | (elliptic curve) the codomain of the separable normalized isogeny |

158 | from this kernel |

159 | |

160 | EXAMPLES:: |

161 | |

162 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import isogeny_codomain_from_kernel |

163 | sage: E = EllipticCurve(GF(7), [1,0,1,0,1]) |

164 | sage: R.<x> = GF(7)[] |

165 | sage: isogeny_codomain_from_kernel(E, [4,1], degree=3) |

166 | Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7 |

167 | sage: EllipticCurveIsogeny(E, [4,1]).codomain() == isogeny_codomain_from_kernel(E, [4,1], degree=3) |

168 | True |

169 | sage: isogeny_codomain_from_kernel(E, x^3 + x^2 + 4*x + 3) |

170 | Elliptic Curve defined by y^2 + x*y + y = x^3 + 4*x + 6 over Finite Field of size 7 |

171 | sage: isogeny_codomain_from_kernel(E, x^3 + 2*x^2 + 4*x + 3) |

172 | Elliptic Curve defined by y^2 + x*y + y = x^3 + 5*x + 2 over Finite Field of size 7 |

173 | |

174 | sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) |

175 | sage: kernel_list = [E((15,10)), E((10,3)),E((6,5))] |

176 | sage: isogeny_codomain_from_kernel(E, kernel_list) |

177 | Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19 |

178 | |

179 | """ |

180 | |

181 | algorithm = isogeny_determine_algorithm(E, kernel, None, degree, None); |

182 | |

183 | if ("velu"==algorithm): |

184 | # if we are using Velu's formula, just instantiate the isogeny |

185 | # and return the codomain |

186 | codomain = EllipticCurveIsogeny(E, kernel).codomain() |

187 | elif ("kohel"==algorithm): |

188 | codomain = compute_codomain_kohel(E, kernel, degree) |

189 | |

190 | return codomain |

191 | |

192 | |

193 | def compute_codomain_formula(E, v, w): |

194 | r""" |

195 | Given parameters `v` and `w` (as in Velu / Kohel / etc formulas) |

196 | computes the codomain curve. |

197 | |

198 | EXAMPLES: |

199 | |

200 | This formula is used by every Isogeny Instantiation:: |

201 | |

202 | sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) |

203 | sage: phi = EllipticCurveIsogeny(E, E((1,2)) ) |

204 | sage: phi.codomain() |

205 | Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19 |

206 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_formula |

207 | sage: v = phi._EllipticCurveIsogeny__v |

208 | sage: w = phi._EllipticCurveIsogeny__w |

209 | sage: compute_codomain_formula(E, v, w) |

210 | Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 13 over Finite Field of size 19 |

211 | |

212 | """ |

213 | |

214 | a1,a2,a3,a4,a6 = E.ainvs() |

215 | |

216 | A4 = a4 - 5*v |

217 | A6 = a6 - (a1**2 + 4*a2)*v - 7*w |

218 | |

219 | return EllipticCurve([a1, a2, a3, A4, A6]) |

220 | |

221 | |

222 | def compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4): |

223 | r""" |

224 | The formula for computing `v` and `w` using Kohel's formulas for |

225 | isogenies of degree 2. |

226 | |

227 | EXAMPLES: |

228 | |

229 | This function will be implicitly called by the following example:: |

230 | |

231 | sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) |

232 | sage: phi = EllipticCurveIsogeny(E, [9,1]) |

233 | sage: phi |

234 | Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 19 to Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19 |

235 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg1 |

236 | sage: a1,a2,a3,a4,a6 = E.ainvs() |

237 | sage: x0 = -9 |

238 | sage: y0 = -(a1*x0 + a3)/2 |

239 | sage: compute_vw_kohel_even_deg1(x0, y0, a1, a2, a4) |

240 | (18, 9) |

241 | |

242 | """ |

243 | |

244 | v = (3*x0**2 + 2*a2*x0 + a4 - a1*y0) |

245 | w = x0*v |

246 | |

247 | return (v,w) |

248 | |

249 | |

250 | def compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3): |

251 | r""" |

252 | The formula for computing `v` and `w` using Kohel's formulas for |

253 | isogenies of degree 3. |

254 | |

255 | EXAMPLES: |

256 | |

257 | This function will be implicitly called by the following example:: |

258 | |

259 | sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) |

260 | sage: R.<x> = GF(19)[] |

261 | sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12) |

262 | sage: phi |

263 | Isogeny of degree 4 from Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 19 to Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19 |

264 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_even_deg3 |

265 | sage: (b2,b4) = (E.b2(), E.b4()) |

266 | sage: (s1, s2, s3) = (-7, 15, -12) |

267 | sage: compute_vw_kohel_even_deg3(b2, b4, s1, s2, s3) |

268 | (4, 7) |

269 | |

270 | """ |

271 | |

272 | temp1 = (s1**2 - 2*s2) |

273 | v = 3*temp1 + b2*s1/2 + 3*b4/2 |

274 | w = 3*(s1**3 - 3*s1*s2 + 3*s3) + b2*temp1/2 + b4*s1/2 |

275 | |

276 | return (v,w) |

277 | |

278 | |

279 | def compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n): |

280 | r""" |

281 | This function computes the `v` and `w` according to Kohel's formulas. |

282 | |

283 | EXAMPLES: |

284 | |

285 | This function will be implicitly called by the following example:: |

286 | |

287 | sage: E = EllipticCurve(GF(19), [18,17,16,15,14]) |

288 | sage: R.<x> = GF(19)[] |

289 | sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11) |

290 | sage: phi |

291 | Isogeny of degree 7 from Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 15*x + 14 over Finite Field of size 19 to Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19 |

292 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_vw_kohel_odd |

293 | sage: (b2,b4,b6) = (E.b2(), E.b4(), E.b6()) |

294 | sage: (s1,s2,s3) = (-14,3,-11) |

295 | sage: compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,3) |

296 | (7, 1) |

297 | |

298 | """ |

299 | |

300 | v = 6*(s1**2 - 2*s2) + b2*s1 + n*b4 |

301 | w = 10*(s1**3 - 3*s1*s2 + 3*s3) + 2*b2*(s1**2 - 2*s2) + 3*b4*s1 + n*b6 |

302 | |

303 | return (v,w) |

304 | |

305 | |

306 | def compute_codomain_kohel(E, kernel, degree): |

307 | r""" |

308 | This function computes the codomain from the kernel polynomial as |

309 | per Kohel's formulas. |

310 | |

311 | EXAMPLES:: |

312 | |

313 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_codomain_kohel |

314 | sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) |

315 | sage: phi = EllipticCurveIsogeny(E, [9,1]) |

316 | sage: phi.codomain() == isogeny_codomain_from_kernel(E, [9,1]) |

317 | True |

318 | sage: compute_codomain_kohel(E, [9,1], 2) |

319 | Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 9*x + 8 over Finite Field of size 19 |

320 | sage: R.<x> = GF(19)[] |

321 | sage: E = EllipticCurve(GF(19), [18,17,16,15,14]) |

322 | sage: phi = EllipticCurveIsogeny(E, x^3 + 14*x^2 + 3*x + 11) |

323 | sage: phi.codomain() == isogeny_codomain_from_kernel(E, x^3 + 14*x^2 + 3*x + 11) |

324 | True |

325 | sage: compute_codomain_kohel(E, x^3 + 14*x^2 + 3*x + 11, 7) |

326 | Elliptic Curve defined by y^2 + 18*x*y + 16*y = x^3 + 17*x^2 + 18*x + 18 over Finite Field of size 19 |

327 | sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) |

328 | sage: phi = EllipticCurveIsogeny(E, x^3 + 7*x^2 + 15*x + 12) |

329 | sage: isogeny_codomain_from_kernel(E, x^3 + 7*x^2 + 15*x + 12) == phi.codomain() |

330 | True |

331 | sage: compute_codomain_kohel(E, x^3 + 7*x^2 + 15*x + 12,4) |

332 | Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 3*x + 15 over Finite Field of size 19 |

333 | |

334 | NOTES: |

335 | |

336 | This function uses the formulas of Section 2.4 of [K96]. |

337 | |

338 | REFERENCES: |

339 | |

340 | - [K96] Kohel, "Endomorphism Rings of Elliptic Curves over Finite Fields" |

341 | |

342 | """ |

343 | |

344 | # First set up the polynomial ring |

345 | |

346 | base_field = E.base_ring() |

347 | |

348 | if (is_Polynomial(kernel)): |

349 | psi = kernel |

350 | kernel_list = psi.list() |

351 | poly_ring = psi.parent() |

352 | x = psi.variables()[0] |

353 | elif (list == type(kernel)) and (kernel[0] in base_field): |

354 | kernel_list = kernel |

355 | poly_ring = base_field.polynomial_ring() |

356 | psi = poly_ring(kernel_list) |

357 | x = poly_ring.gen() |

358 | else: |

359 | raise ValueError, "input not of correct type" |

360 | |

361 | |

362 | # next determine the even / odd part of the isogeny |

363 | psi_2tor = two_torsion_part(E, poly_ring, psi, degree) |

364 | |

365 | if (0 != psi_2tor.degree()): # even degree case |

366 | |

367 | psi_quo = poly_ring(psi/psi_2tor) |

368 | |

369 | if (0 != psi_quo.degree()): |

370 | raise ArithmeticError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion." |

371 | |

372 | n = psi_2tor.degree() |

373 | |

374 | if (1 == n): |

375 | |

376 | a1,a2,a3,a4,a6 = E.ainvs() |

377 | |

378 | x0 = -psi_2tor.constant_coefficient() |

379 | |

380 | # determine y0 |

381 | if (2 == base_field.characteristic()): |

382 | y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt() |

383 | else: |

384 | y0 = -(a1*x0 + a3)/2 |

385 | |

386 | (v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4) |

387 | |

388 | elif (3 == n): |

389 | |

390 | b2 = E.b2() |

391 | b4 = E.b4() |

392 | |

393 | s = psi_2tor.list() |

394 | s1 = -s[n-1] |

395 | s2 = s[n-2] |

396 | s3 = -s[n-3] |

397 | |

398 | (v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3) |

399 | |

400 | else: |

401 | |

402 | n = psi.degree() |

403 | |

404 | b2 = E.b2() |

405 | b4 = E.b4() |

406 | b6 = E.b6() |

407 | |

408 | s1 = 0; s2 = 0; s3 = 0 |

409 | |

410 | if (1 <= n): |

411 | s1 = -kernel_list[n-1] |

412 | |

413 | if (2 <= n): |

414 | s2 = kernel_list[n-2] |

415 | |

416 | if (3 <= n): |

417 | s3 = -kernel_list[n-3] |

418 | |

419 | # initializing these allows us to calculate E2. |

420 | (v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n); |

421 | |

422 | return compute_codomain_formula(E, v, w) |

423 | |

424 | |

425 | def two_torsion_part(E, poly_ring, psi, degree): |

426 | r""" |

427 | |

428 | Returns the greatest common divisor of ``psi`` and the 2 torsion |

429 | polynomial of `E`. |

430 | |

431 | EXAMPLES: |

432 | |

433 | Every function that computes the kernel polynomial via Kohel's |

434 | formulas will call this function:: |

435 | |

436 | sage: E = EllipticCurve(GF(19), [1,2,3,4,5]) |

437 | sage: R.<x> = GF(19)[] |

438 | sage: phi = EllipticCurveIsogeny(E, x + 13) |

439 | sage: isogeny_codomain_from_kernel(E, x + 13) == phi.codomain() |

440 | True |

441 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part |

442 | sage: two_torsion_part(E, R, x+13, 2) |

443 | x + 13 |

444 | |

445 | """ |

446 | if (None==degree) or (0 == degree % 2): |

447 | |

448 | x = poly_ring.gens()[0] |

449 | psi_2 = E.two_division_polynomial(x) |

450 | psi_G = poly_ring(psi.gcd(psi_2)) |

451 | |

452 | else: |

453 | |

454 | psi_G = poly_ring(1) |

455 | |

456 | return psi_G |

457 | |

458 | |

459 | class EllipticCurveIsogeny(Morphism): |

460 | r""" |

461 | Class Implementing Isogenies of Elliptic Curves |

462 | |

463 | This class implements cyclic, separable, normalized isogenies of |

464 | elliptic curves. |

465 | |

466 | Several different algorithms for computing isogenies are |

467 | available. These include: |

468 | |

469 | - Velu's Formulas: Velu's original formulas for computing |

470 | isogenies. This algorithm is selected by giving as the |

471 | ``kernel`` parameter a list of points which generate a finite |

472 | subgroup. |

473 | |

474 | - Kohel's Formulas: Kohel's original formulas for computing |

475 | isogenies. This algorithm is selected by giving as the |

476 | ``kernel`` parameter a monic polynomial (or a coefficient list |

477 | (little endian)) which will define the kernel of the isogeny. |

478 | |

479 | INPUT: |

480 | |

481 | - ``E`` - an elliptic curve, the domain of the isogeny to |

482 | initialize. |

483 | |

484 | - ``kernel`` - a kernel, either a point in ``E``, a list of points |

485 | in ``E``, a monic kernel polynomial, or ``None``. |

486 | If initializing from a domain/codomain, this must be |

487 | set to None. |

488 | |

489 | - ``codomain`` - an elliptic curve (default:``None``). If ``kernel`` |

490 | is ``None``, then this must be the codomain of a cyclic, |

491 | separable, normalized isogeny, furthermore, ``degree`` |

492 | must be the degree of the isogeny from ``E`` to |

493 | ``codomain``. If ``kernel`` is not ``None``, then this |

494 | must be isomorphic to the codomain of the cyclic normalized |

495 | separable isogeny defined by ``kernel``, in this case, the |

496 | isogeny is post composed with an isomorphism so that this |

497 | parameter is the codomain. |

498 | |

499 | - ``degree`` - an integer (default:``None``). |

500 | If ``kernel`` is ``None``, then this is the degree of the |

501 | isogeny from ``E`` to ``codomain``. |

502 | If ``kernel`` is not ``None``, then this is used to determine |

503 | whether or not to skip a gcd of the kernel polynomial with the |

504 | two torsion polynomial of ``E``. |

505 | |

506 | - ``model`` - a string (default:``None``). Only supported variable is |

507 | ``minimal``, in which case if ``E`` is a curve over the |

508 | rationals, then the codomain is set to be the unique global |

509 | minimum model. |

510 | |

511 | - ``check`` (default: ``True``) checks if the input is valid to define an isogeny |

512 | |

513 | EXAMPLES: |

514 | |

515 | A simple example of creating an isogeny of a field of small |

516 | characteristic:: |

517 | |

518 | sage: E = EllipticCurve(GF(7), [0,0,0,1,0]) |

519 | sage: phi = EllipticCurveIsogeny(E, E((0,0)) ); phi |

520 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 7 |

521 | sage: phi.degree() == 2 |

522 | True |

523 | sage: phi.kernel_polynomial() |

524 | x |

525 | sage: phi.rational_maps() |

526 | ((x^2 + 1)/x, (x^2*y - y)/x^2) |

527 | sage: phi == loads(dumps(phi)) # known bug |

528 | True |

529 | |

530 | A more complicated example of a characteristic 2 field:: |

531 | |

532 | sage: E = EllipticCurve(GF(2^4,'alpha'), [0,0,1,0,1]) |

533 | sage: P = E((1,1)) |

534 | sage: phi_v = EllipticCurveIsogeny(E, P); phi_v |

535 | Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + y = x^3 over Finite Field in alpha of size 2^4 |

536 | sage: phi_ker_poly = phi_v.kernel_polynomial() |

537 | sage: phi_ker_poly |

538 | x + 1 |

539 | sage: ker_poly_list = phi_ker_poly.list() |

540 | sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list) |

541 | sage: phi_k == phi_v |

542 | True |

543 | sage: phi_k.rational_maps() |

544 | ((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1)) |

545 | sage: phi_v.rational_maps() |

546 | ((x^3 + x + 1)/(x^2 + 1), (x^3*y + x^2*y + x*y + x + y)/(x^3 + x^2 + x + 1)) |

547 | sage: phi_k.degree() == phi_v.degree() |

548 | True |

549 | sage: phi_k.degree() |

550 | 3 |

551 | sage: phi_k.is_separable() |

552 | True |

553 | sage: phi_v(E(0)) |

554 | (0 : 1 : 0) |

555 | sage: alpha = E.base_field().gen() |

556 | sage: Q = E((0, alpha*(alpha + 1))) |

557 | sage: phi_v(Q) |

558 | (1 : alpha^2 + alpha : 1) |

559 | sage: phi_v(P) == phi_k(P) |

560 | True |

561 | sage: phi_k(P) == phi_v.codomain()(0) |

562 | True |

563 | |

564 | We can create an isogeny that has kernel equal to the full 2 |

565 | torsion:: |

566 | |

567 | sage: E = EllipticCurve(GF(3), [0,0,0,1,1]) |

568 | sage: ker_list = E.division_polynomial(2).list() |

569 | sage: phi = EllipticCurveIsogeny(E, ker_list); phi |

570 | Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 |

571 | sage: phi(E(0)) |

572 | (0 : 1 : 0) |

573 | sage: phi(E((0,1))) |

574 | (1 : 0 : 1) |

575 | sage: phi(E((0,2))) |

576 | (1 : 0 : 1) |

577 | sage: phi(E((1,0))) |

578 | (0 : 1 : 0) |

579 | sage: phi.degree() |

580 | 4 |

581 | |

582 | We can also create trivial isogenies with the trivial kernel:: |

583 | |

584 | sage: E = EllipticCurve(GF(17), [11, 11, 4, 12, 10]) |

585 | sage: phi_v = EllipticCurveIsogeny(E, E(0)) |

586 | sage: phi_v.degree() |

587 | 1 |

588 | sage: phi_v.rational_maps() |

589 | (x, y) |

590 | sage: E == phi_v.codomain() |

591 | True |

592 | sage: P = E.random_point() |

593 | sage: phi_v(P) == P |

594 | True |

595 | |

596 | sage: E = EllipticCurve(GF(31), [23, 1, 22, 7, 18]) |

597 | sage: phi_k = EllipticCurveIsogeny(E, [1]) |

598 | sage: phi_k |

599 | Isogeny of degree 1 from Elliptic Curve defined by y^2 + 23*x*y + 22*y = x^3 + x^2 + 7*x + 18 over Finite Field of size 31 to Elliptic Curve defined by y^2 + 23*x*y + 22*y = x^3 + x^2 + 7*x + 18 over Finite Field of size 31 |

600 | sage: phi_k.degree() |

601 | 1 |

602 | sage: phi_k.rational_maps() |

603 | (x, y) |

604 | sage: phi_k.codomain() == E |

605 | True |

606 | sage: phi_k.kernel_polynomial() |

607 | 1 |

608 | sage: P = E.random_point(); P == phi_k(P) |

609 | True |

610 | |

611 | Velu and Kohel also work in characteristic 0:: |

612 | |

613 | sage: E = EllipticCurve(QQ, [0,0,0,3,4]) |

614 | sage: P_list = E.torsion_points() |

615 | sage: phi = EllipticCurveIsogeny(E, P_list) |

616 | sage: phi |

617 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 3*x + 4 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 27*x + 46 over Rational Field |

618 | sage: P = E((0,2)) |

619 | sage: phi(P) |

620 | (6 : -10 : 1) |

621 | sage: phi_ker_poly = phi.kernel_polynomial() |

622 | sage: phi_ker_poly |

623 | x + 1 |

624 | sage: ker_poly_list = phi_ker_poly.list() |

625 | sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k |

626 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 3*x + 4 over Rational Field to Elliptic Curve defined by y^2 = x^3 - 27*x + 46 over Rational Field |

627 | sage: phi_k(P) == phi(P) |

628 | True |

629 | sage: phi_k == phi |

630 | True |

631 | sage: phi_k.degree() |

632 | 2 |

633 | sage: phi_k.is_separable() |

634 | True |

635 | |

636 | A more complicated example over the rationals (of odd degree):: |

637 | |

638 | sage: E = EllipticCurve('11a1') |

639 | sage: P_list = E.torsion_points() |

640 | sage: phi_v = EllipticCurveIsogeny(E, P_list); phi_v |

641 | Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field |

642 | sage: P = E((16,-61)) |

643 | sage: phi_v(P) |

644 | (0 : 1 : 0) |

645 | sage: ker_poly = phi_v.kernel_polynomial(); ker_poly |

646 | x^2 - 21*x + 80 |

647 | sage: ker_poly_list = ker_poly.list() |

648 | sage: phi_k = EllipticCurveIsogeny(E, ker_poly_list); phi_k |

649 | Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field |

650 | sage: phi_k == phi_v |

651 | True |

652 | sage: phi_v(P) == phi_k(P) |

653 | True |

654 | sage: phi_k.is_separable() |

655 | True |

656 | |

657 | We can also do this same example over the number field defined by |

658 | the irreducible two torsion polynomial of `E`:: |

659 | |

660 | sage: E = EllipticCurve('11a1') |

661 | sage: P_list = E.torsion_points() |

662 | sage: K.<alpha> = NumberField(x^3 - 2* x^2 - 40*x - 158) |

663 | sage: EK = E.change_ring(K) |

664 | sage: P_list = [EK(P) for P in P_list] |

665 | sage: phi_v = EllipticCurveIsogeny(EK, P_list); phi_v |

666 | Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 to Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-7820)*x + (-263580) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 |

667 | sage: P = EK((alpha/2,-1/2)) |

668 | sage: phi_v(P) |

669 | (122/121*alpha^2 + 1633/242*alpha - 3920/121 : -1/2 : 1) |

670 | sage: ker_poly = phi_v.kernel_polynomial() |

671 | sage: ker_poly |

672 | x^2 - 21*x + 80 |

673 | sage: ker_poly_list = ker_poly.list() |

674 | sage: phi_k = EllipticCurveIsogeny(EK, ker_poly_list) |

675 | sage: phi_k |

676 | Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 to Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-7820)*x + (-263580) over Number Field in alpha with defining polynomial x^3 - 2*x^2 - 40*x - 158 |

677 | sage: phi_v == phi_k |

678 | True |

679 | sage: phi_k(P) == phi_v(P) |

680 | True |

681 | sage: phi_k == phi_v |

682 | True |

683 | sage: phi_k.degree() |

684 | 5 |

685 | sage: phi_v.is_separable() |

686 | True |

687 | |

688 | The following example shows how to specify an isogeny from domain |

689 | and codomain:: |

690 | |

691 | sage: E = EllipticCurve('11a1') |

692 | sage: R.<x> = QQ[] |

693 | sage: f = x^2 - 21*x + 80 |

694 | sage: phi = E.isogeny(f) |

695 | sage: E2 = phi.codomain() |

696 | sage: phi_s = EllipticCurveIsogeny(E, None, E2, 5) |

697 | sage: phi_s |

698 | Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field |

699 | sage: phi_s == phi |

700 | True |

701 | sage: phi_s.rational_maps() == phi.rational_maps() |

702 | True |

703 | |

704 | However only cyclic normalized isogenies can be constructed this |

705 | way. So it won't find the isogeny [3]:: |

706 | |

707 | sage: E.isogeny(None, codomain=E,degree=9) |

708 | Traceback (most recent call last): |

709 | ... |

710 | ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 9 |

711 | |

712 | Also the presumed isogeny between the domain and codomain must be |

713 | normalized:: |

714 | |

715 | sage: E2.isogeny(None,codomain=E,degree=5) |

716 | Traceback (most recent call last): |

717 | ... |

718 | ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 5 |

719 | sage: phi.dual() |

720 | Isogeny of degree 5 from Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field |

721 | sage: phi.dual().is_normalized() |

722 | False |

723 | |

724 | Here an example of a construction of a endomorphisms with cyclic |

725 | kernel on a CM-curve:: |

726 | |

727 | sage: K.<i> = NumberField(x^2+1) |

728 | sage: E = EllipticCurve(K, [1,0]) |

729 | sage: RK.<X> = K[] |

730 | sage: f = X^2 - 2/5*i + 1/5 |

731 | sage: phi= E.isogeny(f) |

732 | sage: isom = phi.codomain().isomorphism_to(E) |

733 | sage: phi.set_post_isomorphism(isom) |

734 | sage: phi.codomain() == phi.domain() |

735 | True |

736 | sage: phi.rational_maps() |

737 | (((4/25*i + 3/25)*x^5 + (4/5*i - 2/5)*x^3 - x)/(x^4 + (-4/5*i + 2/5)*x^2 + (-4/25*i - 3/25)), |

738 | ((11/125*i + 2/125)*x^6*y + (-23/125*i + 64/125)*x^4*y + (141/125*i + 162/125)*x^2*y + (3/25*i - 4/25)*y)/(x^6 + (-6/5*i + 3/5)*x^4 + (-12/25*i - 9/25)*x^2 + (2/125*i - 11/125))) |

739 | """ |

740 | |

741 | #################### |

742 | # member variables |

743 | #################### |

744 | __check = None |

745 | # |

746 | # variables common to all algorithms |

747 | # |

748 | __E1 = None # domain curve |

749 | __E2 = None # codomain curve |

750 | |

751 | __degree = None |

752 | |

753 | __separable = True # This class only implements separable isogenies (for now.) |

754 | |

755 | __algorithm = None |

756 | |

757 | __this_hash = None |

758 | |

759 | __check = None |

760 | # |

761 | # pre isomorphism |

762 | # |

763 | __intermediate_domain = None |

764 | __pre_isomorphism = None |

765 | __prei_x_coord_ratl_map = None |

766 | __prei_y_coord_ratl_map = None |

767 | |

768 | # |

769 | # post isomorphism |

770 | # |

771 | |

772 | __intermediate_codomain = None |

773 | __post_isomorphism = None |

774 | __posti_x_coord_ratl_map = None |

775 | __posti_y_coord_ratl_map = None |

776 | |

777 | # |

778 | # algebraic structs |

779 | # |

780 | __base_field = None |

781 | __poly_ring = None |

782 | __x_var = None |

783 | __y_var = None |

784 | |

785 | # |

786 | # Rational Maps |

787 | # |

788 | __rational_maps_initialized = False |

789 | __X_coord_rational_map = None |

790 | __Y_coord_rational_map = None |

791 | |

792 | # |

793 | # The dual |

794 | # |

795 | __dual = None |

796 | |

797 | # |

798 | # Kernel Data |

799 | # |

800 | |

801 | __kernel_list = None # list of elements in the kernel |

802 | |

803 | __kernel_polynomial_list = None # polynomial stored as a little endian list of coefficients |

804 | |

805 | __kernel_polynomial = None # polynomial with roots at x values for x-coordinate of points in the kernel |

806 | |

807 | __inner_kernel_polynomial = None # the inner kernel polynomial (ignoring preisomorphism) |

808 | |

809 | __n = None |

810 | |

811 | |

812 | # |

813 | # member variables common to Velu's formula |

814 | # |

815 | |

816 | # we keep track of the 2 torsion and non2torsion separately |

817 | __kernel_2tor = None |

818 | __kernel_non2tor = None |

819 | |

820 | # variables used in Velu's formula (as well as Kohel's variant) |

821 | __v = None |

822 | __w = None |

823 | |

824 | |

825 | # |

826 | # member variables specific to Kohel's algorithm. |

827 | # |

828 | |

829 | __psi = None # psi polynomial |

830 | __phi = None # phi polynomial |

831 | __omega = None # omega polynomial |

832 | |

833 | |

834 | # |

835 | # Python Special Functions |

836 | # |

837 | |

838 | def __init__(self, E, kernel, codomain=None, degree=None, model=None, check=True): |

839 | r""" |

840 | Constructor for EllipticCurveIsogeny class. |

841 | |

842 | EXAMPLES:: |

843 | |

844 | sage: E = EllipticCurve(GF(2), [0,0,1,0,1]) |

845 | sage: phi = EllipticCurveIsogeny(E, [1,1]) |

846 | sage: phi |

847 | Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 + 1 over Finite Field of size 2 to Elliptic Curve defined by y^2 + y = x^3 over Finite Field of size 2 |

848 | |

849 | sage: E = EllipticCurve(GF(31), [0,0,0,1,0]) |

850 | sage: P = E((2,17)) |

851 | sage: phi = EllipticCurveIsogeny(E, P) |

852 | sage: phi |

853 | Isogeny of degree 8 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 31 to Elliptic Curve defined by y^2 = x^3 + 10*x + 28 over Finite Field of size 31 |

854 | |

855 | sage: E = EllipticCurve('17a1') |

856 | sage: phi = EllipticCurveIsogeny(E, [41/3, -55, -1, -1, 1]) |

857 | sage: phi |

858 | Isogeny of degree 9 from Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 - x - 14 over Rational Field to Elliptic Curve defined by y^2 + x*y + y = x^3 - x^2 - 56*x - 10124 over Rational Field |

859 | |

860 | sage: E = EllipticCurve('37a1') |

861 | sage: triv = EllipticCurveIsogeny(E, E(0)) |

862 | sage: triv |

863 | Isogeny of degree 1 from Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field |

864 | sage: triv.rational_maps() |

865 | (x, y) |

866 | |

867 | sage: E = EllipticCurve('49a3') |

868 | sage: R.<X> = QQ[] |

869 | sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False) |

870 | Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 107*x + 552 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 5252*x - 178837 over Rational Field |

871 | |

872 | """ |

873 | if not is_EllipticCurve(E): |

874 | raise ValueError, "E parameter must be an EllipticCurve." |

875 | |

876 | if type(kernel) != type([1,1]) and kernel in E : |

877 | # a single point was given, we put it in a list |

878 | # the first condition assures that [1,1] is treated as x+1 |

879 | kernel = [kernel] |

880 | |

881 | # if the kernel is None and the codomain isn't |

882 | # calculate the kernel polynomial |

883 | pre_isom = None |

884 | post_isom = None |

885 | |

886 | self.__check = check |

887 | |

888 | if (kernel is None) and (codomain is not None): |

889 | |

890 | if (degree is None): |

891 | raise ValueError, "If specifying isogeny by domain and codomain, degree parameter must be set." |

892 | |

893 | # save the domain/codomain: really used now (trac #7096) |

894 | old_domain = E |

895 | old_codomain = codomain |

896 | |

897 | (pre_isom, post_isom, E, codomain, kernel) = compute_sequence_of_maps(E, codomain, degree) |

898 | self.__init_algebraic_structs(E) |

899 | |

900 | algorithm = isogeny_determine_algorithm(E, kernel, codomain, degree, model); |

901 | |

902 | self.__algorithm = algorithm |

903 | |

904 | if ("velu"==algorithm): |

905 | self.__init_from_kernel_list(kernel) |

906 | elif ("kohel"==algorithm): |

907 | self.__init_from_kernel_polynomial(kernel, degree) |

908 | |

909 | self.__compute_E2() |

910 | |

911 | self.__setup_post_isomorphism(codomain, model) |

912 | |

913 | if (pre_isom is not None): |

914 | self.set_pre_isomorphism(pre_isom) |

915 | |

916 | if (post_isom is not None): |

917 | self.__set_post_isomorphism(old_codomain, post_isom) #(trac #7096) |

918 | |

919 | # Inheritance house keeping |

920 | |

921 | self.__perform_inheritance_housekeeping() |

922 | |

923 | return |

924 | |

925 | # S.Besnier 31/3/2014 : __call__ -> _call_ in order to use Map __call__ |

926 | def _call_(self, P, output_base_ring=None): |

927 | r""" |

928 | Function that implements the call-ability of elliptic curve |

929 | isogenies. |

930 | |

931 | EXAMPLES:: |

932 | |

933 | sage: E = EllipticCurve(GF(17), [1, 9, 5, 4, 3]) |

934 | sage: phi = EllipticCurveIsogeny(E, [6,13,1]) |

935 | sage: phi(E((1,0))) |

936 | (15 : 13 : 1) |

937 | |

938 | sage: E = EllipticCurve(GF(23), [0,0,0,1,0]) |

939 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

940 | sage: phi(E((1,5))) |

941 | (2 : 0 : 1) |

942 | sage: phi(E(15,20), output_base_ring=GF(23^2,'alpha')) |

943 | (12 : 1 : 1) |

944 | |

945 | sage: E = EllipticCurve(QQ, [0,0,0,3,0]) |

946 | sage: P = E((1,2)) |

947 | sage: phi = EllipticCurveIsogeny(E, [0,1]) |

948 | sage: phi(P) |

949 | (4 : -4 : 1) |

950 | sage: phi(-P) |

951 | (4 : 4 : 1) |

952 | |

953 | sage: E = EllipticCurve(GF(17), [0,-1,0,-3,-1]) |

954 | sage: Q = E((16,0)) |

955 | sage: tau = E.isogeny([Q],E) |

956 | sage: tau(Q) |

957 | (0 : 1 : 0) |

958 | |

959 | TESTS (trac 10888):: |

960 | |

961 | sage: K.<th> = NumberField(x^2+3) |

962 | sage: E = EllipticCurve(K,[7,0]) |

963 | sage: phi = E.isogeny(E(0,0)) |

964 | sage: P = E(-3,4*th) |

965 | sage: phi(P) |

966 | (-16/3 : 8/9*th : 1) |

967 | sage: Q = phi(P) |

968 | sage: phihat = phi.dual() |

969 | sage: phihat(Q) |

970 | (-1/48 : 127/576*th : 1) |

971 | |

972 | """ |

973 | E1 = self.__E1 |

974 | E_P = P.curve() |

975 | change_output_ring = False |

976 | |

977 | # check that the parent curve of the input point is this curve |

978 | # or that the point is on the same curve but whose base ring |

979 | # is an extension of this ring |

980 | if (E1 != E_P): |

981 | if (E1.a_invariants() != E_P.a_invariants()) : |

982 | raise ValueError, "P must be on a curve with same Weierstrass model as the domain curve of this isogeny." |

983 | change_output_ring = True |

984 | |

985 | |

986 | if(P.is_zero()): |

987 | return self.__E2(0) |

988 | |

989 | (xP, yP) = P.xy() |

990 | |

991 | if not self.__E1.is_on_curve(xP,yP): |

992 | raise InputError, "Input point must be on the domain curve of this isogeny." |

993 | |

994 | # if there is a pre isomorphism, apply it |

995 | if (self.__pre_isomorphism is not None): |

996 | temp_xP = self.__prei_x_coord_ratl_map(xP, yP) |

997 | temp_yP = self.__prei_y_coord_ratl_map(xP, yP) |

998 | (xP, yP) = (temp_xP, temp_yP) |

999 | |

1000 | if ("velu" == self.__algorithm): |

1001 | outP = self.__compute_via_velu_numeric(xP, yP) |

1002 | elif ("kohel" == self.__algorithm): |

1003 | outP = self.__compute_via_kohel_numeric(xP,yP) |

1004 | |

1005 | # the intermediate functions return the point at infinity |

1006 | # if the input point is in the kernel |

1007 | if (outP == self.__intermediate_codomain(0)): |

1008 | return self.__E2(0) |

1009 | |

1010 | # if there is a post isomorphism, apply it |

1011 | if (self.__post_isomorphism is not None): |

1012 | tempX = self.__posti_x_coord_ratl_map(outP[0], outP[1]) |

1013 | tempY = self.__posti_y_coord_ratl_map(outP[0], outP[1]) |

1014 | outP = [tempX, tempY] |

1015 | |

1016 | if change_output_ring: |

1017 | if (output_base_ring is None): |

1018 | output_base_ring = E_P.base_ring() |

1019 | outE2 = self.__E2.change_ring(output_base_ring) |

1020 | else: |

1021 | output_base_ring = self.__E2.base_ring() |

1022 | outE2 = self.__E2 |

1023 | outP = self.__E2.point(outP,check=False) |

1024 | |

1025 | R = output_base_ring |

1026 | |

1027 | return outE2.point([R(outP[0]), R(outP[1]), R(1)], check=False) |

1028 | |

1029 | |

1030 | def __getitem__(self, i): |

1031 | self.__initialize_rational_maps() |

1032 | if (i < 0) or (i > 2): |

1033 | raise IndexError |

1034 | |

1035 | if i == 0: |

1036 | return self.__X_coord_rational_map |

1037 | else: |

1038 | return self.__Y_coord_rational_map |

1039 | |

1040 | def __iter__(self): |

1041 | self.__initialize_rational_maps() |

1042 | return iter((self.__X_coord_rational_map, self.__Y_coord_rational_map)) |

1043 | |

1044 | def __hash__(self): |

1045 | r""" |

1046 | Function that implements the hash ability of Isogeny objects. |

1047 | |

1048 | This hashes the underlying kernel polynomial so that equal |

1049 | isogeny objects have the same hash value. Also, this hashes |

1050 | the base field, and domain and codomain curves as well, so |

1051 | that isogenies with the same kernel polynomial (over different |

1052 | base fields / curves) hash to different values. |

1053 | |

1054 | EXAMPLES:: |

1055 | |

1056 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

1057 | sage: phi_v = EllipticCurveIsogeny(E, E((0,0))) |

1058 | sage: phi_k = EllipticCurveIsogeny(E, [0,1]) |

1059 | sage: phi_k.__hash__() == phi_v.__hash__() |

1060 | True |

1061 | sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,1]) |

1062 | sage: phi_p = EllipticCurveIsogeny(E_F17, E_F17([0,1])) |

1063 | sage: phi_p.__hash__() == phi_v.__hash__() |

1064 | False |

1065 | |

1066 | sage: E = EllipticCurve('49a3') |

1067 | sage: R.<X> = QQ[] |

1068 | sage: EllipticCurveIsogeny(E,X^3-13*X^2-58*X+503,check=False) |

1069 | Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 107*x + 552 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - x^2 - 5252*x - 178837 over Rational Field |

1070 | |

1071 | """ |

1072 | |

1073 | if (self.__this_hash is not None): |

1074 | return self.__this_hash |

1075 | |

1076 | ker_poly_list = self.__kernel_polynomial_list |

1077 | |

1078 | if (ker_poly_list is None): |

1079 | ker_poly_list = self.__init_kernel_polynomial() |

1080 | |

1081 | this_hash = 0 |

1082 | |

1083 | for a in ker_poly_list: |

1084 | this_hash = this_hash.__xor__(hash(a)) |

1085 | |

1086 | this_hash = this_hash.__xor__(hash(self.__E1)) |

1087 | this_hash = this_hash.__xor__(hash(self.__E2)) |

1088 | this_hash = this_hash.__xor__(hash(self.__base_field)) |

1089 | |

1090 | self.__this_hash = this_hash |

1091 | |

1092 | return self.__this_hash |

1093 | |

1094 | |

1095 | def __cmp__(self, other): |

1096 | r""" |

1097 | Function that implements comparisons between isogeny objects. |

1098 | |

1099 | This function works by comparing the underlying kernel |

1100 | objects. |

1101 | |

1102 | EXAMPLES:: |

1103 | |

1104 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

1105 | sage: phi_v = EllipticCurveIsogeny(E, E((0,0))) |

1106 | sage: phi_k = EllipticCurveIsogeny(E, [0,1]) |

1107 | sage: phi_k == phi_v |

1108 | True |

1109 | sage: E_F17 = EllipticCurve(GF(17), [0,0,0,1,0]) |

1110 | sage: phi_p = EllipticCurveIsogeny(E_F17, [0,1]) |

1111 | sage: phi_p == phi_v |

1112 | False |

1113 | sage: E = EllipticCurve('11a1') |

1114 | sage: phi = E.isogeny(E(5,5)) |

1115 | sage: psi = E.isogeny(phi.kernel_polynomial()) |

1116 | sage: phi == psi |

1117 | True |

1118 | sage: phi.dual() == psi.dual() |

1119 | True |

1120 | |

1121 | |

1122 | """ |

1123 | if (not isinstance(other, EllipticCurveIsogeny)): |

1124 | return -1 |

1125 | |

1126 | if (self.__kernel_polynomial is None): |

1127 | self.__init_kernel_polynomial() |

1128 | |

1129 | return cmp(self.__kernel_polynomial, other.kernel_polynomial()) |

1130 | |

1131 | |

1132 | def __neg__(self): |

1133 | r""" |

1134 | Function to implement unary negation (-) operator on |

1135 | isogenies. Returns a copy of this isogeny that has been |

1136 | negated. |

1137 | |

1138 | EXAMPLES: |

1139 | |

1140 | The following examples inherently exercise this function:: |

1141 | |

1142 | sage: E = EllipticCurve(j=GF(17)(0)) |

1143 | sage: phi = EllipticCurveIsogeny(E, E((-1,0)) ) |

1144 | sage: negphi = -phi |

1145 | sage: phi(E((0,1))) + negphi(E((0,1))) |

1146 | (0 : 1 : 0) |

1147 | |

1148 | sage: E = EllipticCurve(j=GF(19)(1728)) |

1149 | sage: R.<x> = GF(19)[] |

1150 | sage: phi = EllipticCurveIsogeny(E, x) |

1151 | sage: negphi = -phi |

1152 | sage: phi(E((3,7))) + negphi(E((3,12))) == phi(2*E((3,7))) |

1153 | True |

1154 | sage: negphi(E((18,6))) |

1155 | (17 : 0 : 1) |

1156 | |

1157 | sage: R.<x> = QQ[] |

1158 | sage: E = EllipticCurve('17a1') |

1159 | sage: R.<x> = QQ[] |

1160 | sage: f = x - 11/4 |

1161 | sage: phi = EllipticCurveIsogeny(E, f) |

1162 | sage: negphi = -phi |

1163 | sage: phi.rational_maps()[0] == negphi.rational_maps()[0] |

1164 | True |

1165 | sage: P = E((7,13)) |

1166 | sage: phi(P) + negphi(P) |

1167 | (0 : 1 : 0) |

1168 | |

1169 | """ |

1170 | # save off the kernel lists |

1171 | kernel_list = self.__kernel_list |

1172 | self.__kernel_list = None |

1173 | |

1174 | output = deepcopy(self) |

1175 | |

1176 | # reset the kernel lists |

1177 | output.__kernel_list = copy(kernel_list) |

1178 | self.__kernel_list = kernel_list |

1179 | |

1180 | output.switch_sign() |

1181 | return output |

1182 | |

1183 | |

1184 | |

1185 | # |

1186 | # Sage Special Functions |

1187 | # |

1188 | |

1189 | def _repr_(self): |

1190 | r""" |

1191 | Special sage specific function that implement the |

1192 | functionality to display the isogeny self as a string. |

1193 | |

1194 | EXAMPLES:: |

1195 | |

1196 | sage: E = EllipticCurve(GF(31), [1,0,1,1,0]) |

1197 | sage: phi = EllipticCurveIsogeny(E, E((0,0)) ) |

1198 | sage: phi._repr_() |

1199 | 'Isogeny of degree 17 from Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 31 to Elliptic Curve defined by y^2 + x*y + y = x^3 + 14*x + 9 over Finite Field of size 31' |

1200 | |

1201 | sage: E = EllipticCurve(QQ, [1,0,0,1,9]) |

1202 | sage: phi = EllipticCurveIsogeny(E, [2,1]) |

1203 | sage: phi._repr_() |

1204 | 'Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y = x^3 + x + 9 over Rational Field to Elliptic Curve defined by y^2 + x*y = x^3 - 59*x + 165 over Rational Field' |

1205 | |

1206 | """ |

1207 | s= 'Isogeny of degree ' + self.__degree.__repr__() + ':\n From: ' + \ |

1208 | self.domain().__repr__() + '\n To: ' + self.codomain().__repr__() |

1209 | d = self._repr_defn() |

1210 | if d != '': |

1211 | s += "\n Defn: %s"%('\n '.join(self._repr_defn().split('\n'))) |

1212 | return s |

1213 | |

1214 | def _latex_(self): |

1215 | r""" |

1216 | Special sage specific function that implements functionality |

1217 | to display an isogeny object as a latex string. |

1218 | |

1219 | This function returns a latex string representing the isogeny |

1220 | self as the `x` and `y` coordinate rational functions. |

1221 | |

1222 | EXAMPLES:: |

1223 | |

1224 | sage: E = EllipticCurve(QQ, [0,0,0,1,-1]) |

1225 | sage: phi = EllipticCurveIsogeny(E, E(0)) |

1226 | sage: phi._latex_() |

1227 | '\\left( x , y \\right)' |

1228 | |

1229 | sage: E = EllipticCurve(GF(17), [0,0,0,1,-1]) |

1230 | sage: R.<X> = GF(17)[] |

1231 | sage: phi = EllipticCurveIsogeny(E, X+11) |

1232 | sage: phi._latex_() |

1233 | '\\left( \\frac{x^{2} + 11 x + 7}{x + 11} , \\frac{x^{2} y + 5 x y + 12 y}{x^{2} + 5 x + 2} \\right)' |

1234 | |

1235 | |

1236 | """ |

1237 | ratl_maps = self.rational_maps() |

1238 | return '\\left( %s , %s \\right)' % (ratl_maps[0]._latex_(), ratl_maps[1]._latex_()) |

1239 | |

1240 | |

1241 | ########################### |

1242 | # Private Common Functions |

1243 | ########################### |

1244 | |

1245 | # delete the hash value |

1246 | def __clear_cached_values(self): |

1247 | r""" |

1248 | A private function to clear the hash if the codomain has been |

1249 | modified by a pre or post isomorphism. |

1250 | |

1251 | EXAMPLES:: |

1252 | |

1253 | sage: F = GF(7); |

1254 | sage: E = EllipticCurve(j=F(0)) |

1255 | sage: phi = EllipticCurveIsogeny(E, [E((0,-1)), E((0,1))]) |

1256 | sage: old_hash = hash(phi) |

1257 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

1258 | sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,2,-3,4))) |

1259 | sage: hash(phi) == old_hash |

1260 | False |

1261 | |

1262 | sage: R.<x> = QQ[] |

1263 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

1264 | sage: phi = EllipticCurveIsogeny(E, x) |

1265 | sage: old_ratl_maps = phi.rational_maps() |

1266 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

1267 | sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-1,0,0,0))) |

1268 | sage: old_ratl_maps == phi.rational_maps() |

1269 | False |

1270 | sage: old_ratl_maps[1] == -phi.rational_maps()[1] |

1271 | True |

1272 | |

1273 | sage: F = GF(127); R.<x> = F[] |

1274 | sage: E = EllipticCurve(j=F(1728)) |

1275 | sage: f = x^5 + 43*x^4 + 97*x^3 + 81*x^2 + 42*x + 82 |

1276 | sage: phi = EllipticCurveIsogeny(E, f) |

1277 | sage: old_hash = hash(phi) |

1278 | sage: old_ratl_maps = phi.rational_maps() |

1279 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

1280 | sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (-13,13,-13,13))) |

1281 | sage: old_hash == hash(phi) |

1282 | False |

1283 | sage: old_ratl_maps == phi.rational_maps() |

1284 | False |

1285 | sage: phi._EllipticCurveIsogeny__clear_cached_values() |

1286 | |

1287 | """ |

1288 | self.__this_hash = None |

1289 | self.__rational_maps_initialized = False |

1290 | self.__X_coord_rational_map = None |

1291 | self.__Y_coord_rational_map = None |

1292 | self.__dual |

1293 | |

1294 | |

1295 | # performs the inheritance house keeping |

1296 | def __perform_inheritance_housekeeping(self): |

1297 | r""" |

1298 | Internal helper function, sets values on the super classes of |

1299 | this class. |

1300 | |

1301 | EXAMPLES: |

1302 | |

1303 | The following examples will implicitly exercise this |

1304 | function:: |

1305 | |

1306 | sage: E = EllipticCurve(GF(43), [2,3,5,7,11]) |

1307 | sage: R.<x> = GF(43)[]; f = x + 42 |

1308 | sage: phi = EllipticCurveIsogeny(E, f) |

1309 | sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping() |

1310 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

1311 | sage: E2 = phi.codomain() |

1312 | sage: post_isom = WeierstrassIsomorphism(E2, (41, 37, 31, 29)) |

1313 | sage: phi.set_post_isomorphism(post_isom) |

1314 | sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain() |

1315 | sage: pre_isom = E1pr.isomorphism_to(E) |

1316 | sage: phi.set_pre_isomorphism(pre_isom) |

1317 | |

1318 | """ |

1319 | |

1320 | # one of the superclasses uses these fields |

1321 | self._domain = self.__E1 |

1322 | self._codomain = self.__E2 |

1323 | |

1324 | # sets up the parent |

1325 | parent = homset.Hom(self.__E1(0).parent(), self.__E2(0).parent()) |

1326 | Morphism.__init__(self, parent) |

1327 | |

1328 | return |

1329 | |

1330 | |

1331 | # initializes the base field |

1332 | def __init_algebraic_structs(self, E): |

1333 | r""" |

1334 | An internal function for EllipticCurveIsogeny objects that |

1335 | sets up the member variables necessary for algebra. |

1336 | |

1337 | EXAMPLES: |

1338 | |

1339 | The following tests inherently exercise this function:: |

1340 | |

1341 | sage: E = EllipticCurve(j=GF(17)(0)) |

1342 | sage: phi = EllipticCurveIsogeny(E, E((-1,0))) |

1343 | sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E) |

1344 | |

1345 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

1346 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

1347 | sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E) |

1348 | |

1349 | sage: F = GF(19); R.<x> = F[] |

1350 | sage: E = EllipticCurve(j=GF(19)(0)) |

1351 | sage: phi = EllipticCurveIsogeny(E, x) |

1352 | sage: phi._EllipticCurveIsogeny__init_algebraic_structs(E) |

1353 | |

1354 | """ |

1355 | self.__E1 = E |

1356 | self.__base_field = E.base_ring() |

1357 | |

1358 | poly_ring = self.__poly_ring = PolynomialRing(self.__base_field, ['x','y']) |

1359 | |

1360 | self.__x_var = poly_ring('x') |

1361 | self.__y_var = poly_ring('y') |

1362 | |

1363 | self.__intermediate_domain = E |

1364 | |

1365 | return |

1366 | |

1367 | |

1368 | def __compute_E2(self): |

1369 | r""" |

1370 | Private function that computes and sets the isogeny codomain. |

1371 | |

1372 | EXAMPLES: |

1373 | |

1374 | These examples inherently exercise this function:: |

1375 | |

1376 | sage: E = EllipticCurve(j=GF(7)(1728)) |

1377 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

1378 | sage: phi.codomain() |

1379 | Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 7 |

1380 | sage: phi._EllipticCurveIsogeny__compute_E2() |

1381 | |

1382 | sage: R.<x> = GF(7)[] |

1383 | sage: phi = EllipticCurveIsogeny(E, x) |

1384 | sage: phi.codomain() |

1385 | Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 7 |

1386 | sage: phi._EllipticCurveIsogeny__compute_E2() |

1387 | |

1388 | """ |

1389 | |

1390 | if ("velu" == self.__algorithm): |

1391 | E2 = self.__compute_E2_via_velu() |

1392 | elif ("kohel" == self.__algorithm): |

1393 | E2 = self.__compute_E2_via_kohel() |

1394 | |

1395 | self.__E2 = E2 |

1396 | self.__intermediate_codomain = E2 |

1397 | |

1398 | return |

1399 | |

1400 | |

1401 | # initializes the rational maps fields |

1402 | def __initialize_rational_maps(self, precomputed_maps=None): |

1403 | r""" |

1404 | Private function that computes and initializes the rational |

1405 | maps. |

1406 | |

1407 | INPUT: |

1408 | |

1409 | - `` |

1410 | |

1411 | EXAMPLES: |

1412 | |

1413 | The following examples inherently exercise this function:: |

1414 | |

1415 | sage: E = EllipticCurve(j=GF(7)(1728)) |

1416 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

1417 | sage: phi._EllipticCurveIsogeny__initialize_rational_maps() |

1418 | sage: phi.rational_maps() |

1419 | ((x^2 + 1)/x, (x^2*y - y)/x^2) |

1420 | |

1421 | sage: R.<x> = GF(7)[] |

1422 | sage: phi = EllipticCurveIsogeny(E, x) |

1423 | sage: phi = EllipticCurveIsogeny(E, x) |

1424 | sage: phi.rational_maps() |

1425 | ((x^2 + 1)/x, (x^2*y - y)/x^2) |

1426 | sage: phi._EllipticCurveIsogeny__initialize_rational_maps() |

1427 | |

1428 | sage: E = EllipticCurve([1,2,3,4,5]) |

1429 | sage: Eshort = E.short_weierstrass_model() |

1430 | sage: phi = E.isogeny(E(0), Eshort) |

1431 | sage: phiX, phiY = phi.rational_maps() |

1432 | sage: phiX(1,2), phiY(1,2) |

1433 | (63, 864) |

1434 | """ |

1435 | if self.__rational_maps_initialized: |

1436 | return |

1437 | |

1438 | if precomputed_maps is None: |

1439 | if ("velu"==self.__algorithm): |

1440 | (X_map, Y_map) = self.__initialize_rational_maps_via_velu() |

1441 | if ("kohel"==self.__algorithm): |

1442 | (X_map, Y_map) = self.__initialize_rational_maps_via_kohel() |

1443 | else: |

1444 | X_map, Y_map = precomputed_maps |

1445 | |

1446 | if self.__prei_x_coord_ratl_map is not None: |

1447 | prei_X_map = self.__prei_x_coord_ratl_map |

1448 | prei_Y_map = self.__prei_y_coord_ratl_map |

1449 | X_map, Y_map = X_map.subs(x=prei_X_map, y=prei_Y_map), \ |

1450 | Y_map.subs(x=prei_X_map, y=prei_Y_map) |

1451 | |

1452 | if self.__posti_x_coord_ratl_map is not None: |

1453 | X_map, Y_map = \ |

1454 | self.__posti_x_coord_ratl_map.subs(x=X_map, y=Y_map), \ |

1455 | self.__posti_y_coord_ratl_map.subs(x=X_map, y=Y_map) |

1456 | |

1457 | self.__X_coord_rational_map = X_map |

1458 | self.__Y_coord_rational_map = Y_map |

1459 | self.__rational_maps_initialized = True |

1460 | |

1461 | |

1462 | def __init_kernel_polynomial(self): |

1463 | r""" |

1464 | Private function that initializes the kernel polynomial (if |

1465 | the algorithm does not take it as a parameter.) |

1466 | |

1467 | EXAMPLES: |

1468 | |

1469 | The following examples inherently exercise this function:: |

1470 | |

1471 | sage: E = EllipticCurve(j=GF(7)(1728)) |

1472 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

1473 | sage: phi.kernel_polynomial() |

1474 | x |

1475 | sage: phi._EllipticCurveIsogeny__init_kernel_polynomial() |

1476 | [0, 1] |

1477 | |

1478 | """ |

1479 | |

1480 | if (self.__kernel_polynomial_list is not None): |

1481 | return self.__kernel_polynomial_list |

1482 | |

1483 | if ("velu" == self.__algorithm): |

1484 | ker_poly_list = self.__init_kernel_polynomial_velu() |

1485 | else: |

1486 | raise InputError, "The kernel polynomial should already be defined!" |

1487 | |

1488 | return ker_poly_list |

1489 | |

1490 | |

1491 | def __set_pre_isomorphism(self, domain, isomorphism): |

1492 | r""" |

1493 | Private function to set the pre isomorphism and domain (and |

1494 | keep track of the domain of the isogeny.) |

1495 | |

1496 | EXAMPLES:: |

1497 | |

1498 | sage: E = EllipticCurve(GF(43), [2,3,5,7,11]) |

1499 | sage: R.<x> = GF(43)[]; f = x + 42 |

1500 | sage: phi = EllipticCurveIsogeny(E, f) |

1501 | sage: phi._EllipticCurveIsogeny__perform_inheritance_housekeeping() |

1502 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

1503 | sage: E1pr = WeierstrassIsomorphism(E, (-1, 2, -3, 4)).codomain().codomain() |

1504 | sage: pre_isom = E1pr.isomorphism_to(E) |

1505 | sage: phi.set_pre_isomorphism(pre_isom) |

1506 | sage: phi._EllipticCurveIsogeny__set_pre_isomorphism(E, WeierstrassIsomorphism(E, (-1, 3, -3, 4))) |

1507 | sage: E == phi.domain() |

1508 | True |

1509 | |

1510 | """ |

1511 | |

1512 | self.__E1 = domain |

1513 | |

1514 | # set the isomorphism |

1515 | self.__pre_isomorphism = isomorphism |

1516 | |

1517 | # calculate the isomorphism as a rational map. |

1518 | |

1519 | (u, r, s, t) = isomorphism.tuple() |

1520 | |

1521 | x = self.__x_var; |

1522 | y = self.__y_var; |

1523 | |

1524 | self.__prei_x_coord_ratl_map = (x - r)/u**2 |

1525 | self.__prei_y_coord_ratl_map = (y - s*(x-r) - t)/u**3 |

1526 | |

1527 | if (self.__kernel_polynomial is not None): |

1528 | ker_poly = self.__kernel_polynomial |

1529 | ker_poly = ker_poly.subs(x=self.__prei_x_coord_ratl_map) |

1530 | kp_lc = ker_poly.univariate_polynomial().leading_coefficient() |

1531 | ker_poly = (1/kp_lc)*ker_poly |

1532 | self.__kernel_polynomial = ker_poly |

1533 | |

1534 | self.__perform_inheritance_housekeeping() |

1535 | |

1536 | return; |

1537 | |

1538 | |

1539 | def __set_post_isomorphism(self, codomain, isomorphism): |

1540 | r""" |

1541 | Private function to set the post isomorphism and codomain (and |

1542 | keep track of the codomain of the isogeny.) |

1543 | |

1544 | EXAMPLES: |

1545 | |

1546 | The following examples inherently exercise this function:: |

1547 | |

1548 | sage: E = EllipticCurve(j=GF(7)(1728)) |

1549 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

1550 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

1551 | sage: E2 = phi.codomain() |

1552 | sage: isom = WeierstrassIsomorphism(E2, (-1,2,-3,4)) |

1553 | sage: phi.set_post_isomorphism(isom) |

1554 | sage: phi._EllipticCurveIsogeny__set_post_isomorphism(E2, WeierstrassIsomorphism(phi.codomain(), (1,-2,3,-4))) |

1555 | sage: E2 == phi.codomain() |

1556 | True |

1557 | |

1558 | """ |

1559 | |

1560 | # set the codomains |

1561 | self.__E2 = codomain |

1562 | |

1563 | # set the isomorphism |

1564 | self.__post_isomorphism = isomorphism |

1565 | |

1566 | # calculate the isomorphism as a rational map. |

1567 | |

1568 | (u, r, s, t) = isomorphism.tuple() |

1569 | |

1570 | x = self.__x_var; |

1571 | y = self.__y_var; |

1572 | |

1573 | self.__posti_x_coord_ratl_map = (x - r)/u**2 |

1574 | self.__posti_y_coord_ratl_map = (y - s*(x-r) - t)/u**3 |

1575 | |

1576 | self.__perform_inheritance_housekeeping() |

1577 | |

1578 | return; |

1579 | |

1580 | |

1581 | def __setup_post_isomorphism(self, codomain, model): |

1582 | r""" |

1583 | Private function to set up the post isomorphism given the |

1584 | codomain. |

1585 | |

1586 | EXAMPLES: |

1587 | |

1588 | The following examples inherently exercise this function:: |

1589 | |

1590 | sage: E = EllipticCurve(j=GF(7)(1728)) |

1591 | sage: E2 = EllipticCurve(GF(7), [0,0,0,5,0]) |

1592 | sage: phi = EllipticCurveIsogeny(E, E((0,0)), E2); phi |

1593 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 5*x over Finite Field of size 7 |

1594 | sage: E3 = EllipticCurve(GF(7), [0,0,0,6,0]) |

1595 | sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(E3, None) |

1596 | sage: phi |

1597 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 |

1598 | |

1599 | sage: R.<x> = QQ[] |

1600 | sage: E = EllipticCurve(j=1728) |

1601 | sage: f = x^3 - x |

1602 | sage: phi = EllipticCurveIsogeny(E, f, model='minimal'); phi |

1603 | Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 - x over Rational Field to Elliptic Curve defined by y^2 = x^3 - x over Rational Field |

1604 | |

1605 | sage: phi = EllipticCurveIsogeny(E, f, model=None) |

1606 | sage: phi._EllipticCurveIsogeny__setup_post_isomorphism(None, 'minimal') |

1607 | sage: phi |

1608 | Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 - x over Rational Field to Elliptic Curve defined by y^2 = x^3 - x over Rational Field |

1609 | |

1610 | """ |

1611 | |

1612 | # TODO: add checks to make sure that |

1613 | # codomain and model parameters are consistent with the |

1614 | # algorithm used. |

1615 | |

1616 | post_isom = None |

1617 | newE2 = None |

1618 | |

1619 | oldE2 = self.__E2 |

1620 | |

1621 | if (model is not None): |

1622 | |

1623 | if (codomain is not None): |

1624 | raise ValueError, "Cannot specify a codomain and model flag simultaneously." |

1625 | |

1626 | if ('minimal' == model): |

1627 | |

1628 | if (not is_RationalField(oldE2.base_field())): |

1629 | raise ValueError, "specifying minimal for model flag only valid with curves over the rational numbers." |

1630 | |

1631 | newE2 = oldE2.minimal_model() |

1632 | post_isom = oldE2.isomorphism_to(newE2) |

1633 | |

1634 | else: |

1635 | raise ValueError, "Unknown value of model flag." |

1636 | |

1637 | elif (codomain is not None): |

1638 | if (not is_EllipticCurve(codomain)): |

1639 | raise ValueError, "Codomain parameter must be an elliptic curve." |

1640 | |

1641 | if (not oldE2.is_isomorphic(codomain)): |

1642 | raise ValueError, "Codomain parameter must be isomorphic to computed codomain isogeny" |

1643 | |

1644 | newE2 = codomain |

1645 | post_isom = oldE2.isomorphism_to(newE2) |

1646 | |

1647 | if (post_isom is not None): |

1648 | self.__set_post_isomorphism(newE2, post_isom) |

1649 | |

1650 | return |

1651 | |

1652 | |

1653 | ########################### |

1654 | # Velu's Formula Functions |

1655 | ########################### |

1656 | |

1657 | # |

1658 | # Setup function for Velu's formula |

1659 | # |

1660 | |

1661 | def __init_from_kernel_list(self, kernel_gens): |

1662 | r""" |

1663 | Private function that initializes the isogeny from a list of |

1664 | points which generate the kernel (For Velu's formulas.) |

1665 | |

1666 | EXAMPLES: |

1667 | |

1668 | The following example inherently exercises this function:: |

1669 | |

1670 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1671 | sage: phi = EllipticCurveIsogeny(E, E((0,0))); phi |

1672 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 7 |

1673 | sage: phi._EllipticCurveIsogeny__init_from_kernel_list([E(0), E((0,0))]) |

1674 | |

1675 | """ |

1676 | if self.__check : |

1677 | for P in kernel_gens: |

1678 | if not P.has_finite_order(): |

1679 | raise ValueError, "The points in the kernel must be of finite order." |

1680 | # work around the current implementation of torsion points. When they are done better this could be |

1681 | # reduced but it won't speed things up too much. |

1682 | kernel_list = Set([self.__E1(0)]) |

1683 | for P in kernel_gens: |

1684 | points_to_add = [] |

1685 | for j in range(P.order()): |

1686 | for Q in kernel_list: |

1687 | points_to_add.append(j*P+Q) |

1688 | kernel_list += Set(points_to_add) |

1689 | |

1690 | self.__kernel_list = kernel_list.list() |

1691 | self.__kernel_2tor = {} |

1692 | self.__kernel_non2tor = {} |

1693 | |

1694 | self.__degree = len(kernel_list) |

1695 | |

1696 | self.__sort_kernel_list() |

1697 | |

1698 | return |

1699 | |

1700 | |

1701 | # |

1702 | # Precompute the values in Velu's Formula. |

1703 | # |

1704 | def __sort_kernel_list(self): |

1705 | r""" |

1706 | Private function that sorts the list of points in the kernel |

1707 | (For Velu's formulas). Sorts out the 2 torsion points, and |

1708 | puts them in a dictionary. |

1709 | |

1710 | EXAMPLES: |

1711 | |

1712 | The following example inherently exercises this function:: |

1713 | |

1714 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1715 | sage: P = E((4,2)) |

1716 | sage: phi = EllipticCurveIsogeny(E, P); phi |

1717 | Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 7 |

1718 | sage: phi._EllipticCurveIsogeny__kernel_2tor = {} |

1719 | sage: phi._EllipticCurveIsogeny__kernel_non2tor = {} |

1720 | sage: phi._EllipticCurveIsogeny__sort_kernel_list() |

1721 | |

1722 | """ |

1723 | |

1724 | a1,a2,a3,a4,a6 = self.__E1.ainvs() |

1725 | |

1726 | v = 0 |

1727 | w = 0 |

1728 | |

1729 | for Q in self.__kernel_list: |

1730 | |

1731 | if Q.is_zero(): |

1732 | continue |

1733 | |

1734 | (xQ,yQ) = Q.xy() |

1735 | |

1736 | gxQ = 3*xQ**2 + 2*a2*xQ + a4 - a1*yQ |

1737 | gyQ = -2*yQ - a1*xQ - a3 |

1738 | |

1739 | uQ = gyQ**2 |

1740 | |

1741 | # sort torsion points: |

1742 | if (2*yQ == -a1*xQ - a3): # Q is 2-torsion |

1743 | vQ = gxQ |

1744 | self.__kernel_2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ) |

1745 | v = v + vQ |

1746 | w = w + (uQ + xQ*vQ) |

1747 | elif xQ not in self.__kernel_non2tor: # Q is not a 2-torsion |

1748 | vQ = 2*gxQ - a1*gyQ |

1749 | self.__kernel_non2tor[xQ] = (xQ,yQ,gxQ,gyQ,vQ,uQ) |

1750 | v = v + vQ |

1751 | w = w + (uQ + xQ*vQ) |

1752 | |

1753 | self.__v = v |

1754 | self.__w = w |

1755 | |

1756 | return |

1757 | |

1758 | |

1759 | # |

1760 | # Velu's formula computing the codomain curve |

1761 | # |

1762 | def __compute_E2_via_velu(self): |

1763 | r""" |

1764 | Private function that computes the codomain via Velu's |

1765 | formulas. |

1766 | |

1767 | EXAMPLES: |

1768 | |

1769 | The following example inherently exercises this function:: |

1770 | |

1771 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1772 | sage: P = E((4,2)) |

1773 | sage: phi = EllipticCurveIsogeny(E, P); |

1774 | sage: phi.codomain() |

1775 | Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 7 |

1776 | sage: phi._EllipticCurveIsogeny__compute_E2_via_velu() |

1777 | Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 7 |

1778 | |

1779 | """ |

1780 | v = self.__v |

1781 | w = self.__w |

1782 | |

1783 | return compute_codomain_formula(self.__E1, v,w) |

1784 | |

1785 | |

1786 | def __velu_sum_helper(self, Qvalues, a1, a3, x, y): |

1787 | r""" |

1788 | Private function for Velu's formulas, helper function to help |

1789 | perform the summation. |

1790 | |

1791 | EXAMPLES: |

1792 | |

1793 | The following example inherently exercises this function:: |

1794 | |

1795 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1796 | sage: P = E((4,2)) |

1797 | sage: phi = EllipticCurveIsogeny(E, P); |

1798 | sage: Q = E((0,0)); phi(Q) |

1799 | (0 : 0 : 1) |

1800 | sage: phi.rational_maps() |

1801 | ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2), |

1802 | (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1)) |

1803 | |

1804 | sage: E = EllipticCurve(GF(7), [0,0,0,1,0]) |

1805 | sage: phi = EllipticCurveIsogeny(E, E((0,0)) ) |

1806 | sage: Qvals = phi._EllipticCurveIsogeny__kernel_2tor[0] |

1807 | sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, 5, 5) |

1808 | (3, 3) |

1809 | sage: R.<x,y> = GF(7)[] |

1810 | sage: phi._EllipticCurveIsogeny__velu_sum_helper(Qvals, 0, 0, x, y) |

1811 | (1/x, y/x^2) |

1812 | |

1813 | """ |

1814 | xQ = Qvalues[0] |

1815 | yQ = Qvalues[1] |

1816 | gxQ = Qvalues[2] |

1817 | gyQ = Qvalues[3] |

1818 | vQ = Qvalues[4] |

1819 | uQ = Qvalues[5] |

1820 | |

1821 | t1 = x - xQ |

1822 | inv_t1 = t1**-1 |

1823 | inv_t1_2 = inv_t1**2 |

1824 | inv_t1_3 = inv_t1_2*inv_t1 |

1825 | |

1826 | tX = vQ*inv_t1 + uQ*(inv_t1_2) |

1827 | |

1828 | tY0 = uQ*(2*y + a1*x + a3) |

1829 | tY1 = vQ*(a1*t1 + y - yQ) |

1830 | tY2 = a1*uQ - gxQ*gyQ |

1831 | |

1832 | tY = ( tY0*inv_t1_3 + (tY1 + tY2)*inv_t1_2 ) |

1833 | |

1834 | return (tX, tY) |

1835 | |

1836 | |

1837 | def __compute_via_velu_numeric(self, xP, yP): |

1838 | r""" |

1839 | Private function that sorts the list of points in the kernel |

1840 | (for Velu's formulas). Sorts out the 2 torsion points, and |

1841 | puts them in a diction |

1842 | |

1843 | EXAMPLES: |

1844 | |

1845 | The following example inherently exercises this function:: |

1846 | |

1847 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1848 | sage: P = E((4,2)) |

1849 | sage: phi = EllipticCurveIsogeny(E, P); |

1850 | sage: Q = E((0,0)); phi(Q) |

1851 | (0 : 0 : 1) |

1852 | sage: Q = E((-1,0)); phi(Q) |

1853 | (0 : 0 : 1) |

1854 | sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(0, 0) |

1855 | (0, 0) |

1856 | sage: phi._EllipticCurveIsogeny__compute_via_velu_numeric(-1, 0) |

1857 | (0, 0) |

1858 | |

1859 | """ |

1860 | # first check if the point is in the kernel |

1861 | if xP in self.__kernel_2tor or xP in self.__kernel_non2tor: |

1862 | return self.__intermediate_codomain(0) |

1863 | |

1864 | outP = self.__compute_via_velu(xP,yP) |

1865 | |

1866 | return outP |

1867 | |

1868 | |

1869 | def __compute_via_velu(self, xP, yP): |

1870 | r""" |

1871 | Private function for Velu's formulas, to perform the |

1872 | summation. |

1873 | |

1874 | EXAMPLES: |

1875 | |

1876 | The following example inherently exercises this function:: |

1877 | |

1878 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1879 | sage: P = E((4,2)) |

1880 | sage: phi = EllipticCurveIsogeny(E, P); |

1881 | sage: Q = E((0,0)); phi(Q) |

1882 | (0 : 0 : 1) |

1883 | sage: phi.rational_maps() |

1884 | ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2), |

1885 | (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1)) |

1886 | sage: phi._EllipticCurveIsogeny__compute_via_velu(0, 0) |

1887 | (0, 0) |

1888 | sage: R.<x,y> = GF(7)[] |

1889 | sage: phi._EllipticCurveIsogeny__compute_via_velu(x, y) |

1890 | ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2), |

1891 | (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1)) |

1892 | |

1893 | """ |

1894 | |

1895 | ker_2tor = self.__kernel_2tor |

1896 | ker_non2tor = self.__kernel_non2tor |

1897 | |

1898 | X = 0 |

1899 | Y = 0 |

1900 | |

1901 | a1 = self.__E1.a1() |

1902 | a3 = self.__E1.a3() |

1903 | |

1904 | # next iterate over the 2torsion points of the kernel |

1905 | for Qvalues in ker_2tor.itervalues(): |

1906 | (tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP) |

1907 | X = X + tX |

1908 | Y = Y + tY |

1909 | |

1910 | for Qvalues in ker_non2tor.itervalues(): |

1911 | (tX, tY) = self.__velu_sum_helper(Qvalues, a1, a3, xP, yP) |

1912 | X = X + tX |

1913 | Y = Y + tY |

1914 | |

1915 | X = xP + X |

1916 | Y = yP - Y |

1917 | |

1918 | return (X,Y) |

1919 | |

1920 | |

1921 | def __initialize_rational_maps_via_velu(self): |

1922 | r""" |

1923 | Private function for Velu's formulas, helper function to initialize the rational maps. |

1924 | |

1925 | EXAMPLES: |

1926 | |

1927 | The following example inherently exercises this function:: |

1928 | |

1929 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1930 | sage: P = E((4,2)) |

1931 | sage: phi = EllipticCurveIsogeny(E, P); |

1932 | sage: phi.rational_maps() |

1933 | ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2), |

1934 | (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1)) |

1935 | sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_velu() |

1936 | ((x^4 - 2*x^3 + x^2 - 3*x)/(x^3 - 2*x^2 + 3*x - 2), |

1937 | (x^5*y - 2*x^3*y - x^2*y - 2*x*y + 2*y)/(x^5 + 3*x^3 + 3*x^2 + x - 1)) |

1938 | |

1939 | """ |

1940 | |

1941 | x = self.__x_var |

1942 | y = self.__y_var |

1943 | |

1944 | return self.__compute_via_velu(x,y) |

1945 | |

1946 | |

1947 | def __init_kernel_polynomial_velu(self): |

1948 | r""" |

1949 | Private function for Velu's formulas, helper function to |

1950 | initialize the rational maps. |

1951 | |

1952 | EXAMPLES: |

1953 | |

1954 | The following example inherently exercises this function:: |

1955 | |

1956 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

1957 | sage: P = E((4,2)) |

1958 | sage: phi = EllipticCurveIsogeny(E, P); |

1959 | sage: phi.kernel_polynomial() |

1960 | x^2 + 2*x + 4 |

1961 | sage: phi._EllipticCurveIsogeny__init_kernel_polynomial_velu() |

1962 | [4, 2, 1] |

1963 | |

1964 | """ |

1965 | |

1966 | poly_ring = self.__poly_ring |

1967 | x = self.__x_var |

1968 | |

1969 | invX = 0 |

1970 | |

1971 | if (self.__pre_isomorphism is not None): |

1972 | pre_isom = self.__pre_isomorphism |

1973 | u = pre_isom.u |

1974 | r = pre_isom.r |

1975 | invX = (u**2)*x + r |

1976 | else: |

1977 | invX = x |

1978 | |

1979 | psi = poly_ring(1) |

1980 | |

1981 | for Qvalues in self.__kernel_2tor.itervalues(): |

1982 | xQ = invX(x=Qvalues[0]) |

1983 | psi = psi*(x - xQ) |

1984 | |

1985 | for Qvalues in self.__kernel_non2tor.itervalues(): |

1986 | xQ = invX(x=Qvalues[0]) |

1987 | psi = psi*(x - xQ) |

1988 | |

1989 | ker_poly_list = psi.univariate_polynomial().list() |

1990 | |

1991 | self.__kernel_polynomial_list = ker_poly_list |

1992 | self.__kernel_polynomial = psi |

1993 | |

1994 | return ker_poly_list |

1995 | |

1996 | |

1997 | |

1998 | ################################### |

1999 | # Kohel's Variant of Velu's Formula |

2000 | ################################### |

2001 | |

2002 | def __init_from_kernel_polynomial(self, kernel_polynomial, degree=None): |

2003 | r""" |

2004 | Private function that initializes the isogeny from a kernel |

2005 | polynomial. |

2006 | |

2007 | EXAMPLES: |

2008 | |

2009 | These examples inherently exercise this private function:: |

2010 | |

2011 | sage: R.<x> = GF(7)[] |

2012 | sage: E = EllipticCurve(GF(7), [0,0,0,-1,0]) |

2013 | sage: phi = EllipticCurveIsogeny(E, x);phi |

2014 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 7 |

2015 | |

2016 | sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x) |

2017 | |

2018 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2019 | sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi |

2020 | Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7 |

2021 | |

2022 | sage: phi._EllipticCurveIsogeny__init_from_kernel_polynomial(x+6, degree=3) |

2023 | |

2024 | """ |

2025 | |

2026 | poly_ring = self.__poly_ring |

2027 | x = self.__x_var |

2028 | |

2029 | E = self.__E1 |

2030 | |

2031 | if(is_Polynomial(kernel_polynomial)): |

2032 | kernel_polynomial = kernel_polynomial.list() |

2033 | |

2034 | n = len(kernel_polynomial)-1 |

2035 | |

2036 | if kernel_polynomial[-1] != 1: |

2037 | raise ValueError, "The kernel polynomial must be monic." |

2038 | |

2039 | self.__kernel_polynomial_list = kernel_polynomial |

2040 | |

2041 | psi = 0 |

2042 | for j in xrange(len(kernel_polynomial)): |

2043 | psi = psi*x + kernel_polynomial[n-j] |

2044 | |

2045 | |

2046 | # |

2047 | # Determine if kernel polynomial is entirely a two torsion |

2048 | # |

2049 | psi_G = two_torsion_part(E, poly_ring, psi, degree); |

2050 | |

2051 | # force this polynomial to be monic: |

2052 | psi_G = psi_G/psi_G.univariate_polynomial().leading_coefficient() |

2053 | |

2054 | if (0 != psi_G.degree()): # even degree case |

2055 | |

2056 | psi_quo = poly_ring(psi/psi_G) |

2057 | |

2058 | if (0 != psi_quo.degree()): |

2059 | raise NotImplementedError, "For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion." |

2060 | |

2061 | (phi, omega, v, w, n, d) = self.__init_even_kernel_polynomial(E, psi_G) |

2062 | |

2063 | else: # odd degree case |

2064 | |

2065 | (phi, omega, v, w, n, d) = self.__init_odd_kernel_polynomial(E, psi) |

2066 | |

2067 | |

2068 | # |

2069 | # Set up the necessary instance variables |

2070 | # |

2071 | |

2072 | self.__kernel_polynomial = psi |

2073 | self.__inner_kernel_polynomial = psi |

2074 | |

2075 | self.__n = n |

2076 | self.__degree = d |

2077 | |

2078 | self.__psi = psi |

2079 | self.__phi = phi |

2080 | self.__omega = omega |

2081 | |

2082 | self.__v = v |

2083 | self.__w = w |

2084 | |

2085 | return |

2086 | |

2087 | |

2088 | def __init_even_kernel_polynomial(self, E, psi_G): |

2089 | r""" |

2090 | Private function that initializes the isogeny from a kernel |

2091 | polynomial, for Kohel's algorithm in the even degree case. |

2092 | |

2093 | EXAMPLES: |

2094 | |

2095 | These examples inherently exercise this private function:: |

2096 | |

2097 | sage: R.<x> = GF(7)[] |

2098 | sage: E = EllipticCurve(GF(7), [-1,0]) |

2099 | sage: phi = EllipticCurveIsogeny(E, x);phi |

2100 | Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + 6*x over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 7 |

2101 | |

2102 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import two_torsion_part |

2103 | sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var) |

2104 | sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig) |

2105 | (x^3 - x, x^3*y + x*y, 6, 0, 1, 2) |

2106 | |

2107 | sage: F = GF(2^4, 'alpha'); R.<x> = F[] |

2108 | sage: E = EllipticCurve(F, [1,1,0,1,0]) |

2109 | sage: phi = EllipticCurveIsogeny(E, x); phi |

2110 | Isogeny of degree 2 from Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + x over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + 1 over Finite Field in alpha of size 2^4 |

2111 | |

2112 | sage: psig = two_torsion_part(E,R,x,None)(phi._EllipticCurveIsogeny__x_var) |

2113 | sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig) |

2114 | (x^3 + x, x^3*y + x^2 + x*y, 1, 0, 1, 2) |

2115 | |

2116 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2117 | sage: R.<x> = GF(7)[] |

2118 | sage: f = x^3 + 6*x^2 + 1 |

2119 | sage: phi = EllipticCurveIsogeny(E, f); phi |

2120 | Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 2*x + 5 over Finite Field of size 7 |

2121 | sage: psig = two_torsion_part(E,R,f,None) |

2122 | sage: psig = two_torsion_part(E,R,f,None)(phi._EllipticCurveIsogeny__x_var) |

2123 | sage: phi._EllipticCurveIsogeny__init_even_kernel_polynomial(E,psig) |

2124 | (x^7 - 2*x^6 + 2*x^5 - x^4 + 3*x^3 - 2*x^2 - x + 3, |

2125 | x^9*y - 3*x^8*y + 2*x^7*y - 3*x^3*y + 2*x^2*y + x*y - y, |

2126 | 1, |

2127 | 6, |

2128 | 3, |

2129 | 4) |

2130 | |

2131 | |

2132 | """ |

2133 | |

2134 | |

2135 | #check if the polynomial really divides the two_torsion_polynomial |

2136 | if self.__check and E.division_polynomial(2, x=self.__x_var) % psi_G != 0 : |

2137 | raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve." |

2138 | |

2139 | n = psi_G.degree() |

2140 | d = n+1 |

2141 | |

2142 | base_field = self.__base_field |

2143 | char = base_field.characteristic() |

2144 | |

2145 | x = self.__x_var |

2146 | y = self.__y_var |

2147 | |

2148 | a1,a2,a3,a4,a6 = E.ainvs() |

2149 | |

2150 | b2 = E.b2() |

2151 | b4 = E.b4() |

2152 | |

2153 | if (1 == n): |

2154 | x0 = -psi_G.constant_coefficient() |

2155 | |

2156 | # determine y0 |

2157 | if (2 == char): |

2158 | y0 = (x0**3 + a2*x0**2 + a4*x0 + a6).sqrt() |

2159 | else: |

2160 | y0 = -(a1*x0 + a3)/2 |

2161 | |

2162 | (v,w) = compute_vw_kohel_even_deg1(x0,y0,a1,a2,a4) |

2163 | |

2164 | phi = (x*psi_G + v)*psi_G |

2165 | omega = (y*psi_G**2 - v*(a1*psi_G + (y - y0)))*psi_G |

2166 | |

2167 | elif (3 == n): |

2168 | s = psi_G.univariate_polynomial().list() |

2169 | s1 = -s[n-1] |

2170 | s2 = s[n-2] |

2171 | s3 = -s[n-3] |

2172 | |

2173 | psi_G_pr = psi_G.derivative(x) |

2174 | psi_G_prpr = psi_G_pr.derivative(x) |

2175 | |

2176 | phi = (psi_G_pr**2) + (-2*psi_G_prpr + (4*x - s1))*psi_G |

2177 | |

2178 | phi_pr = phi.derivative(x) |

2179 | |

2180 | psi_2 = 2*y + a1*x + a3 |

2181 | |

2182 | omega = (psi_2*(phi_pr*psi_G - phi*psi_G_pr) - (a1*phi + a3*psi_G)*psi_G)/2 |

2183 | |

2184 | phi = phi*psi_G |

2185 | omega = omega*psi_G |

2186 | |

2187 | (v,w) = compute_vw_kohel_even_deg3(b2,b4,s1,s2,s3) |

2188 | |

2189 | else: |

2190 | raise ValueError, "input polynomial must be of degree 1 or 3, not %d" % n |

2191 | |

2192 | return (phi, omega, v, w, n, d) |

2193 | |

2194 | |

2195 | def __init_odd_kernel_polynomial(self, E, psi): |

2196 | r""" |

2197 | Private function that initializes the isogeny from a kernel |

2198 | polynomial. |

2199 | |

2200 | EXAMPLES: |

2201 | |

2202 | These examples inherently exercise this private function:: |

2203 | |

2204 | sage: R.<x> = GF(7)[] |

2205 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2206 | sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi |

2207 | Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7 |

2208 | |

2209 | sage: R.<x,y> = GF(7)[] |

2210 | sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, x+6) |

2211 | (x^3 - 2*x^2 + 3*x + 2, x^3*y - 3*x^2*y + x*y, 2, 6, 1, 3) |

2212 | |

2213 | sage: F = GF(2^4, 'alpha'); R.<x> = F[] |

2214 | sage: alpha = F.gen() |

2215 | sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1]) |

2216 | sage: f = x + alpha^2 + 1 |

2217 | sage: phi = EllipticCurveIsogeny(E, f); phi |

2218 | Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + (alpha^2+1)*x + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + alpha*x + alpha^3 over Finite Field in alpha of size 2^4 |

2219 | |

2220 | sage: R.<x,y> = F[] |

2221 | sage: f = x + alpha^2 + 1 |

2222 | sage: phi._EllipticCurveIsogeny__init_odd_kernel_polynomial(E, f) |

2223 | (x^3 + (alpha^2 + 1)*x + (alpha^3 + alpha^2 + alpha), |

2224 | x^3*y + (alpha^2 + 1)*x^2*y + (alpha^2 + alpha + 1)*x^2 + (alpha^2 + 1)*x*y + (alpha^2 + alpha)*x + (alpha)*y + (alpha), |

2225 | alpha^2 + alpha + 1, |

2226 | alpha^3 + alpha^2 + alpha, |

2227 | 1, |

2228 | 3) |

2229 | |

2230 | sage: E = EllipticCurve(j=-262537412640768000) |

2231 | sage: f = (E.isogenies_prime_degree()[0]).kernel_polynomial() |

2232 | sage: f.degree() |

2233 | 81 |

2234 | sage: E.isogeny(kernel=f) # long time (25s on sage.math, 2012) |

2235 | Isogeny of degree 163 from Elliptic Curve defined by y^2 + y = x^3 - 2174420*x + 1234136692 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 57772164980*x - 5344733777551611 over Rational Field |

2236 | |

2237 | """ |

2238 | n = psi.degree() |

2239 | d = 2*n + 1 |

2240 | |

2241 | # check if the polynomial really divides the torsion polynomial : |

2242 | if self.__check: |

2243 | alpha = psi.parent().quotient(psi).gen() |

2244 | if not E.division_polynomial(d, x=alpha).is_zero(): |

2245 | raise ValueError, "The polynomial does not define a finite subgroup of the elliptic curve." |

2246 | |

2247 | x = self.__x_var |

2248 | |

2249 | b2 = E.b2() |

2250 | b4 = E.b4() |

2251 | b6 = E.b6() |

2252 | |

2253 | psi_coeffs = psi.univariate_polynomial().list() |

2254 | |

2255 | s1 = 0; s2 = 0; s3 = 0 |

2256 | |

2257 | if (1 <= n): |

2258 | s1 = -psi_coeffs[n-1] |

2259 | |

2260 | if (2 <= n): |

2261 | s2 = psi_coeffs[n-2] |

2262 | |

2263 | if (3 <= n): |

2264 | s3 = -psi_coeffs[n-3] |

2265 | |

2266 | # initializing these allows us to calculate E2. |

2267 | (v,w) = compute_vw_kohel_odd(b2,b4,b6,s1,s2,s3,n); |

2268 | |

2269 | # initialize the polynomial temporary variables |

2270 | |

2271 | psi_pr = psi.derivative(x) |

2272 | psi_prpr = psi_pr.derivative(x) |

2273 | |

2274 | phi = (4*x**3 + b2*x**2 + 2*b4*x + b6)*(psi_pr**2 - psi_prpr*psi) - \ |

2275 | (6*x**2 + b2*x + b4)*psi_pr*psi + (d*x - 2*s1)*psi**2 |

2276 | |

2277 | phi_pr = phi.derivative(x) |

2278 | |

2279 | omega = 0 |

2280 | if (2 != self.__base_field.characteristic()): |

2281 | omega = self.__compute_omega_fast(E, psi, psi_pr, phi, phi_pr) |

2282 | else: |

2283 | omega = self.__compute_omega_general(E, psi, psi_pr, phi, phi_pr) |

2284 | |

2285 | return (phi, omega, v, w, n, d) |

2286 | |

2287 | |

2288 | # |

2289 | # This is the fast omega computation that works when characteristic is not 2 |

2290 | # |

2291 | def __compute_omega_fast(self, E, psi, psi_pr, phi, phi_pr): |

2292 | r""" |

2293 | Private function that initializes the omega polynomial (from |

2294 | Kohel's formulas) in the case that the characteristic of the |

2295 | underlying field is not 2. |

2296 | |

2297 | EXAMPLES: |

2298 | |

2299 | These examples inherently exercise this private function:: |

2300 | |

2301 | sage: R.<x> = GF(7)[] |

2302 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2303 | sage: phi = EllipticCurveIsogeny(E, x+6, degree=3); phi |

2304 | Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 1 over Finite Field of size 7 to Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7 |

2305 | |

2306 | sage: R.<x,y> = GF(7)[] |

2307 | sage: psi = phi._EllipticCurveIsogeny__psi |

2308 | sage: psi_pr = psi.derivative(x) |

2309 | sage: fi = phi._EllipticCurveIsogeny__phi |

2310 | sage: fi_pr = fi.derivative(x) |

2311 | sage: phi._EllipticCurveIsogeny__compute_omega_fast(E, psi, psi_pr, fi, fi_pr) |

2312 | x^3*y - 3*x^2*y + x*y |

2313 | |

2314 | """ |

2315 | |

2316 | a1 = E.a1() |

2317 | a3 = E.a3() |

2318 | |

2319 | x = self.__x_var; # 'x' |

2320 | y = self.__y_var; # 'y' |

2321 | |

2322 | psi_2 = 2*y + a1*x + a3 |

2323 | |

2324 | # note, the formula below is correct |

2325 | # the formula in Kohel's thesis has some typos |

2326 | # notably the first plus sign should be a minus |

2327 | # as it is here below. |

2328 | |

2329 | omega = phi_pr*psi*psi_2/2 - phi*psi_pr*psi_2 - \ |

2330 | (a1*phi + a3*psi**2)*psi/2 |

2331 | |

2332 | return omega |

2333 | |

2334 | |

2335 | def __compute_omega_general(self, E, psi, psi_pr, phi, phi_pr): |

2336 | r""" |

2337 | Private function that initializes the omega polynomial (from |

2338 | Kohel's formulas) in the case of general characteristic of the |

2339 | underlying field. |

2340 | |

2341 | EXAMPLES: |

2342 | |

2343 | These examples inherently exercise this private function:: |

2344 | |

2345 | sage: F = GF(2^4, 'alpha'); R.<x> = F[] |

2346 | sage: alpha = F.gen() |

2347 | sage: E = EllipticCurve(F, [1,1,F.gen(),F.gen()^2+1,1]) |

2348 | sage: f = x + alpha^2 + 1 |

2349 | sage: phi = EllipticCurveIsogeny(E, f); phi |

2350 | Isogeny of degree 3 from Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + (alpha^2+1)*x + 1 over Finite Field in alpha of size 2^4 to Elliptic Curve defined by y^2 + x*y + alpha*y = x^3 + x^2 + alpha*x + alpha^3 over Finite Field in alpha of size 2^4 |

2351 | |

2352 | sage: R.<x,y> = F[] |

2353 | sage: psi = phi._EllipticCurveIsogeny__psi |

2354 | sage: psi_pr = psi.derivative(x) |

2355 | sage: fi = phi._EllipticCurveIsogeny__phi |

2356 | sage: fi_pr = fi.derivative(x) |

2357 | sage: phi._EllipticCurveIsogeny__compute_omega_general(E, psi, psi_pr, fi, fi_pr) |

2358 | x^3*y + (alpha^2 + 1)*x^2*y + (alpha^2 + alpha + 1)*x^2 + (alpha^2 + 1)*x*y + (alpha^2 + alpha)*x + (alpha)*y + (alpha) |

2359 | |

2360 | A bug fixed in ticket #7907:: |

2361 | |

2362 | sage: F = GF(128,'a') |

2363 | sage: a = F.gen() |

2364 | sage: E = EllipticCurve([1,0,0,0,(a**6+a**4+a**2+a)]) |

2365 | sage: x = polygen(F) |

2366 | sage: ker = (x^6 + (a^6 + a^5 + a^4 + a^3 + a^2 + a)*x^5 + (a^6 + a^5 + a^2 + 1)*x^4 + (a^6 + a^5 + a^4 + a^3 + a^2 + 1)*x^3 + (a^6 + a^3 + a)*x^2 + (a^4 + a^3 + 1)*x + a^5 + a^4 + a) |

2367 | sage: E.isogeny(ker) |

2368 | Isogeny of degree 13 from Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^4+a^2+a) over Finite Field in a of size 2^7 to Elliptic Curve defined by y^2 + x*y = x^3 + (a^6+a^5+a^4+a^3+a^2+a)*x + (a^5+a^3) over Finite Field in a of size 2^7 |

2369 | |

2370 | |

2371 | """ |

2372 | |

2373 | a1,a2,a3,a4,a6 = E.ainvs() |

2374 | |

2375 | b2 = E.b2() |

2376 | b4 = E.b4() |

2377 | |

2378 | n = psi.degree() |

2379 | d = 2*n+1 |

2380 | |

2381 | x = self.__x_var |

2382 | y = self.__y_var |

2383 | |

2384 | psi_2 = 2*y + a1*x + a3 |

2385 | |

2386 | psi_coeffs = psi.univariate_polynomial().list() |

2387 | |

2388 | if (0 < n): |

2389 | s1 = -psi_coeffs[n-1] |

2390 | else: |

2391 | s1 = 0 |

2392 | |

2393 | psi_prpr = 0 |

2394 | cur_x_pow = 1 |

2395 | |

2396 | # |

2397 | # Note: we now get the "derivatives" of psi |

2398 | # these are not actually the derivatives |

2399 | # furthermore, the formulas in Kohel's |

2400 | # thesis are wrong, the correct formulas |

2401 | # are coded below |

2402 | # |

2403 | from sage.rings.arith import binomial |

2404 | |

2405 | for j in xrange(0,n-1): |

2406 | psi_prpr = psi_prpr + \ |

2407 | binomial(j+2,2)*psi_coeffs[(j+2)]*cur_x_pow |

2408 | cur_x_pow = x*cur_x_pow |

2409 | |

2410 | psi_prprpr = 0 |

2411 | cur_x_pow = 1 |

2412 | |

2413 | for j in xrange(0,n-2): |

2414 | psi_prprpr = psi_prprpr + \ |

2415 | (3*binomial(j+3,3))*psi_coeffs[(j+3)]*cur_x_pow |

2416 | cur_x_pow = x*cur_x_pow |

2417 | |

2418 | |

2419 | omega = phi_pr*psi*y - phi*psi_pr*psi_2 + \ |

2420 | ((a1*x + a3)*(psi_2**2)*(psi_prpr*psi_pr-psi_prprpr*psi) + \ |

2421 | (a1*psi_2**2 - 3*(a1*x + a3)*(6*x**2 + b2*x + b4))*psi_prpr*psi + \ |

2422 | (a1*x**3 + 3*a3*x**2 + (2*a2*a3 - a1*a4)*x + (a3*a4 - 2*a1*a6))*psi_pr**2 + \ |

2423 | (-(3*a1*x**2 + 6*a3*x + (-a1*a4 + 2*a2*a3)) + \ |

2424 | (a1*x + a3)*(d*x - 2*s1) )*psi_pr*psi + (a1*s1 + a3*n)*psi**2)*psi |

2425 | |

2426 | return omega |

2427 | |

2428 | |

2429 | def __compute_via_kohel_numeric(self, xP, yP): |

2430 | r""" |

2431 | Private function that computes a numeric result of this |

2432 | isogeny (via Kohel's formulas.) |

2433 | |

2434 | EXAMPLES: |

2435 | |

2436 | These examples inherently exercise this private function:: |

2437 | |

2438 | sage: R.<x> = GF(7)[] |

2439 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2440 | sage: phi = EllipticCurveIsogeny(E, x+6, degree=3) |

2441 | sage: P = E((0,1)); phi(P) |

2442 | (2 : 0 : 1) |

2443 | sage: P = E((1,1)); phi(P) |

2444 | (0 : 1 : 0) |

2445 | sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(0, 1) |

2446 | (2, 0) |

2447 | sage: phi._EllipticCurveIsogeny__compute_via_kohel_numeric(1, 1) |

2448 | (0 : 1 : 0) |

2449 | |

2450 | """ |

2451 | |

2452 | # first check if this is a kernel point |

2453 | # to avoid a divide by 0 error later |

2454 | if(0 == self.__inner_kernel_polynomial(x=xP)): |

2455 | return self.__intermediate_codomain(0) |

2456 | |

2457 | (xP_out, yP_out) = self.__compute_via_kohel(xP,yP) |

2458 | |

2459 | # for some dang reason in some cases |

2460 | # when the base_field is a number field |

2461 | # xP_out and yP_out do not get evaluated to field elements |

2462 | # but rather constant polynomials. |

2463 | # So in this case, we do some explicit casting to make sure |

2464 | # everything comes out right |

2465 | |

2466 | if is_NumberField(self.__base_field) and (1 < self.__base_field.degree()) : |

2467 | xP_out = self.__poly_ring(xP_out).constant_coefficient() |

2468 | yP_out = self.__poly_ring(yP_out).constant_coefficient() |

2469 | |

2470 | return (xP_out,yP_out) |

2471 | |

2472 | |

2473 | def __compute_via_kohel(self, xP, yP): |

2474 | r""" |

2475 | Private function that applies Kohel's formulas. |

2476 | |

2477 | EXAMPLES: |

2478 | |

2479 | These examples inherently exercise this private function:: |

2480 | |

2481 | sage: R.<x> = GF(7)[] |

2482 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2483 | sage: phi = EllipticCurveIsogeny(E, x+6, degree=3) |

2484 | sage: P = E((0,1)); phi(P) |

2485 | (2 : 0 : 1) |

2486 | sage: phi.rational_maps() |

2487 | ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1), |

2488 | (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1)) |

2489 | sage: phi._EllipticCurveIsogeny__compute_via_kohel(0,1) |

2490 | (2, 0) |

2491 | sage: R.<x,y> = GF(7)[] |

2492 | sage: phi._EllipticCurveIsogeny__compute_via_kohel(x,y) |

2493 | ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1), |

2494 | (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1)) |

2495 | |

2496 | """ |

2497 | |

2498 | x = self.__x_var |

2499 | y = self.__y_var |

2500 | |

2501 | psi_out = self.__psi(xP,yP) |

2502 | phi_out = self.__phi(xP,yP) |

2503 | omega_out =self.__omega(xP, yP) |

2504 | |

2505 | psi_inv_out = 1/psi_out |

2506 | |

2507 | psi_inv_sq_out = psi_inv_out**2 |

2508 | |

2509 | X_out = phi_out*(psi_inv_sq_out) |

2510 | Y_out = omega_out*(psi_inv_sq_out*psi_inv_out) |

2511 | |

2512 | return (X_out, Y_out) |

2513 | |

2514 | |

2515 | def __initialize_rational_maps_via_kohel(self): |

2516 | r""" |

2517 | Private function that computes and initializes the rational |

2518 | maps of this isogeny. |

2519 | |

2520 | EXAMPLES: |

2521 | |

2522 | These examples inherently exercise this private function:: |

2523 | |

2524 | sage: R.<x> = GF(7)[] |

2525 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2526 | sage: phi = EllipticCurveIsogeny(E, x+6, degree=3) |

2527 | sage: phi.rational_maps() |

2528 | ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1), |

2529 | (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1)) |

2530 | sage: phi._EllipticCurveIsogeny__initialize_rational_maps_via_kohel() |

2531 | ((x^3 - 2*x^2 + 3*x + 2)/(x^2 - 2*x + 1), |

2532 | (x^3*y - 3*x^2*y + x*y)/(x^3 - 3*x^2 + 3*x - 1)) |

2533 | |

2534 | |

2535 | """ |

2536 | x = self.__x_var |

2537 | y = self.__y_var |

2538 | |

2539 | (X,Y) = self.__compute_via_kohel(x,y) |

2540 | |

2541 | return (X,Y) |

2542 | |

2543 | |

2544 | # |

2545 | # Kohel's formula computing the codomain curve |

2546 | # |

2547 | def __compute_E2_via_kohel(self): |

2548 | r""" |

2549 | Private function that computes and initializes the codomain of |

2550 | the isogeny (via Kohel's.) |

2551 | |

2552 | EXAMPLES: |

2553 | |

2554 | These examples inherently exercise this private function:: |

2555 | |

2556 | sage: R.<x> = GF(7)[] |

2557 | sage: E = EllipticCurve(GF(7), [0,-1,0,0,1]) |

2558 | sage: phi = EllipticCurveIsogeny(E, x+6, degree=3) |

2559 | sage: phi.codomain() |

2560 | Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7 |

2561 | sage: phi._EllipticCurveIsogeny__compute_E2_via_kohel() |

2562 | Elliptic Curve defined by y^2 = x^3 + 6*x^2 + 4*x + 2 over Finite Field of size 7 |

2563 | |

2564 | """ |

2565 | |

2566 | v = self.__v |

2567 | w = self.__w |

2568 | |

2569 | return compute_codomain_formula(self.__E1, v,w) |

2570 | |

2571 | |

2572 | |

2573 | # |

2574 | # public isogeny methods |

2575 | # |

2576 | |

2577 | # def domain(self): |

2578 | r""" |

2579 | Returns the domain curve of this isogeny. |

2580 | |

2581 | EXAMPLES:: |

2582 | |

2583 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

2584 | sage: phi = EllipticCurveIsogeny(E, E(0,0)) |

2585 | sage: phi.domain() == E |

2586 | True |

2587 | |

2588 | sage: E = EllipticCurve(GF(31), [1,0,0,1,2]) |

2589 | sage: phi = EllipticCurveIsogeny(E, [17, 1]) |

2590 | sage: phi.domain() |

2591 | Elliptic Curve defined by y^2 + x*y = x^3 + x + 2 over Finite Field of size 31 |

2592 | |

2593 | """ |

2594 | # !!!! S. Besnier change here !!!! : replace __E1 by __E1(self.__E1.base_field()) in order |

2595 | # to make self.domain() an AbelianGroup |

2596 | # return self.__E1(self.__E1.base_field()) |

2597 | |

2598 | |

2599 | # def codomain(self): |

2600 | r""" |

2601 | Returns the codomain (range) curve of this isogeny. |

2602 | |

2603 | EXAMPLES:: |

2604 | |

2605 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

2606 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

2607 | sage: phi.codomain() |

2608 | Elliptic Curve defined by y^2 = x^3 - 4*x over Rational Field |

2609 | |

2610 | sage: E = EllipticCurve(GF(31), [1,0,0,1,2]) |

2611 | sage: phi = EllipticCurveIsogeny(E, [17, 1]) |

2612 | sage: phi.codomain() |

2613 | Elliptic Curve defined by y^2 + x*y = x^3 + 24*x + 6 over Finite Field of size 31 |

2614 | |

2615 | """ |

2616 | # !!!! S. Besnier change here !!!! : replace __E2 by __E1(self.__E2.base_field()) |

2617 | # return self.__E2(self.__E2.base_field()) |

2618 | |

2619 | |

2620 | def degree(self): |

2621 | r""" |

2622 | Returns the degree of this isogeny. |

2623 | |

2624 | EXAMPLES:: |

2625 | |

2626 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

2627 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

2628 | sage: phi.degree() |

2629 | 2 |

2630 | sage: phi = EllipticCurveIsogeny(E, [0,1,0,1]) |

2631 | sage: phi.degree() |

2632 | 4 |

2633 | |

2634 | sage: E = EllipticCurve(GF(31), [1,0,0,1,2]) |

2635 | sage: phi = EllipticCurveIsogeny(E, [17, 1]) |

2636 | sage: phi.degree() |

2637 | 3 |

2638 | |

2639 | """ |

2640 | return self.__degree |

2641 | |

2642 | |

2643 | def rational_maps(self): |

2644 | r""" |

2645 | This function returns this isogeny as a pair of rational maps. |

2646 | |

2647 | EXAMPLES:: |

2648 | |

2649 | sage: E = EllipticCurve(QQ, [0,2,0,1,-1]) |

2650 | sage: phi = EllipticCurveIsogeny(E, [1]) |

2651 | sage: phi.rational_maps() |

2652 | (x, y) |

2653 | |

2654 | sage: E = EllipticCurve(GF(17), [0,0,0,3,0]) |

2655 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

2656 | sage: phi.rational_maps() |

2657 | ((x^2 + 3)/x, (x^2*y - 3*y)/x^2) |

2658 | |

2659 | |

2660 | """ |

2661 | if (not self.__rational_maps_initialized): |

2662 | self.__initialize_rational_maps() |

2663 | return (self.__X_coord_rational_map, self.__Y_coord_rational_map) |

2664 | |

2665 | |

2666 | def is_separable(self): |

2667 | r""" |

2668 | This function returns a bool indicating whether or not this |

2669 | isogeny is separable. |

2670 | |

2671 | This function always returns ``True`` as currently this class |

2672 | only implements separable isogenies. |

2673 | |

2674 | EXAMPLES:: |

2675 | |

2676 | sage: E = EllipticCurve(GF(17), [0,0,0,3,0]) |

2677 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

2678 | sage: phi.is_separable() |

2679 | True |

2680 | |

2681 | sage: E = EllipticCurve('11a1') |

2682 | sage: phi = EllipticCurveIsogeny(E, E.torsion_points()) |

2683 | sage: phi.is_separable() |

2684 | True |

2685 | |

2686 | |

2687 | """ |

2688 | return self.__separable |

2689 | |

2690 | |

2691 | def kernel_polynomial(self): |

2692 | r""" |

2693 | Returns the kernel polynomial of this isogeny. |

2694 | |

2695 | EXAMPLES:: |

2696 | |

2697 | sage: E = EllipticCurve(QQ, [0,0,0,2,0]) |

2698 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

2699 | sage: phi.kernel_polynomial() |

2700 | x |

2701 | |

2702 | sage: E = EllipticCurve('11a1') |

2703 | sage: phi = EllipticCurveIsogeny(E, E.torsion_points()) |

2704 | sage: phi.kernel_polynomial() |

2705 | x^2 - 21*x + 80 |

2706 | |

2707 | sage: E = EllipticCurve(GF(17), [1,-1,1,-1,1]) |

2708 | sage: phi = EllipticCurveIsogeny(E, [1]) |

2709 | sage: phi.kernel_polynomial() |

2710 | 1 |

2711 | |

2712 | sage: E = EllipticCurve(GF(31), [0,0,0,3,0]) |

2713 | sage: phi = EllipticCurveIsogeny(E, [0,3,0,1]) |

2714 | sage: phi.kernel_polynomial() |

2715 | x^3 + 3*x |

2716 | |

2717 | |

2718 | """ |

2719 | if (self.__kernel_polynomial is None): |

2720 | self.__init_kernel_polynomial() |

2721 | |

2722 | return self.__kernel_polynomial.univariate_polynomial() |

2723 | |

2724 | |

2725 | def set_pre_isomorphism(self, preWI): |

2726 | r""" |

2727 | Modifies this isogeny object to pre compose with the given |

2728 | Weierstrass isomorphism. |

2729 | |

2730 | EXAMPLES:: |

2731 | |

2732 | sage: E = EllipticCurve(GF(31), [1,1,0,1,-1]) |

2733 | sage: R.<x> = GF(31)[] |

2734 | sage: f = x^3 + 9*x^2 + x + 30 |

2735 | sage: phi = EllipticCurveIsogeny(E, f) |

2736 | sage: Epr = E.short_weierstrass_model() |

2737 | sage: isom = Epr.isomorphism_to(E) |

2738 | sage: phi.set_pre_isomorphism(isom) |

2739 | sage: phi.rational_maps() |

2740 | ((-6*x^4 - 3*x^3 + 12*x^2 + 10*x - 1)/(x^3 + x - 12), |

2741 | (3*x^7 + x^6*y - 14*x^6 - 3*x^5 + 5*x^4*y + 7*x^4 + 8*x^3*y - 8*x^3 - 5*x^2*y + 5*x^2 - 14*x*y + 14*x - 6*y - 6)/(x^6 + 2*x^4 + 7*x^3 + x^2 + 7*x - 11)) |

2742 | sage: phi(Epr((0,22))) |

2743 | (13 : 21 : 1) |

2744 | sage: phi(Epr((3,7))) |

2745 | (14 : 17 : 1) |

2746 | |

2747 | sage: E = EllipticCurve(GF(29), [0,0,0,1,0]) |

2748 | sage: R.<x> = GF(29)[] |

2749 | sage: f = x^2 + 5 |

2750 | sage: phi = EllipticCurveIsogeny(E, f) |

2751 | sage: phi |

2752 | Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 20*x over Finite Field of size 29 |

2753 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

2754 | sage: inv_isom = WeierstrassIsomorphism(E, (1,-2,5,10)) |

2755 | sage: Epr = inv_isom.codomain().codomain() |

2756 | sage: isom = Epr.isomorphism_to(E) |

2757 | sage: phi.set_pre_isomorphism(isom); phi |

2758 | Isogeny of degree 5 from Elliptic Curve defined by y^2 + 10*x*y + 20*y = x^3 + 27*x^2 + 6 over Finite Field of size 29 to Elliptic Curve defined by y^2 = x^3 + 20*x over Finite Field of size 29 |

2759 | sage: phi(Epr((12,1))) |

2760 | (26 : 0 : 1) |

2761 | sage: phi(Epr((2,9))) |

2762 | (0 : 0 : 1) |

2763 | sage: phi(Epr((21,12))) |

2764 | (3 : 0 : 1) |

2765 | sage: phi.rational_maps()[0] |

2766 | (x^5 - 10*x^4 - 6*x^3 - 7*x^2 - x + 3)/(x^4 - 8*x^3 + 5*x^2 - 14*x - 6) |

2767 | |

2768 | sage: E = EllipticCurve('11a1') |

2769 | sage: R.<x> = QQ[] |

2770 | sage: f = x^2 - 21*x + 80 |

2771 | sage: phi = EllipticCurveIsogeny(E, f); phi |

2772 | |

2773 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

2774 | sage: Epr = E.short_weierstrass_model() |

2775 | sage: isom = Epr.isomorphism_to(E) |

2776 | sage: phi.set_pre_isomorphism(isom) |

2777 | sage: phi |

2778 | Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 - 13392*x - 1080432 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field |

2779 | sage: phi(Epr((168,1188))) |

2780 | (0 : 1 : 0) |

2781 | |

2782 | """ |

2783 | |

2784 | WIdom = preWI.domain().codomain() |

2785 | WIcod = preWI.codomain().codomain() |

2786 | |

2787 | if (type(preWI) != WeierstrassIsomorphism): |

2788 | raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism." |

2789 | |

2790 | if (self.__E1 != WIcod): |

2791 | raise ValueError, "Invalid parameter: isomorphism must have codomain curve equal to this isogenies' domain." |

2792 | |

2793 | if (self.__pre_isomorphism is None): |

2794 | isom = preWI |

2795 | domain = WIdom |

2796 | else: |

2797 | isom = self.__pre_isomorphism*preWI |

2798 | domain = WIdom |

2799 | |

2800 | self.__clear_cached_values() |

2801 | |

2802 | self.__set_pre_isomorphism(domain, isom) |

2803 | |

2804 | return |

2805 | |

2806 | |

2807 | def set_post_isomorphism(self, postWI): |

2808 | r""" |

2809 | Modifies this isogeny object to post compose with the given |

2810 | Weierstrass isomorphism. |

2811 | |

2812 | EXAMPLES:: |

2813 | |

2814 | sage: E = EllipticCurve(j=GF(31)(0)) |

2815 | sage: R.<x> = GF(31)[] |

2816 | sage: phi = EllipticCurveIsogeny(E, x+18) |

2817 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

2818 | sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(), (6,8,10,12))) |

2819 | sage: phi |

2820 | Isogeny of degree 3 from Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 31 to Elliptic Curve defined by y^2 + 24*x*y + 7*y = x^3 + 22*x^2 + 16*x + 20 over Finite Field of size 31 |

2821 | |

2822 | sage: E = EllipticCurve(j=GF(47)(0)) |

2823 | sage: f = E.torsion_polynomial(3)/3 |

2824 | sage: phi = EllipticCurveIsogeny(E, f) |

2825 | sage: E2 = phi.codomain() |

2826 | sage: post_isom = E2.isomorphism_to(E) |

2827 | sage: phi.set_post_isomorphism(post_isom) |

2828 | sage: phi.rational_maps() == E.multiplication_by_m(3) |

2829 | False |

2830 | sage: phi.switch_sign() |

2831 | sage: phi.rational_maps() == E.multiplication_by_m(3) |

2832 | True |

2833 | |

2834 | Example over a number field:: |

2835 | |

2836 | sage: R.<x> = QQ[] |

2837 | sage: K.<a> = NumberField(x^2 + 2) |

2838 | sage: E = EllipticCurve(j=K(1728)) |

2839 | sage: ker_list = E.torsion_points() |

2840 | sage: phi = EllipticCurveIsogeny(E, ker_list) |

2841 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

2842 | sage: post_isom = WeierstrassIsomorphism(phi.codomain(), (a,2,3,5)) |

2843 | sage: phi |

2844 | Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x over Number Field in a with defining polynomial x^2 + 2 to Elliptic Curve defined by y^2 = x^3 + (-44)*x + 112 over Number Field in a with defining polynomial x^2 + 2 |

2845 | |

2846 | """ |

2847 | |

2848 | WIdom = postWI.domain().codomain() |

2849 | WIcod = postWI.codomain().codomain() |

2850 | |

2851 | if (type(postWI) != WeierstrassIsomorphism): |

2852 | raise ValueError, "Invalid parameter: isomorphism must be of type Weierstrass isomorphism." |

2853 | |

2854 | if (self.__E2 != WIdom): |

2855 | raise ValueError, "Invalid parameter: isomorphism must have domain curve equal to this isogenies' codomain." |

2856 | |

2857 | if (self.__post_isomorphism is None): |

2858 | isom = postWI |

2859 | codomain = WIcod |

2860 | else: |

2861 | isom = postWI*self.__post_isomorphism |

2862 | codomain = WIcod |

2863 | |

2864 | self.__clear_cached_values() |

2865 | |

2866 | self.__set_post_isomorphism(codomain, isom) |

2867 | |

2868 | return |

2869 | |

2870 | |

2871 | def get_pre_isomorphism(self): |

2872 | r""" |

2873 | Returns the pre-isomorphism of this isogeny. If there has |

2874 | been no pre-isomorphism set, this returns ``None``. |

2875 | |

2876 | EXAMPLES:: |

2877 | |

2878 | sage: E = EllipticCurve(GF(31), [1,1,0,1,-1]) |

2879 | sage: R.<x> = GF(31)[] |

2880 | sage: f = x^3 + 9*x^2 + x + 30 |

2881 | sage: phi = EllipticCurveIsogeny(E, f) |

2882 | sage: phi.get_post_isomorphism() |

2883 | sage: Epr = E.short_weierstrass_model() |

2884 | sage: isom = Epr.isomorphism_to(E) |

2885 | sage: phi.set_pre_isomorphism(isom) |

2886 | sage: isom == phi.get_pre_isomorphism() |

2887 | True |

2888 | |

2889 | sage: E = EllipticCurve(GF(83), [1,0,1,1,0]) |

2890 | sage: R.<x> = GF(83)[]; f = x+24 |

2891 | sage: phi = EllipticCurveIsogeny(E, f) |

2892 | sage: E2 = phi.codomain() |

2893 | sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2) |

2894 | sage: phi2.get_pre_isomorphism() |

2895 | Generic morphism: |

2896 | From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 83 |

2897 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83 |

2898 | Via: (u,r,s,t) = (1, 76, 41, 3) |

2899 | |

2900 | |

2901 | |

2902 | """ |

2903 | return self.__pre_isomorphism |

2904 | |

2905 | |

2906 | def get_post_isomorphism(self): |

2907 | r""" |

2908 | Returns the post-isomorphism of this isogeny. If there has |

2909 | been no post-isomorphism set, this returns ``None``. |

2910 | |

2911 | EXAMPLES:: |

2912 | |

2913 | sage: E = EllipticCurve(j=GF(31)(0)) |

2914 | sage: R.<x> = GF(31)[] |

2915 | sage: phi = EllipticCurveIsogeny(E, x+18) |

2916 | sage: phi.get_post_isomorphism() |

2917 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

2918 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (6,8,10,12)) |

2919 | sage: phi.set_post_isomorphism(isom) |

2920 | sage: isom == phi.get_post_isomorphism() |

2921 | True |

2922 | |

2923 | sage: E = EllipticCurve(GF(83), [1,0,1,1,0]) |

2924 | sage: R.<x> = GF(83)[]; f = x+24 |

2925 | sage: phi = EllipticCurveIsogeny(E, f) |

2926 | sage: E2 = phi.codomain() |

2927 | sage: phi2 = EllipticCurveIsogeny(E, None, E2, 2) |

2928 | sage: phi2.get_post_isomorphism() |

2929 | Generic morphism: |

2930 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83 |

2931 | To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 83 |

2932 | Via: (u,r,s,t) = (1, 7, 42, 80) |

2933 | |

2934 | """ |

2935 | return self.__post_isomorphism |

2936 | |

2937 | |

2938 | def switch_sign(self): |

2939 | r""" |

2940 | This function composes the isogeny with `[-1]` (flipping the |

2941 | coefficient between +/-1 on the `y` coordinate rational map). |

2942 | |

2943 | EXAMPLES:: |

2944 | |

2945 | sage: E = EllipticCurve(GF(23), [0,0,0,1,0]) |

2946 | sage: f = E.torsion_polynomial(3)/3 |

2947 | sage: phi = EllipticCurveIsogeny(E, f, E) |

2948 | sage: phi.rational_maps() == E.multiplication_by_m(3) |

2949 | False |

2950 | sage: phi.switch_sign() |

2951 | sage: phi.rational_maps() == E.multiplication_by_m(3) |

2952 | True |

2953 | |

2954 | sage: E = EllipticCurve(GF(17), [-2, 3, -5, 7, -11]) |

2955 | sage: R.<x> = GF(17)[] |

2956 | sage: f = x+6 |

2957 | sage: phi = EllipticCurveIsogeny(E, f) |

2958 | sage: phi |

2959 | Isogeny of degree 2 from Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 7*x + 6 over Finite Field of size 17 to Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 4*x + 8 over Finite Field of size 17 |

2960 | sage: phi.rational_maps() |

2961 | ((x^2 + 6*x + 4)/(x + 6), (x^2*y - 5*x*y + 8*x - 2*y)/(x^2 - 5*x + 2)) |

2962 | sage: phi.switch_sign() |

2963 | sage: phi |

2964 | Isogeny of degree 2 from Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 7*x + 6 over Finite Field of size 17 to Elliptic Curve defined by y^2 + 15*x*y + 12*y = x^3 + 3*x^2 + 4*x + 8 over Finite Field of size 17 |

2965 | sage: phi.rational_maps() |

2966 | ((x^2 + 6*x + 4)/(x + 6), |

2967 | (2*x^3 - x^2*y - 5*x^2 + 5*x*y - 4*x + 2*y + 7)/(x^2 - 5*x + 2)) |

2968 | |

2969 | sage: E = EllipticCurve('11a1') |

2970 | sage: R.<x> = QQ[] |

2971 | sage: f = x^2 - 21*x + 80 |

2972 | sage: phi = EllipticCurveIsogeny(E, f) |

2973 | sage: (xmap1, ymap1) = phi.rational_maps() |

2974 | sage: phi.switch_sign() |

2975 | sage: (xmap2, ymap2) = phi.rational_maps() |

2976 | sage: xmap1 == xmap2 |

2977 | True |

2978 | sage: ymap1 == -ymap2 - E.a1()*xmap2 - E.a3() |

2979 | True |

2980 | |

2981 | sage: K.<a> = NumberField(x^2 + 1) |

2982 | sage: E = EllipticCurve(K, [0,0,0,1,0]) |

2983 | sage: R.<x> = K[] |

2984 | sage: phi = EllipticCurveIsogeny(E, x-a) |

2985 | sage: phi.rational_maps() |

2986 | ((x^2 + (-a)*x - 2)/(x + (-a)), (x^2*y + (-2*a)*x*y + y)/(x^2 + (-2*a)*x - 1)) |

2987 | sage: phi.switch_sign() |

2988 | sage: phi.rational_maps() |

2989 | ((x^2 + (-a)*x - 2)/(x + (-a)), (-x^2*y + (2*a)*x*y - y)/(x^2 + (-2*a)*x - 1)) |

2990 | |

2991 | """ |

2992 | self.set_post_isomorphism(WeierstrassIsomorphism(self.__E2, (-1,0,-self.__E2.a1(),-self.__E2.a3()))) |

2993 | |

2994 | def is_normalized(self, via_formal=True, check_by_pullback=True): |

2995 | r""" |

2996 | Returns ``True`` if this isogeny is normalized. An isogeny |

2997 | `\varphi\colon E\to E_2` between two given Weierstrass |

2998 | equations is said to be normalized if the constant `c` is `1` |

2999 | in `\varphi*(\omega_2) = c\cdot\omega`, where `\omega` and |

3000 | `omega_2` are the invariant differentials on `E` and `E_2` |

3001 | corresponding to the given equation. |

3002 | |

3003 | INPUT: |

3004 | |

3005 | - ``via_formal`` - (default: ``True``) If ``True`` it simply checks if |

3006 | the leading term of the formal series is 1. Otherwise |

3007 | it uses a deprecated algorithm involving the second |

3008 | optional argument. |

3009 | |

3010 | - ``check_by_pullback`` - (default:``True``) Deprecated. |

3011 | |

3012 | EXAMPLES:: |

3013 | |

3014 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

3015 | sage: E = EllipticCurve(GF(7), [0,0,0,1,0]) |

3016 | sage: R.<x> = GF(7)[] |

3017 | sage: phi = EllipticCurveIsogeny(E, x) |

3018 | sage: phi.is_normalized() |

3019 | True |

3020 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (3, 0, 0, 0)) |

3021 | sage: phi.set_post_isomorphism(isom) |

3022 | sage: phi.is_normalized() |

3023 | False |

3024 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (5, 0, 0, 0)) |

3025 | sage: phi.set_post_isomorphism(isom) |

3026 | sage: phi.is_normalized() |

3027 | True |

3028 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1)) |

3029 | sage: phi.set_post_isomorphism(isom) |

3030 | sage: phi.is_normalized() |

3031 | True |

3032 | |

3033 | sage: F = GF(2^5, 'alpha'); alpha = F.gen() |

3034 | sage: E = EllipticCurve(F, [1,0,1,1,1]) |

3035 | sage: R.<x> = F[] |

3036 | sage: phi = EllipticCurveIsogeny(E, x+1) |

3037 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (alpha, 0, 0, 0)) |

3038 | sage: phi.is_normalized() |

3039 | True |

3040 | sage: phi.set_post_isomorphism(isom) |

3041 | sage: phi.is_normalized() |

3042 | False |

3043 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/alpha, 0, 0, 0)) |

3044 | sage: phi.set_post_isomorphism(isom) |

3045 | sage: phi.is_normalized() |

3046 | True |

3047 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1)) |

3048 | sage: phi.set_post_isomorphism(isom) |

3049 | sage: phi.is_normalized() |

3050 | True |

3051 | |

3052 | sage: E = EllipticCurve('11a1') |

3053 | sage: R.<x> = QQ[] |

3054 | sage: f = x^3 - x^2 - 10*x - 79/4 |

3055 | sage: phi = EllipticCurveIsogeny(E, f) |

3056 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (2, 0, 0, 0)) |

3057 | sage: phi.is_normalized() |

3058 | True |

3059 | sage: phi.set_post_isomorphism(isom) |

3060 | sage: phi.is_normalized() |

3061 | False |

3062 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (1/2, 0, 0, 0)) |

3063 | sage: phi.set_post_isomorphism(isom) |

3064 | sage: phi.is_normalized() |

3065 | True |

3066 | sage: isom = WeierstrassIsomorphism(phi.codomain(), (1, 1, 1, 1)) |

3067 | sage: phi.set_post_isomorphism(isom) |

3068 | sage: phi.is_normalized() |

3069 | True |

3070 | |

3071 | """ |

3072 | # easy algorithm using the formal expansion. |

3073 | if via_formal: |

3074 | phi_formal = self.formal(prec=5) |

3075 | return phi_formal[1] == 1 |

3076 | |

3077 | # this is the old algorithm. it should be deprecated. |

3078 | check_prepost_isomorphism = False |

3079 | |

3080 | f_normalized = True |

3081 | |

3082 | if (check_by_pullback): |

3083 | |

3084 | (Xmap, Ymap) = self.rational_maps() |

3085 | |

3086 | E1 = self.__E1 |

3087 | E2 = self.__E2 |

3088 | |

3089 | a1 = E1.a1() |

3090 | a3 = E1.a3() |

3091 | |

3092 | a1pr = E2.a1() |

3093 | a3pr = E2.a3() |

3094 | |

3095 | x = self.__x_var |

3096 | y = self.__y_var |

3097 | |

3098 | Xmap_pr = Xmap.derivative(x) |

3099 | |

3100 | domain_inv_diff = 1/(2*y + a1*x + a3) |

3101 | codomain_inv_diff = Xmap_pr/(2*Ymap + a1pr*Xmap + a3pr) |

3102 | |

3103 | inv_diff_quo = domain_inv_diff/codomain_inv_diff |

3104 | |

3105 | if (1 == inv_diff_quo): |

3106 | f_normalized = True |

3107 | else: |

3108 | # For some reason, in certain cases, when the isogeny |

3109 | # is pre or post composed with a translation the |

3110 | # resulting rational functions are too complicated for |

3111 | # sage to simplify down to a constant in this case, we |

3112 | # do some cheating by checking if the post-composition |

3113 | # by isogeny has a non 1 scaling factor |

3114 | if ( inv_diff_quo.numerator().is_constant() and (inv_diff_quo.denominator().is_constant) ): |

3115 | f_normalized = False |

3116 | else: |

3117 | check_prepost_isomorphism = True |

3118 | else: |

3119 | check_prepost_isomorphism = True |

3120 | |

3121 | # If we skip checking by the pullback of the invariant |

3122 | # differential OR if that was inconclusive We explicitly check |

3123 | # if there is a post isomorphism and if it has a non 1 scaling |

3124 | # factor or if it is a just a translation. NOTE: This only |

3125 | # works because we are using algorithms for calculating the |

3126 | # isogenies that calculate a separable normalized isogeny, if |

3127 | # this changes, this check will no longer be correct. |

3128 | # |

3129 | if (check_prepost_isomorphism): |

3130 | post_isom = self.__post_isomorphism |

3131 | if (post_isom is not None): |

3132 | if (1 == self.__base_field(post_isom.u)): |

3133 | f_post_normalized = True |

3134 | else: |

3135 | f_post_normalized = False |

3136 | else: |

3137 | f_post_normalized = True |

3138 | |

3139 | pre_isom = self.__pre_isomorphism |

3140 | if (pre_isom is not None): |

3141 | if (1 == self.__base_field(pre_isom.u)): |

3142 | f_pre_normalized = True |

3143 | else: |

3144 | f_pre_normalized = False |

3145 | else: |

3146 | f_pre_normalized = True |

3147 | |

3148 | f_normalized = f_pre_normalized and f_post_normalized |

3149 | |

3150 | return f_normalized |

3151 | |

3152 | def dual(self): |

3153 | r""" |

3154 | Computes and returns the dual isogeny of this isogeny. If |

3155 | `\varphi\colon E \to E_2` is the given isogeny, then the dual |

3156 | is by definition the unique isogeny `\hat\varphi\colon E_2\to |

3157 | E` such that the compositions `\hat\varphi\circ\varphi` and |

3158 | `\varphi\circ\hat\varphi` are the multiplication `[n]` by the |

3159 | degree of `\varphi` on `E` and `E_2` respectively. |

3160 | |

3161 | EXAMPLES:: |

3162 | |

3163 | sage: E = EllipticCurve('11a1') |

3164 | sage: R.<x> = QQ[] |

3165 | sage: f = x^2 - 21*x + 80 |

3166 | sage: phi = EllipticCurveIsogeny(E, f) |

3167 | sage: phi_hat = phi.dual() |

3168 | sage: phi_hat.domain() == phi.codomain() |

3169 | True |

3170 | sage: phi_hat.codomain() == phi.domain() |

3171 | True |

3172 | sage: (X, Y) = phi.rational_maps() |

3173 | sage: (Xhat, Yhat) = phi_hat.rational_maps() |

3174 | sage: Xm = Xhat.subs(x=X, y=Y) |

3175 | sage: Ym = Yhat.subs(x=X, y=Y) |

3176 | sage: (Xm, Ym) == E.multiplication_by_m(5) |

3177 | True |

3178 | |

3179 | sage: E = EllipticCurve(GF(37), [0,0,0,1,8]) |

3180 | sage: R.<x> = GF(37)[] |

3181 | sage: f = x^3 + x^2 + 28*x + 33 |

3182 | sage: phi = EllipticCurveIsogeny(E, f) |

3183 | sage: phi_hat = phi.dual() |

3184 | sage: phi_hat.codomain() == phi.domain() |

3185 | True |

3186 | sage: phi_hat.domain() == phi.codomain() |

3187 | True |

3188 | sage: (X, Y) = phi.rational_maps() |

3189 | sage: (Xhat, Yhat) = phi_hat.rational_maps() |

3190 | sage: Xm = Xhat.subs(x=X, y=Y) |

3191 | sage: Ym = Yhat.subs(x=X, y=Y) |

3192 | sage: (Xm, Ym) == E.multiplication_by_m(7) |

3193 | True |

3194 | |

3195 | sage: E = EllipticCurve(GF(31), [0,0,0,1,8]) |

3196 | sage: R.<x> = GF(31)[] |

3197 | sage: f = x^2 + 17*x + 29 |

3198 | sage: phi = EllipticCurveIsogeny(E, f) |

3199 | sage: phi_hat = phi.dual() |

3200 | sage: phi_hat.codomain() == phi.domain() |

3201 | True |

3202 | sage: phi_hat.domain() == phi.codomain() |

3203 | True |

3204 | sage: (X, Y) = phi.rational_maps() |

3205 | sage: (Xhat, Yhat) = phi_hat.rational_maps() |

3206 | sage: Xm = Xhat.subs(x=X, y=Y) |

3207 | sage: Ym = Yhat.subs(x=X, y=Y) |

3208 | sage: (Xm, Ym) == E.multiplication_by_m(5) |

3209 | True |

3210 | |

3211 | Test (for trac ticket 7096):: |

3212 | |

3213 | sage: E = EllipticCurve('11a1') |

3214 | sage: phi = E.isogeny(E(5,5)) |

3215 | sage: phi.dual().dual() == phi |

3216 | True |

3217 | |

3218 | sage: k = GF(103) |

3219 | sage: E = EllipticCurve(k,[11,11]) |

3220 | sage: phi = E.isogeny(E(4,4)) |

3221 | sage: phi |

3222 | Isogeny of degree 5 from Elliptic Curve defined by y^2 = x^3 + 11*x + 11 over Finite Field of size 103 to Elliptic Curve defined by y^2 = x^3 + 25*x + 80 over Finite Field of size 103 |

3223 | sage: from sage.schemes.elliptic_curves.weierstrass_morphism import WeierstrassIsomorphism |

3224 | sage: phi.set_post_isomorphism(WeierstrassIsomorphism(phi.codomain(),(5,0,1,2))) |

3225 | sage: phi.dual().dual() == phi |

3226 | True |

3227 | |

3228 | sage: E = EllipticCurve(GF(103),[1,0,0,1,-1]) |

3229 | sage: phi = E.isogeny(E(60,85)) |

3230 | sage: phi.dual() |

3231 | Isogeny of degree 7 from Elliptic Curve defined by y^2 + x*y = x^3 + 84*x + 34 over Finite Field of size 103 to Elliptic Curve defined by y^2 + x*y = x^3 + x + 102 over Finite Field of size 103 |

3232 | |

3233 | """ |

3234 | |

3235 | if (self.__base_field.characteristic() in [2,3]): |

3236 | raise NotImplemented |

3237 | |

3238 | if (self.__dual is not None): |

3239 | return self.__dual |

3240 | |

3241 | # trac 7096 |

3242 | (E1, E2pr, pre_isom, post_isom) = compute_intermediate_curves(self.__E2, self.__E1) |

3243 | |

3244 | F = self.__base_field |

3245 | |

3246 | d = self.__degree |

3247 | |

3248 | # trac 7096 |

3249 | if F(d) == 0: |

3250 | raise NotImplementedError, "The dual isogeny is not separable, but only separable isogenies are implemented so far" |

3251 | |

3252 | # trac 7096 |

3253 | # this should take care of the case when the isogeny is not normalized. |

3254 | u = self.formal(prec=5)[1] |

3255 | isom = WeierstrassIsomorphism(E2pr, (u/F(d), 0, 0, 0)) |

3256 | |

3257 | E2 = isom.codomain().codomain() |

3258 | |

3259 | pre_isom = self.__E2.isomorphism_to(E1) |

3260 | post_isom = E2.isomorphism_to(self.__E1) |

3261 | |

3262 | phi_hat = EllipticCurveIsogeny(E1, None, E2, d) |

3263 | |

3264 | phi_hat.set_pre_isomorphism(pre_isom) |

3265 | phi_hat.set_post_isomorphism(post_isom) |

3266 | phi_hat.__perform_inheritance_housekeeping() |

3267 | |

3268 | assert phi_hat.codomain() == self.domain() |

3269 | |

3270 | # trac 7096 : this adjust a posteriori the automorphism |

3271 | # on the codomain of the dual isogeny. |

3272 | # we used _a_ Weierstrass isomorphism to get to the original |

3273 | # curve, but we may have to change it my an automorphism. |

3274 | # we impose that the composition has the degree |

3275 | # as a leading coefficient in the formal expansion. |

3276 | |

3277 | phi_sc = self.formal(prec=5)[1] |

3278 | phihat_sc = phi_hat.formal(prec=5)[1] |

3279 | |

3280 | sc = phi_sc * phihat_sc/F(d) |

3281 | print sc |

3282 | if sc != 1: |

3283 | auts = phi_hat.codomain().automorphsims() |

3284 | aut = [a for a in auts if a.u == sc] |

3285 | if len(aut) != 1: |

3286 | raise ValueError, "There is a bug in dual()." |

3287 | phi_hat.set_post_isomorphism(a[0]) |

3288 | |

3289 | self.__dual = phi_hat |

3290 | |

3291 | return phi_hat |

3292 | |

3293 | def formal(self,prec=20): |

3294 | r""" |

3295 | Computes the formal isogeny as a power series in the variable |

3296 | `t=-x/y` on the domain curve. |

3297 | |

3298 | INPUT: |

3299 | |

3300 | - ``prec`` - (default = 20), the precision with which the computations |

3301 | in the formal group are carried out. |

3302 | |

3303 | EXAMPLES:: |

3304 | |

3305 | sage: E = EllipticCurve(GF(13),[1,7]) |

3306 | sage: phi = E.isogeny(E(10,4)) |

3307 | sage: phi.formal() |

3308 | t + 12*t^13 + 2*t^17 + 8*t^19 + 2*t^21 + O(t^23) |

3309 | |

3310 | sage: E = EllipticCurve([0,1]) |

3311 | sage: phi = E.isogeny(E(2,3)) |

3312 | sage: phi.formal(prec=10) |

3313 | t + 54*t^5 + 255*t^7 + 2430*t^9 + 19278*t^11 + O(t^13) |

3314 | |

3315 | sage: E = EllipticCurve('11a2') |

3316 | sage: R.<x> = QQ[] |

3317 | sage: phi = E.isogeny(x^2 + 101*x + 12751/5) |

3318 | sage: phi.formal(prec=7) |

3319 | t - 2724/5*t^5 + 209046/5*t^7 - 4767/5*t^8 + 29200946/5*t^9 + O(t^10) |

3320 | |

3321 | |

3322 | """ |

3323 | Eh = self.__E1.formal() |

3324 | f, g = self.rational_maps() |

3325 | xh = Eh.x(prec=prec) |

3326 | yh = Eh.y(prec=prec) |

3327 | fh = f(xh,yh) |

3328 | gh = g(xh,yh) |

3329 | return -fh/gh |

3330 | |

3331 | # |

3332 | # Overload Morphism methods that we want to |

3333 | # |

3334 | # !!!! S. Besnier change here !!!! : comment the all function |

3335 | #def _composition_(self, right, homset): |

3336 | r""" |

3337 | Composition operator function inherited from morphism class. |

3338 | |

3339 | EXAMPLES:: |

3340 | |

3341 | sage: E = EllipticCurve(j=GF(7)(0)) |

3342 | sage: phi = EllipticCurveIsogeny(E, [E(0), E((0,1)), E((0,-1))]) |

3343 | sage: phi._composition_(phi, phi.parent()) |

3344 | Traceback (most recent call last): |

3345 | ... |

3346 | NotImplementedError |

3347 | |

3348 | The following should test that :meth:`_composition_` is called |

3349 | upon a product. However phi is currently improperly |

3350 | constructed (see :trac:`12880`), which triggers an assertion |

3351 | failure before the actual call :: |

3352 | |

3353 | sage: phi*phi |

3354 | Traceback (most recent call last): |

3355 | ... |

3356 | TypeError: Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7 is not in Category of hom sets in Category of Schemes |

3357 | |

3358 | Here would be the desired output:: |

3359 | |

3360 | sage: phi*phi # not tested |

3361 | Traceback (most recent call last): |

3362 | ... |

3363 | NotImplementedError |

3364 | """ |

3365 | #raise NotImplementedError |

3366 | |

3367 | |

3368 | def is_injective(self): |

3369 | r""" |

3370 | Method inherited from the morphism class. Returns ``True`` if |

3371 | and only if this isogeny has trivial kernel. |

3372 | |

3373 | EXAMPLES:: |

3374 | |

3375 | sage: E = EllipticCurve('11a1') |

3376 | sage: R.<x> = QQ[] |

3377 | sage: f = x^2 + x - 29/5 |

3378 | sage: phi = EllipticCurveIsogeny(E, f) |

3379 | sage: phi.is_injective() |

3380 | False |

3381 | sage: phi = EllipticCurveIsogeny(E, R(1)) |

3382 | sage: phi.is_injective() |

3383 | True |

3384 | |

3385 | sage: F = GF(7) |

3386 | sage: E = EllipticCurve(j=F(0)) |

3387 | sage: phi = EllipticCurveIsogeny(E, [ E((0,-1)), E((0,1))]) |

3388 | sage: phi.is_injective() |

3389 | False |

3390 | sage: phi = EllipticCurveIsogeny(E, E(0)) |

3391 | sage: phi.is_injective() |

3392 | True |

3393 | |

3394 | """ |

3395 | |

3396 | if (1 < self.__degree): return False |

3397 | return True |

3398 | |

3399 | |

3400 | def is_surjective(self): |

3401 | r""" |

3402 | For elliptic curve isogenies, always returns ``True`` (as a |

3403 | non-constant map of algebraic curves must be surjective). |

3404 | |

3405 | EXAMPLES:: |

3406 | |

3407 | sage: E = EllipticCurve('11a1') |

3408 | sage: R.<x> = QQ[] |

3409 | sage: f = x^2 + x - 29/5 |

3410 | sage: phi = EllipticCurveIsogeny(E, f) |

3411 | sage: phi.is_surjective() |

3412 | True |

3413 | |

3414 | sage: E = EllipticCurve(GF(7), [0,0,0,1,0]) |

3415 | sage: phi = EllipticCurveIsogeny(E, E((0,0))) |

3416 | sage: phi.is_surjective() |

3417 | True |

3418 | |

3419 | sage: F = GF(2^5, 'omega') |

3420 | sage: E = EllipticCurve(j=F(0)) |

3421 | sage: R.<x> = F[] |

3422 | sage: phi = EllipticCurveIsogeny(E, x) |

3423 | sage: phi.is_surjective() |

3424 | True |

3425 | |

3426 | """ |

3427 | return True |

3428 | |

3429 | def is_zero(self): |

3430 | r""" |

3431 | Member function inherited from morphism class. |

3432 | |

3433 | EXAMPLES:: |

3434 | |

3435 | sage: E = EllipticCurve(j=GF(7)(0)) |

3436 | sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))]) |

3437 | sage: phi.is_zero() |

3438 | Traceback (most recent call last): |

3439 | ... |

3440 | NotImplementedError |

3441 | """ |

3442 | raise NotImplementedError |

3443 | |

3444 | def post_compose(self, left): |

3445 | r""" |

3446 | Member function inherited from morphism class. |

3447 | |

3448 | EXAMPLES:: |

3449 | |

3450 | sage: E = EllipticCurve(j=GF(7)(0)) |

3451 | sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))]) |

3452 | sage: phi.post_compose(phi) |

3453 | Traceback (most recent call last): |

3454 | ... |

3455 | NotImplementedError |

3456 | |

3457 | """ |

3458 | raise NotImplementedError |

3459 | |

3460 | |

3461 | def pre_compose(self, right): |

3462 | r""" |

3463 | Member function inherited from morphism class. |

3464 | |

3465 | EXAMPLES:: |

3466 | |

3467 | sage: E = EllipticCurve(j=GF(7)(0)) |

3468 | sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))]) |

3469 | sage: phi.pre_compose(phi) |

3470 | Traceback (most recent call last): |

3471 | ... |

3472 | NotImplementedError |

3473 | |

3474 | """ |

3475 | raise NotImplementedError |

3476 | |

3477 | |

3478 | def n(self): |

3479 | r""" |

3480 | Numerical Approximation inherited from Map (through morphism), |

3481 | nonsensical for isogenies. |

3482 | |

3483 | EXAMPLES:: |

3484 | |

3485 | sage: E = EllipticCurve(j=GF(7)(0)) |

3486 | sage: phi = EllipticCurveIsogeny(E, [ E((0,1)), E((0,-1))]) |

3487 | sage: phi.n() |

3488 | Traceback (most recent call last): |

3489 | ... |

3490 | NotImplementedError: Numerical approximations do not make sense for Elliptic Curve Isogenies |

3491 | |

3492 | """ |

3493 | raise NotImplementedError, "Numerical approximations do not make sense for Elliptic Curve Isogenies" |

3494 | |

3495 | # no longer needed (trac 7096) |

3496 | # def starks_find_r_and_t(T, Z): |

3497 | |

3498 | def compute_isogeny_starks(E1, E2, ell): |

3499 | r""" |

3500 | Computes the degree ``ell`` isogeny between ``E1`` and ``E2`` via |

3501 | Stark's algorithm. There must be a degree ``ell``, separable, |

3502 | normalized cyclic isogeny from ``E1`` to ``E2``. |

3503 | |

3504 | INPUT: |

3505 | |

3506 | - ``E1`` - an elliptic curve in short Weierstrass form. |

3507 | - ``E2`` - an elliptic curve in short Weierstrass form. |

3508 | - ``ell`` - the degree of the isogeny from E1 to E2. |

3509 | |

3510 | OUTPUT: |

3511 | |

3512 | polynomial -- over the field of definition of ``E1``, ``E2``, that is the |

3513 | kernel polynomial of the isogeny from ``E1`` to ``E2``. |

3514 | |

3515 | ALGORITHM: |

3516 | |

3517 | This function uses Starks Algorithm as presented in section 6.2 of |

3518 | [BMSS]. |

3519 | |

3520 | .. note:: |

3521 | |

3522 | As published there, the algorithm is incorrect, and a correct |

3523 | version (with slightly different notation) can be found in |

3524 | [M09]. The algorithm originates in [S72] |

3525 | |

3526 | REFERENCES: |

3527 | |

3528 | - [BMSS] Boston, Morain, Salvy, Schost, "Fast Algorithms for Isogenies." |

3529 | - [M09] Moody, "The Diffie-Hellman Problem and Generalization of Verheul's Theorem" |

3530 | - [S72] Stark, "Class-numbers of complex quadratic fields." |

3531 | |

3532 | EXAMPLES:: |

3533 | |

3534 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks, compute_sequence_of_maps |

3535 | |

3536 | sage: E = EllipticCurve(GF(97), [1,0,1,1,0]) |

3537 | sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 21 |

3538 | sage: phi = EllipticCurveIsogeny(E, f) |

3539 | sage: E2 = phi.codomain() |

3540 | sage: (isom1, isom2, E1pr, E2pr, ker_poly) = compute_sequence_of_maps(E, E2, 11) |

3541 | sage: compute_isogeny_starks(E1pr, E2pr, 11) |

3542 | x^10 + 37*x^9 + 53*x^8 + 66*x^7 + 66*x^6 + 17*x^5 + 57*x^4 + 6*x^3 + 89*x^2 + 53*x + 8 |

3543 | |

3544 | sage: E = EllipticCurve(GF(37), [0,0,0,1,8]) |

3545 | sage: R.<x> = GF(37)[] |

3546 | sage: f = (x + 14) * (x + 30) |

3547 | sage: phi = EllipticCurveIsogeny(E, f) |

3548 | sage: E2 = phi.codomain() |

3549 | sage: compute_isogeny_starks(E, E2, 5) |

3550 | x^4 + 14*x^3 + x^2 + 34*x + 21 |

3551 | sage: f**2 |

3552 | x^4 + 14*x^3 + x^2 + 34*x + 21 |

3553 | |

3554 | sage: E = EllipticCurve(QQ, [0,0,0,1,0]) |

3555 | sage: R.<x> = QQ[] |

3556 | sage: f = x |

3557 | sage: phi = EllipticCurveIsogeny(E, f) |

3558 | sage: E2 = phi.codomain() |

3559 | sage: compute_isogeny_starks(E, E2, 2) |

3560 | x |

3561 | |

3562 | """ |

3563 | |

3564 | K = E1.base_field() |

3565 | R = PolynomialRing(K, 'x') |

3566 | x = R.gen() |

3567 | |

3568 | wp1 = E1.weierstrass_p(prec=4*ell+4) #BMSS claim 2*ell is enough, but it is not M09 |

3569 | wp2 = E2.weierstrass_p(prec=4*ell+4) |

3570 | |

3571 | # viewed them as power series in Z = z^2 |

3572 | S = LaurentSeriesRing(K, 'Z') |

3573 | Z = S.gen() |

3574 | pe1 = 1/Z |

3575 | pe2 = 1/Z |

3576 | for i in xrange(2*ell+1): |

3577 | pe1 += wp1[2*i] * Z**i |

3578 | pe2 += wp2[2*i] * Z**i |

3579 | pe1 = pe1.add_bigoh(2*ell+2) |

3580 | pe2 = pe2.add_bigoh(2*ell+2) |

3581 | |

3582 | #print 'wps = ',pe1 |

3583 | #print 'wps2 = ',pe2 |

3584 | |

3585 | n = 1 |

3586 | q = [R(1), R(0)] |

3587 | #p = [R(0), R(1)] |

3588 | T = pe2 |

3589 | |

3590 | while ( q[n].degree() < (ell-1) ): |

3591 | #print 'n=', n |

3592 | |

3593 | n += 1 |

3594 | a_n = 0 |

3595 | r = -T.valuation() |

3596 | while (0 <= r): |

3597 | t_r = T[-r] |

3598 | #print ' r=',r |

3599 | #print ' t_r=',t_r |

3600 | #print ' T=',T |

3601 | a_n = a_n + t_r * x**r |

3602 | T = T - t_r*pe1**r |

3603 | r = -T.valuation() |

3604 | |

3605 | |

3606 | q_n = a_n*q[n-1] + q[n-2] |

3607 | q.append(q_n) |

3608 | #p_n = a_n*p[n-1] + q[n-2] |

3609 | #p.append(p_n) |

3610 | |

3611 | if (n == ell+1 or T == 0): |

3612 | if (T == 0 or T.valuation()<2): |

3613 | raise ValueError("The two curves are not linked by a cyclic normalized isogeny of degree %s" % ell) |

3614 | #print 'breaks here' |

3615 | break |

3616 | |

3617 | T = 1/T |

3618 | #print ' a_n=', a_n |

3619 | #print ' q_n=', q_n |

3620 | #print ' p_n=', p_n |

3621 | #print ' T = ', T |

3622 | |

3623 | qn = q[n] |

3624 | #pn= p[n] |

3625 | #print 'final T = ', T |

3626 | #print ' f =', pn/qn |

3627 | |

3628 | qn = (1/qn.leading_coefficient())*qn |

3629 | #pn = (1/qn.leading_coefficient())*pn |

3630 | |

3631 | return qn |

3632 | |

3633 | def split_kernel_polynomial(E1, ker_poly, ell): |

3634 | r""" |

3635 | Internal helper function for ``compute_isogeny_kernel_polynomial``. |

3636 | |

3637 | Given a full kernel polynomial (where two torsion `x`-coordinates |

3638 | are roots of multiplicity 1, and all other roots have multiplicity |

3639 | 2.) of degree `\ell-1`, returns the maximum separable divisor. |

3640 | (i.e. the kernel polynomial with roots of multiplicity at most 1). |

3641 | |

3642 | EXAMPLES: |

3643 | |

3644 | The following example implicitly exercises this function:: |

3645 | |

3646 | sage: E = EllipticCurve(GF(37), [0,0,0,1,8]) |

3647 | sage: R.<x> = GF(37)[] |

3648 | sage: f = (x + 10) * (x + 12) * (x + 16) |

3649 | sage: phi = EllipticCurveIsogeny(E, f) |

3650 | sage: E2 = phi.codomain() |

3651 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_starks |

3652 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import split_kernel_polynomial |

3653 | sage: ker_poly = compute_isogeny_starks(E, E2, 7); ker_poly |

3654 | x^6 + 2*x^5 + 20*x^4 + 11*x^3 + 36*x^2 + 35*x + 16 |

3655 | sage: split_kernel_polynomial(E, ker_poly, 7) |

3656 | x^3 + x^2 + 28*x + 33 |

3657 | |

3658 | """ |

3659 | |

3660 | poly_ring = ker_poly.parent() |

3661 | |

3662 | z = poly_ring.gen(0) |

3663 | |

3664 | ker_poly_2tor = two_torsion_part(E1, poly_ring, ker_poly, ell) |

3665 | ker_poly_quo = poly_ring(ker_poly/ker_poly_2tor) |

3666 | ker_poly_quo_sqrt = ker_poly_quo.gcd(ker_poly_quo.derivative(z)) |

3667 | ker_poly = ker_poly_2tor*ker_poly_quo_sqrt |

3668 | ker_poly = (1/ker_poly.leading_coefficient())*ker_poly |

3669 | |

3670 | return ker_poly |

3671 | |

3672 | |

3673 | def compute_isogeny_kernel_polynomial(E1, E2, ell, algorithm="starks"): |

3674 | r""" |

3675 | Computes the kernel polynomial of the degree ``ell`` isogeny |

3676 | between ``E1`` and ``E2``. There must be a degree ``ell``, |

3677 | cyclic, separable, normalized isogeny from ``E1`` to ``E2``. |

3678 | |

3679 | INPUT: |

3680 | |

3681 | - ``E1`` - an elliptic curve in short Weierstrass form. |

3682 | |

3683 | - ``E2`` - an elliptic curve in short Weierstrass form. |

3684 | |

3685 | - ``ell`` - the degree of the isogeny from ``E1`` to ``E2``. |

3686 | |

3687 | - ``algorithm`` - currently only ``starks`` (default) is implemented. |

3688 | |

3689 | OUTPUT: |

3690 | |

3691 | polynomial -- over the field of definition of ``E1``, ``E2``, that is the |

3692 | kernel polynomial of the isogeny from ``E1`` to ``E2``. |

3693 | |

3694 | EXAMPLES:: |

3695 | |

3696 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_isogeny_kernel_polynomial |

3697 | |

3698 | sage: E = EllipticCurve(GF(37), [0,0,0,1,8]) |

3699 | sage: R.<x> = GF(37)[] |

3700 | sage: f = (x + 14) * (x + 30) |

3701 | sage: phi = EllipticCurveIsogeny(E, f) |

3702 | sage: E2 = phi.codomain() |

3703 | sage: compute_isogeny_kernel_polynomial(E, E2, 5) |

3704 | x^2 + 7*x + 13 |

3705 | sage: f |

3706 | x^2 + 7*x + 13 |

3707 | |

3708 | sage: R.<x> = QQ[] |

3709 | sage: K.<i> = NumberField(x^2 + 1) |

3710 | sage: E = EllipticCurve(K, [0,0,0,1,0]) |

3711 | sage: E2 = EllipticCurve(K, [0,0,0,16,0]) |

3712 | sage: compute_isogeny_kernel_polynomial(E, E2, 4) |

3713 | x^3 + x |

3714 | |

3715 | """ |

3716 | |

3717 | ker_poly = compute_isogeny_starks(E1, E2, ell) |

3718 | ker_poly = split_kernel_polynomial(E1, ker_poly, ell) |

3719 | |

3720 | return ker_poly |

3721 | |

3722 | |

3723 | def compute_intermediate_curves(E1, E2): |

3724 | r""" |

3725 | Computes isomorphism from ``E1`` to an intermediate domain and an |

3726 | isomorphism from an intermediate codomain to ``E2``. |

3727 | |

3728 | Intermediate domain and intermediate codomain, are in short |

3729 | Weierstrass form. |

3730 | |

3731 | This is used so we can compute `\wp` functions from the short |

3732 | Weierstrass model more easily. |

3733 | |

3734 | The underlying field must be of characteristic not equal to 2,3. |

3735 | |

3736 | INPUT: |

3737 | |

3738 | - ``E1`` - an elliptic curve |

3739 | - ``E2`` - an elliptic curve |

3740 | |

3741 | OUTPUT: |

3742 | |

3743 | tuple -- (``pre_isomorphism``, ``post_isomorphism``, ``intermediate_domain``, |

3744 | ``intermediate_codomain``): |

3745 | |

3746 | - ``intermediate_domain``: a short Weierstrass model isomorphic to ``E1`` |

3747 | - ``intermediate_codomain``: a short Weierstrass model isomorphic to ``E2`` |

3748 | - ``pre_isomorphism``: normalized isomorphism from ``E1`` to intermediate_domain |

3749 | - ``post_isomorphism``: normalized isomorphism from intermediate_codomain to ``E2`` |

3750 | |

3751 | EXAMPLES:: |

3752 | |

3753 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_intermediate_curves |

3754 | sage: E = EllipticCurve(GF(83), [1,0,1,1,0]) |

3755 | sage: R.<x> = GF(83)[]; f = x+24 |

3756 | sage: phi = EllipticCurveIsogeny(E, f) |

3757 | sage: E2 = phi.codomain() |

3758 | sage: compute_intermediate_curves(E, E2) |

3759 | (Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83, |

3760 | Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83, |

3761 | Generic morphism: |

3762 | From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 83 |

3763 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 62*x + 74 over Finite Field of size 83 |

3764 | Via: (u,r,s,t) = (1, 76, 41, 3), |

3765 | Generic morphism: |

3766 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 65*x + 69 over Finite Field of size 83 |

3767 | To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 77*y = x^3 + 49*x + 28 over Finite Field of size 83 |

3768 | Via: (u,r,s,t) = (1, 7, 42, 80)) |

3769 | |

3770 | sage: R.<x> = QQ[] |

3771 | sage: K.<i> = NumberField(x^2 + 1) |

3772 | sage: E = EllipticCurve(K, [0,0,0,1,0]) |

3773 | sage: E2 = EllipticCurve(K, [0,0,0,16,0]) |

3774 | sage: compute_intermediate_curves(E, E2) |

3775 | (Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1, |

3776 | Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1, |

3777 | Generic morphism: |

3778 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 |

3779 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 |

3780 | Via: (u,r,s,t) = (1, 0, 0, 0), |

3781 | Generic morphism: |

3782 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 |

3783 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 |

3784 | Via: (u,r,s,t) = (1, 0, 0, 0)) |

3785 | |

3786 | """ |

3787 | |

3788 | if (E1.base_ring().characteristic() in [2,3]): |

3789 | raise NotImplemented |

3790 | |

3791 | # compute the r,s,t values that clear the denominator of E1 |

3792 | a1 = E1.a1() |

3793 | a2 = E1.a2() |

3794 | a3 = E1.a3() |

3795 | |

3796 | s1 = -a1/2 |

3797 | r1 = (s1**2 + s1*a1 - a2)/3 |

3798 | t1 = (-r1*a1 - a3)/2 |

3799 | |

3800 | # compute the isomorphism from E1 to intermediate_domain |

3801 | pre_isom = WeierstrassIsomorphism(E1, (1, r1, s1, t1)) |

3802 | |

3803 | intermediate_domain = pre_isom.codomain().codomain() |

3804 | |

3805 | # compute the r,s,t values that clear the denominator of E2 |

3806 | a1pr = E2.a1() |

3807 | a2pr = E2.a2() |

3808 | a3pr = E2.a3() |

3809 | |

3810 | s2 = -a1pr/2 |

3811 | r2 = (s2**2 + s2*a1pr - a2pr)/3 |

3812 | t2 = (-r2*a1pr - a3pr)/2 |

3813 | |

3814 | post_isom_inv = WeierstrassIsomorphism(E2, (1, r2, s2, t2)) |

3815 | intermediate_codomain = post_isom_inv.codomain().codomain() |

3816 | |

3817 | post_isom = WeierstrassIsomorphism(intermediate_codomain, (1, -r2, -s2, -t2)) |

3818 | |

3819 | return (intermediate_domain, intermediate_codomain, pre_isom, post_isom) |

3820 | |

3821 | |

3822 | def compute_sequence_of_maps(E1, E2, ell): |

3823 | r""" |

3824 | Given domain ``E1`` and codomain ``E2`` such that there is a |

3825 | degree ``ell`` separable normalized isogeny from ``E1`` to ``E2``, |

3826 | returns pre/post isomorphism, as well as intermediate domain and |

3827 | codomain, and kernel polynomial. |

3828 | |

3829 | EXAMPLES:: |

3830 | |

3831 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import compute_sequence_of_maps |

3832 | sage: E = EllipticCurve('11a1') |

3833 | sage: R.<x> = QQ[]; f = x^2 - 21*x + 80 |

3834 | sage: phi = EllipticCurveIsogeny(E, f) |

3835 | sage: E2 = phi.codomain() |

3836 | sage: compute_sequence_of_maps(E, E2, 5) |

3837 | (Generic morphism: |

3838 | From: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field |

3839 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field |

3840 | Via: (u,r,s,t) = (1, 1/3, 0, -1/2), |

3841 | Generic morphism: |

3842 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field |

3843 | To: Abelian group of points on Elliptic Curve defined by y^2 + y = x^3 - x^2 - 7820*x - 263580 over Rational Field |

3844 | Via: (u,r,s,t) = (1, -1/3, 0, 1/2), |

3845 | Elliptic Curve defined by y^2 = x^3 - 31/3*x - 2501/108 over Rational Field, |

3846 | Elliptic Curve defined by y^2 = x^3 - 23461/3*x - 28748141/108 over Rational Field, |

3847 | x^2 - 61/3*x + 658/9) |

3848 | |

3849 | sage: K.<i> = NumberField(x^2 + 1) |

3850 | sage: E = EllipticCurve(K, [0,0,0,1,0]) |

3851 | sage: E2 = EllipticCurve(K, [0,0,0,16,0]) |

3852 | sage: compute_sequence_of_maps(E, E2, 4) |

3853 | (Generic morphism: |

3854 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 |

3855 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1 |

3856 | Via: (u,r,s,t) = (1, 0, 0, 0), |

3857 | Generic morphism: |

3858 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 |

3859 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1 |

3860 | Via: (u,r,s,t) = (1, 0, 0, 0), |

3861 | Elliptic Curve defined by y^2 = x^3 + x over Number Field in i with defining polynomial x^2 + 1, |

3862 | Elliptic Curve defined by y^2 = x^3 + 16*x over Number Field in i with defining polynomial x^2 + 1, |

3863 | x^3 + x) |

3864 | |

3865 | sage: E = EllipticCurve(GF(97), [1,0,1,1,0]) |

3866 | sage: R.<x> = GF(97)[]; f = x^5 + 27*x^4 + 61*x^3 + 58*x^2 + 28*x + 21 |

3867 | sage: phi = EllipticCurveIsogeny(E, f) |

3868 | sage: E2 = phi.codomain() |

3869 | sage: compute_sequence_of_maps(E, E2, 11) |

3870 | (Generic morphism: |

3871 | From: Abelian group of points on Elliptic Curve defined by y^2 + x*y + y = x^3 + x over Finite Field of size 97 |

3872 | To: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97 |

3873 | Via: (u,r,s,t) = (1, 8, 48, 44), |

3874 | Generic morphism: |

3875 | From: Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97 |

3876 | To: Abelian group of points on Elliptic Curve defined by y^2 + x*y + 9*y = x^3 + 83*x + 6 over Finite Field of size 97 |

3877 | Via: (u,r,s,t) = (1, 89, 49, 53), |

3878 | Elliptic Curve defined by y^2 = x^3 + 52*x + 31 over Finite Field of size 97, |

3879 | Elliptic Curve defined by y^2 = x^3 + 41*x + 66 over Finite Field of size 97, |

3880 | x^5 + 67*x^4 + 13*x^3 + 35*x^2 + 77*x + 69) |

3881 | |

3882 | """ |

3883 | |

3884 | (E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2) |

3885 | |

3886 | ker_poly = compute_isogeny_kernel_polynomial(E1pr, E2pr, ell) |

3887 | |

3888 | return (pre_isom, post_isom, E1pr, E2pr, ker_poly) |

3889 | |

3890 | |

3891 | # Utility function for manipulating isogeny degree matrices |

3892 | |

3893 | def fill_isogeny_matrix(M): |

3894 | """ |

3895 | Returns a filled isogeny matrix giving all degrees from one giving only prime degrees. |

3896 | |

3897 | INPUT: |

3898 | |

3899 | - ``M`` -- a square symmetric matrix whose off-diagonal `i`, `j` |

3900 | entry is either a prime `l` (if the `i`'th and `j`'th curves |

3901 | have an `l`-isogeny between them), otherwise is 0. |

3902 | |

3903 | OUTPUT: |

3904 | |

3905 | (matrix) a square matrix with entries `1` on the diagonal, and in |

3906 | general the `i`, `j` entry is `d>0` if `d` is the minimal degree |

3907 | of an isogeny from the `i`'th to the `j`'th curve, |

3908 | |

3909 | EXAMPLES:: |

3910 | |

3911 | sage: M = Matrix([[0, 2, 3, 3, 0, 0], [2, 0, 0, 0, 3, 3], [3, 0, 0, 0, 2, 0], [3, 0, 0, 0, 0, 2], [0, 3, 2, 0, 0, 0], [0, 3, 0, 2, 0, 0]]); M |

3912 | [0 2 3 3 0 0] |

3913 | [2 0 0 0 3 3] |

3914 | [3 0 0 0 2 0] |

3915 | [3 0 0 0 0 2] |

3916 | [0 3 2 0 0 0] |

3917 | [0 3 0 2 0 0] |

3918 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix |

3919 | sage: fill_isogeny_matrix(M) |

3920 | [ 1 2 3 3 6 6] |

3921 | [ 2 1 6 6 3 3] |

3922 | [ 3 6 1 9 2 18] |

3923 | [ 3 6 9 1 18 2] |

3924 | [ 6 3 2 18 1 9] |

3925 | [ 6 3 18 2 9 1] |

3926 | """ |

3927 | from sage.matrix.all import Matrix |

3928 | from sage.rings.infinity import Infinity |

3929 | |

3930 | n = M.nrows() |

3931 | M0 = copy(M) |

3932 | for i in range(n): |

3933 | M0[i,i]=1 |

3934 | |

3935 | def fix(d): |

3936 | if d==0: return Infinity |

3937 | return d |

3938 | |

3939 | def fix2(d): |

3940 | if d==Infinity: return 0 |

3941 | return d |

3942 | |

3943 | def pr(M1,M2): |

3944 | return Matrix([[fix2(min([fix(M1[i,k]*M2[k,j]) for k in range(n)])) for i in range(n)] for j in range(n)]) |

3945 | |

3946 | M1 = M0 |

3947 | M2 = pr(M0,M1) |

3948 | while M1!=M2: |

3949 | M1 = M2 |

3950 | M2 = pr(M0,M1) |

3951 | |

3952 | return M1 |

3953 | |

3954 | def unfill_isogeny_matrix(M): |

3955 | """ |

3956 | Reverses the action of ``fill_isogeny_matrix``. |

3957 | |

3958 | INPUT: |

3959 | |

3960 | - ``M`` -- a square symmetric matrix of integers. |

3961 | |

3962 | OUTPUT: |

3963 | |

3964 | (matrix) a square symmetric matrix obtained from ``M`` by |

3965 | replacing non-prime entries with `0`. |

3966 | |

3967 | EXAMPLES:: |

3968 | |

3969 | sage: M = Matrix([[0, 2, 3, 3, 0, 0], [2, 0, 0, 0, 3, 3], [3, 0, 0, 0, 2, 0], [3, 0, 0, 0, 0, 2], [0, 3, 2, 0, 0, 0], [0, 3, 0, 2, 0, 0]]); M |

3970 | [0 2 3 3 0 0] |

3971 | [2 0 0 0 3 3] |

3972 | [3 0 0 0 2 0] |

3973 | [3 0 0 0 0 2] |

3974 | [0 3 2 0 0 0] |

3975 | [0 3 0 2 0 0] |

3976 | sage: from sage.schemes.elliptic_curves.ell_curve_isogeny import fill_isogeny_matrix, unfill_isogeny_matrix |

3977 | sage: M1 = fill_isogeny_matrix(M); M1 |

3978 | [ 1 2 3 3 6 6] |

3979 | [ 2 1 6 6 3 3] |

3980 | [ 3 6 1 9 2 18] |

3981 | [ 3 6 9 1 18 2] |

3982 | [ 6 3 2 18 1 9] |

3983 | [ 6 3 18 2 9 1] |

3984 | sage: unfill_isogeny_matrix(M1) |

3985 | [0 2 3 3 0 0] |

3986 | [2 0 0 0 3 3] |

3987 | [3 0 0 0 2 0] |

3988 | [3 0 0 0 0 2] |

3989 | [0 3 2 0 0 0] |

3990 | [0 3 0 2 0 0] |

3991 | sage: unfill_isogeny_matrix(M1) == M |

3992 | True |

3993 | """ |

3994 | from sage.matrix.all import Matrix |

3995 | from sage.rings.infinity import Infinity |

3996 | |

3997 | n = M.nrows() |

3998 | M1 = copy(M) |

3999 | zero = Integer(0) |

4000 | for i in range(n): |

4001 | M1[i,i] = zero |

4002 | for j in range(i): |

4003 | if not M1[i,j].is_prime(): |

4004 | M1[i,j] = zero |

4005 | M1[j,i] = zero |

4006 | return M1 |