Ask Your Question
1

Elliptic Curves and Isogenies in Sage

asked 2018-01-15 18:43:52 +0100

ninho gravatar image

updated 2018-01-15 21:13:07 +0100

I have the following Sage code which throws an error:

p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2 = Fp.extension(x^2 + 1, 'i')

# E0 is the starting curve E0/Fp2: y^2=x^3+x (the A=0 Montgomery curve)
E0 = EllipticCurve(Fp2, [1,0])
assert E0.is_supersingular()

phiP = E0([params[2], params[3]])
print "phiP =", phiP
phiQ = E0([-params[2], I*params[3]])
print "phiQ =", phiQ

param is a list of some big values. The phiP part executes sucessfully, and I get the correct values that I need, but the next line phiQ, throws and error. I believe because I want to have an imaginary number and multiply by I. The error that it throws is: TypeError: positive characteristic not allowed in symbolic computations . Any ideas what the problem is and how to workaround it?

Additionally, I also have a problem with the EllipcticCurveIsogeny function. Using the above prime and fields, I have something like this:

E = EllipticCurve(Fp2, [1,0])
ker = x^3 + 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576829*x^2 + x
phi = EllipticCurveIsogeny(E, ker)

But, this throws also an error, the error is: NotImplementedError: For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion.. Any idea how to call the isogeny function using a kernel?

EDIT:

params = [
    578430703315757416239167247452252298383230451121890570770496205879957246271\
        94741927699803619225371873099605244752411865273005490885339418654128746\
        61143122262830946833377212881592965099601886901183961091839303261748866\
        970694633,
    552894179318461736451145230096269508494216546007889788158066655273655541827\
        34966458946743147740010723538169667646894930981225566627558420019697816\
        87909521301233517912821073526079191975713749455487083964491867894271185\
        073160661,
    435991739684910123105333676370030089291509670001370421019478145780141273164\
        39883673898708868843364532451567754543362491991856542501590519299756008\
        57047173121187832546031604804277991148436536445770452624367894371450077\
        315674371,
    106866937607440797536385002617766720826944674650271400721039514250889186719\
        92313304948796673051468229664303969453105267287375412800684443463681956\
        65543642579133322371232938607676833959588179836843700655987261910882390\
        28762772
]
edit retag flag offensive close merge delete

Comments

without the params list it is impossible for us to reproduce.

Does the first problem also shows up if you use smaller numbers?

vdelecroix gravatar imagevdelecroix ( 2018-01-15 21:04:06 +0100 )edit

Check the edit for the params.

ninho gravatar imageninho ( 2018-01-15 21:13:17 +0100 )edit
add a comment

1 Answer

Sort by ยป oldest newest most voted
1

answered 2018-01-16 01:29:08 +0100

dan_fulea gravatar image

Usually, when using the constructor for a point of an elliptic curve E, the point should have components living in the field of coefficients of E. If not, sage tries to convert. In our case, the first conversion works, the second conversion fails. To fix this, use instead of I the root of $-1$ that exists in the field with $p^2$ elements. I will use j instead of $i$ and/or $I$. (So there is no need to restart sage...)

The second error comes from the fact that the polynomial is $x(x-1)^2$. Using $x(x-1)$ instead also fails. I tried to guess which is the isogeny to be used, using instead an explicit point $P_4(1,\sqrt2)$, which is $4$--torsion.

The following code shows the solution in a decent case.

F = GF(127)
R.<x> = PolynomialRing(Fp)
K.<j> = F.extension( x^2 + 1 )

E0 = EllipticCurve( K, [1,0] )
assert E0.is_supersingular()

params = ( None, None, 9, 22 )

phiP = E0( [ params[2],   params[3]] )
print "phiP =", phiP

phiQ = E0( [-params[2], j*params[3]] )
print "phiQ =", phiQ

E   = EllipticCurve( K, [1,0] )
P4  = E( ( 1, sqrt(F(2)) ) )
phi = EllipticCurveIsogeny(E, P4)
print "phi is:\n%s\n" % phi
print "phi has the kernel polynomial %s" % phi.kernel_polynomial().factor()

The prints are, after a slight manual rearrangement:

phiP = (9 : 22 : 1)
phiQ = (118 : 22*j : 1)
phi is:
Isogeny of degree 4 
  from Elliptic Curve defined by y^2 = x^3 + x 
    over Finite Field in j of size 127^2 
  to Elliptic Curve defined by y^2 = x^3 + 83*x + 15 
    over Finite Field in j of size 127^2

phi has the kernel polynomial x * (x + 126)

Note that $P_4$ is a point of order four, and the degree of $\phi$ is also four.

sage: P4.order()
4
sage: phi.degree()
4

The code can be now easily adapted to work over the more complicated posted situation.

edit flag offensive delete link more

Comments

Thank you for the good and clear answer. I have a question about the second part. The above code that I have posted is just an excerpt, but I'm executing the EllipticCurveIsogeny function inside a for loop for many iterations, where I also perform some calculations to get the kernel polynomial for each of the iterations. So, a different kernel polynomial is used in every iteration. Is there a way to get the explicit point from the kernel polynomial in Sage? So that I can convert the polynomial that I calculate at every iteration to an explicit point and use it in the isogeny function, seeing that using a kernel polynomial does not quite work.

ninho gravatar imageninho ( 2018-01-16 11:22:35 +0100 )edit
add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

subscribe to rss feed

Stats

Asked: 2018-01-15 18:43:52 +0100

Seen: 1,357 times

Last updated: Jan 16 '18

Related questions

Generate a list/table for cardinality of elliptic curve

Elliptic curve over binary field in Sage

elliptic curve

Finding Re() and Im() for complex numbers

NIST B-283 Elliptic Curve

solving sqrt(-1) to a real number

How to correctly load and use a pari/gp script in sage notebook [closed]

TypeError doing a contour plot of imag_part(I*log(x+I*y))

computing order of elliptic curves over binary field

Elliptic curves over function fields

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59