ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 18 Mar 2020 02:55:08 -0500multiply the point by 2^-1 (mod n)http://ask.sagemath.org/question/50288/multiply-the-point-by-2-1-mod-n/ Public key x and y == Double(Half of the Public key x and y)
how to code this in sage math how to get coordinate x
x = f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
y = 388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
from this to >
x = c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413
y = 17f3dadd767275ddd3b23f46723631778bf01dadaebb9a953cf068712457c010
educomWed, 18 Mar 2020 02:55:08 -0500http://ask.sagemath.org/question/50288/Find order of an Elliptic Curve over Gaussian Integerhttp://ask.sagemath.org/question/49838/find-order-of-an-elliptic-curve-over-gaussian-integer/I am new with Sagemath. I just find out that Sagemath has Elliptic Curve Library and I curious to find out how to find order of an elliptic curve over Gaussian Integer.
p = 107927
G = ZZ[I]
J = G.ideal(p)
Q = G.quotient(J,'x')
a = Q(I)
A = (95385+100114*a)
B = (18724+61222*a)
E = EllipticCurve(Q,[A, B])
E
it will show :
Elliptic Curve defined by y^2 = x^3 + (-7813*I-12542)*x + (-46705*I+18724) over Quotient of Gaussian Integers in Number Field in I with defining polynomial x^2 + 1 with I = 1*I by the ideal (107927)
E.cardinality()
AttributeError: 'EllipticCurve_field_with_category' object has no attribute 'cardinality'
why it shows an error ?
I found the group order is 11648283482 (using python and the program that I made from scratch)
`edFri, 07 Feb 2020 01:18:05 -0600http://ask.sagemath.org/question/49838/Halving Point on curve25519http://ask.sagemath.org/question/49463/halving-point-on-curve25519/ Hi there,
Is there any ways in sagemath to half a point in curve25519? I found that mod inverse of 2 are not defined in this curve.
Thanks beforeZor-elThu, 09 Jan 2020 02:30:27 -0600http://ask.sagemath.org/question/49463/How do I obtain the generator of a elliptic curve? Is E.gens() only for the generator for the free part of the group or is for torsion also?http://ask.sagemath.org/question/49373/how-do-i-obtain-the-generator-of-a-elliptic-curve-is-egens-only-for-the-generator-for-the-free-part-of-the-group-or-is-for-torsion-also/Code:
sage: E = EllipticCurve([0,-1,0,-4,-2])
sage: E.gens()
[(3 : 2 : 1)]
sage: T = E.torsion_subgroup()
sage: T.points()
[(0 : 1 : 0), (-1 : 0 : 1)]
What is the generator of the group E(Q)?Is it the point (3,2) only? or the point (3,2)+(-1,0)?ABSun, 05 Jan 2020 03:20:33 -0600http://ask.sagemath.org/question/49373/Elliptic curve defined over completionhttp://ask.sagemath.org/question/49033/elliptic-curve-defined-over-completion/I have an elliptic curve E defined over the rationals and K is an imaginary quadratic field. I have a Heegner point P for E over K. I also have a rational prime p. Let q be a prime of K above p. I would like to use Sage to check whether the point P is divisible by p in E(K) and also in E(Kq) where Kq is the completion of K at the prime q. To check this in E(K) is easy; one can use the heegner_index() function or one can use the division_points() function. I am wondering if there is a way in Sage to do my required check in E(Kq). It seems to me that completions of number fields at finite primes are not defined in Sage.amatarSat, 14 Dec 2019 03:11:35 -0600http://ask.sagemath.org/question/49033/Sagemath refuses to load singular curvehttp://ask.sagemath.org/question/48982/sagemath-refuses-to-load-singular-curve/I know that this below Elliptic curve is singular at $(23796,0)$
F = GF(23981)
E = EllipticCurve(F,[0, 0, 0, 17230, 22699])
Since
$\frac{\partial f}{\partial x} = 3x^2 + 17230 =0 \pmod p$ and vanishes at $x=\{185,23796\}$ and $(185,0)$ not on the curve.
$\frac{\partial f}{\partial y} = -2y = 0 \pmod p$ and vanishes at $y=0$
I'm trying to define this curve to plot but SageMath gives the error;
> ArithmeticError: invariants (0, 0, 0, 17230, 22699) define a singular curve
How can I plot this curve?kelalakaMon, 09 Dec 2019 14:20:27 -0600http://ask.sagemath.org/question/48982/Pycharm + sage incorrect computationhttp://ask.sagemath.org/question/48503/pycharm-sage-incorrect-computation/I am using sage with Pycharm with sage by choosing Python2.7 from sage /bin directory like in guide in question 39742.
In computation on finite field there is bug or other incorrect behavior:
p = 5256107634024827443646803157596584915370839195839782329597601469354483229307063
j = 3611062252397503822281535488379195436991347721427144349104935225639485573271142
K = GF(p)
a = K((3 * j) / (1728 - j))
`a` is equals `5256107634024827443646803157596584915370839195839782329597601469354483229307059`, but in fact it should be `1674511800600631022371777328069227143110125063664501651628290807871952520681596`.
In stand-alone sage from terminal it works correctly. What should I do for working with sage from Pycharm with correct computation.
Latest version Mac OS, sage 8.9 from Homebrew, latest version Pycharm.SobiegFri, 25 Oct 2019 15:05:04 -0500http://ask.sagemath.org/question/48503/Elliptic curves - morphismhttp://ask.sagemath.org/question/48457/elliptic-curves-morphism/ Consider the example from the documentation:
sage: R.<u,v,t> = QQ[]
sage: Jacobian(u^3+v^3+t, variables=[u,v])
Elliptic Curve defined by y^2 = x^3 + (-27/4*t^2) over
Multivariate Polynomial Ring in u, v, t over Rational Field
how to obtain the morphism in this case?castorTue, 22 Oct 2019 03:04:13 -0500http://ask.sagemath.org/question/48457/elliptic curve : find only xhttp://ask.sagemath.org/question/48003/elliptic-curve-find-only-x/sir,
im a python programme and some idea of sagemath and c++ and .net
i study the btc cryptography seacp256k1
my problem is that
1. how to find x value where start from nearest of k so my loop is small and find the k
2.how to find cyclic ring where the repeate of x and ecliptic curve on seacp256k1 or bitcoin parameters
3.if i have x,y of public key and address how to find private key descrete logirithm problem loop is very large
how can i mage the small cuve , any apprelication or function if availabel in sagemath i required with baby step consider to proofsagemathecdlpSat, 21 Sep 2019 03:45:28 -0500http://ask.sagemath.org/question/48003/How to find a CM point with the image in the elliptic curve under modular parametrization givenhttp://ask.sagemath.org/question/47463/how-to-find-a-cm-point-with-the-image-in-the-elliptic-curve-under-modular-parametrization-given/ everyone! Let $E:y^2+y=x^3-61$ be the minimal model of the elliptic curve 243b. How can I find the CM point $\tau$ in $X_0(243)$ such that $\tau$ maps to the point $(3\sqrt[3]{3},4)$ under the modular parametrization? Can anyone tell me the answer or how to use sagemath to find it?
I use the sagemath code
EllipticCurve([0,0,1,0,-61])
phi = EllipticCurve([0,0,1,0,-61]).modular_parametrization()
f=phi.power_series(prec = 10000)[1]
f.truncate(20000)
to get the parametrization of y coordinate, then I use
q=var('q')
f(q)=
df=diff(f,q)
NewtonIt(q)=q-(f/df)(q)
xn=e^(2*pi*I*a/20.031)
for i in range(1000):
xn=N(NewtonIt(xn),digits=2000)
print xn
to get the numerical $e^{2\pi i \tau}$. After taking log and dividing by $2 \pi i$, I get the numerical $\tau$. But if I use
z=
p=z.algebraic_dependency(100)
I get the wrong polynomial. Why?
LeeSun, 11 Aug 2019 16:05:54 -0500http://ask.sagemath.org/question/47463/Height of point elliptic curve over finite fieldhttp://ask.sagemath.org/question/47310/height-of-point-elliptic-curve-over-finite-field/Is it possible to count height of point from elliptic curve over finite field? How do I do that with Sage?
Thanks before.zelleonTue, 30 Jul 2019 03:22:52 -0500http://ask.sagemath.org/question/47310/Why is exponentiation of points on elliptic curve so fast?http://ask.sagemath.org/question/46705/why-is-exponentiation-of-points-on-elliptic-curve-so-fast/I am working on elliptic curves in sagemath. I was trying to collect benchmarks for group operation and exponentiation of points on NIST P-256 elliptic curve. When I tried to perform a group operation on 2 points on the curve, it takes roughly 2 micro seconds. When I tried to perform exponentiation on a point in elliptic curve with a random exponent, it takes only 3 micro seconds. How is this even possible? Since I am exponentiating with a 256 bit value, this should at least take time required for 256 group operations, which is more than 1ms. I am worried if my code is wrong!
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
F = GF(p)
E = EllipticCurve(F, [-3,b])
runs = 10000
G = E.abelian_group()
F2 = GF(order)
exponent = [F2.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = Integer(exponent[i])*e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"
e1 = [G.random_element() for i in range(runs)]
e2 = [G.random_element() for i in range(runs)]
t1 = time()
for i in range(runs):
e = e1[i]+e2[i]
t2 = time()
print "Time per operation = ", (t2 - t1)/runs , " seconds"pantherWed, 29 May 2019 22:50:46 -0500http://ask.sagemath.org/question/46705/Putting label in the right spot (upper-left) during animationhttp://ask.sagemath.org/question/46496/putting-label-in-the-right-spot-upper-left-during-animation/I'm quite new to SageMath. It took some time (half a sunday) to create a code the draws an elliptic curve with a cubic, controlling the speed of the animation and putting a label in. However, I don't know where I can put something like a `legend_loc='upper left` somewhere or whether that's even possible. My code is as follows:
step=0.2;
var('x,y');
a=animate([
plot(EllipticCurve(y^2==x^3+3.8*x^2-0.8*x+float(k)),xmin=-6,xmax=0
,color="red",thickness=2,legend_label=r'$y^2=x^3+3.8x^2-0.8x+{}$'.format(float(k)))
+plot(EllipticCurve(y^2==x^3+3.8*x^2-0.8*x+float(k)),xmin=10^(-9),xmax=6
,color="red",thickness=2)
+ plot(x^3+3.8*x^2-0.8*x+float(k),xmin=-6,xmax=6,color="blue",thickness=1)
for k in srange(-5,5,step)],xmin=-6,xmax=6,ymin=-20,ymax=20,gridlines=[[-6,6],[-20,20]]);
a.show(delay=1)
I also tried `set_legend_options(shadow=False, loc=2)` in the `plot` function, but that doesn't satisfy SageMath either. Anyone an idea how I can put that label at some fixed spot? Btw, it would be even better if I could put that label on the top centre **above** the animation. I appreciate any suggestions and help.AlgebearSun, 12 May 2019 15:52:37 -0500http://ask.sagemath.org/question/46496/How to implement pairings on MNT curves?http://ask.sagemath.org/question/46491/how-to-implement-pairings-on-mnt-curves/I have used elliptic curves in sagemath. But I do not how to use pairings in sagemath.
I found a list of MNT curves at https://www.esat.kuleuven.be/cosic/publications/article-522.pdf
I also found some documentation on elliptic curves at
https://doc.sagemath.org/html/en/reference/curves/sage/schemes/elliptic_curves/ell_point.html
It provides ate_pairing, tate_pairing, weil_pairing functions. I don't know which one to use. I couldn't understand it. I do not know math behind pairings well enough. Please provide a simple code for performing pairing operations on these curves.pantherSat, 11 May 2019 20:26:27 -0500http://ask.sagemath.org/question/46491/How would I be able to check if a given number is a solinas prime?http://ask.sagemath.org/question/46327/how-would-i-be-able-to-check-if-a-given-number-is-a-solinas-prime/Using sage, how would I be able to check whether a given number is a general mersenne prime, or if possible any other special primes?
In particular, looking to check for special primes `p` such that modulo `p` is easy to calculatejonathansmithWed, 24 Apr 2019 01:36:50 -0500http://ask.sagemath.org/question/46327/elliptic curve arithmetic without inversionhttp://ask.sagemath.org/question/45784/elliptic-curve-arithmetic-without-inversion/ It seems when you add points on an elliptic curve in sage, it immediately divides by the z coordinate if it is not zero. Since I plan on working in a finite field of a large prime, I would rather it not calculate this inverse, but I'm not sure how to stop it from automatically doing so. How do I get it to leave the z coordinate alone so as to avoid inverting elements of my field?milksushFri, 15 Mar 2019 02:49:09 -0500http://ask.sagemath.org/question/45784/Elliptic Curve Twisthttp://ask.sagemath.org/question/45530/elliptic-curve-twist/Hello, I am trying to compute the quadratic twist for an example of an Elliptic curve defined over a GF(p^8) Field:
With
p=3351951982486667453837338848452726606028033606935065896469552348842908133596080151967071453287452469772970937967942438575522391344438242727636910570385409
and an Elliptic curve defined as:
E = ElllipticCurve(GF(p),[1,0])
given the extensions:
F2.<i> = GF(p^2, modulus=x^2 + 11)
F4.<j> = GF(p^4, modulus=x^4 + 11)
F8.<k> = GF(p^8, modulus=x^8 + 11)
I am trying to compute a twist of the elliptic curve defined over F8, of the twist equation form: y^2=x^3+a w^4 x, while a=1, and w satisfies the following: $w\in F_{p^8}$ and $w^4 \in F_{p^2}$, $w^2 \in F_{p^4}$ and $w^3 \in F_{p^{8}} \setminus F_{p^{4}}$
Is there any sage command that would help with this problem ?
Another way but I didn't know how to write it in sage: {1,w,w^2,w^3} are the basis of $F_{p^8}$ as a vector space over $F_{p^{2}}$.
Thanks in advance.JosephThu, 21 Feb 2019 10:03:56 -0600http://ask.sagemath.org/question/45530/x coordinate Of an Elliptic Curve pointhttp://ask.sagemath.org/question/45239/x-coordinate-of-an-elliptic-curve-point/I am defining an Elliptic curve E and then taking a random point P over E. now I want to print the x coordinate of the elliptic curve. How to do that ?
F.<z>=GF(2^11, modulus= conway_polynomial(2,11))
j= F.random_element()
E= EllipticCurve_from_j(j)
P= E.random_point()
Now I want to define w to be the x co-ordinate of P. BishwajitCThu, 31 Jan 2019 02:04:37 -0600http://ask.sagemath.org/question/45239/Get bit representation of an elliptic curve group elementhttp://ask.sagemath.org/question/44547/get-bit-representation-of-an-elliptic-curve-group-element/ I can define an elliptic curve using
> E = EllipticCurve(GF(97), [2,3])
I can then compute a group on E using
> G = E.abelian_group()
I can then sample a random element in the group using
> R = G.random_element()
Is there a way I can get a bit string representation of this group element R? Actually, I am implementing a pseudo-random generator scheme, which finally outputs a group element on elliptic curve. I need to convert it to a bit string.pantherMon, 03 Dec 2018 04:38:55 -0600http://ask.sagemath.org/question/44547/generate random elliptic curve of prime orderhttp://ask.sagemath.org/question/44480/generate-random-elliptic-curve-of-prime-order/As required in many cryptographic algorithms, I would like to sample a group (in this case, an abelian group defined on elliptic curve) of a random prime order. I know how to define an elliptic curve with given parameters, and then calculate its order. But how to sample an elliptic curve of random prime order?pantherTue, 27 Nov 2018 21:24:16 -0600http://ask.sagemath.org/question/44480/Determining Elliptic Curve Componentshttp://ask.sagemath.org/question/44274/determining-elliptic-curve-components/Say we have an elliptic curve:
R.<a,b,c> = QQ[]
cubic = a*(a+c)*(a+b)+b*(b+c)*(a+b)+c*(b+c)*(a+c)-4*(a+b)*(a+c)*(b+c)
E = EllipticCurve_from_cubic(cubic, morphism=False)
print(E)
print(E.minimal_model())
f = EllipticCurve_from_cubic(cubic, morphism=True)
finv = f.inverse()
generators = E.gens()
print
print("generators = %s" %(generators))
Output:
Elliptic Curve defined by y^2 + x*y = x^3 + 69*x^2 + 1365*x + 8281 over Rational Field
Elliptic Curve defined by y^2 + x*y + y = x^3 - 234*x + 1352 over Rational Field
generators = [(-39 : 52 : 1)]
How do we determine which of the two elliptic curve components a particular point is on? If we had this elliptic curve in the form $y^2 = x^3 + 109 x^2 + 234 x$ it'd be quite simple (if $x<0$ it's on the egg). Is there a nice way to automate this process in SageMath? For example, in this case the generator is on the egg.octonionTue, 13 Nov 2018 19:59:02 -0600http://ask.sagemath.org/question/44274/Elliptic Curve: Python int too large to convert to C longhttp://ask.sagemath.org/question/44054/elliptic-curve-python-int-too-large-to-convert-to-c-long/I'd like to plot the secp256k1 curve, but I get "Python int too large to convert to C long". Does sage have a built-in type to handle large numbers, or is there a recommended way to do this?
p=2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
A=0
B=7
F=GF(p)
F=GF(p)
E = EllipticCurve( [A,B] )
show(graphics_array([plot(E,thickness=3), plot(E.change_ring(GF(p)))]), frame=True)
Traceback:
Traceback (most recent call last): A=0
File "", line 1, in <module>
File "/private/var/folders/k6/lrb1z5jd7vx95c7lh05kq6v00000gn/T/tmpmwcLjo/___code___.py", line 14, in <module>
exec compile(u'show(graphics_array([plot(E,thickness=_sage_const_3 ), plot(E.change_ring(GF(p)))]), frame=True)
File "", line 1, in <module>
File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/misc/decorators.py", line 567, in wrapper
return func(*args, **options)
File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/plot/plot.py", line 1941, in plot
G = funcs.plot(*args, **original_opts)
File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 107, in plot
G += plot.points([P[0:2] for P in self.points() if not P.is_zero()], *args, **kwds)
File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 208, in points
v = self._points_via_group_structure()
File "/Users/Jbaczuk/Documents/Personal/SageMath/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_finite_field.py", line 150, in _points_via_group_structure
for m in range(1,ni[0]):
OverflowError: Python int too large to convert to C longjbaczukWed, 24 Oct 2018 09:43:51 -0500http://ask.sagemath.org/question/44054/Reducing a polynomial over a function field modulo a valuationhttp://ask.sagemath.org/question/43965/reducing-a-polynomial-over-a-function-field-modulo-a-valuation/ In my situation, I have the following elliptic curve:
K.<t> = FunctionField(QQ)
E = EllipticCurve([t,t])
I want to be able to go modulo t to get the curve
z*y^2 - x^3 = 0
I cannot figure out how to do this. I would like to work with valuations if possible (like going mod K.valuation(0)), but any way to make this work would be great. In general, I'd like to be able to go modulo any irreducible polynomial.trbillinTue, 16 Oct 2018 08:22:31 -0500http://ask.sagemath.org/question/43965/Calculating the order of an Elliptic Curve fails.http://ask.sagemath.org/question/43765/calculating-the-order-of-an-elliptic-curve-fails/Hi. I would like to calculate the order of the base point on an Elliptic Curve. Some curves are successful while some fail.
Here are two examples and their parameters. The first example is successful, the second is not.
Example 1.
p = 10562920556476600174223203553624763158759224241690200395609486946570543757980521851146458516500451409335864053457189473296570712977858859585999979839497081
a = 1
b = 0
E = EllipticCurve(GF(p), [a, b])
Gx = 7001153264502603531568809091006890066238093206490706740054133060198019760090859987689015805782317128823647585142349315457499198272662472818714043462452903
Gy = 5379780378477219053711555876878459214243674711784518156355184015695786277532464885846858297098947964642836892714492422913471742703229817151186461774623684
G = E(Gx, Gy)
Q = G.order()
Q = 5532044755580494717
Example 2.
p = 8245498483844445086274997696534494324318871629323439587180432555305925857658196874670618312457436840885370130522487176480691396150486059031119600012524801
a = 1
b = 0
E = EllipticCurve(GF(p), [a, b])
Gx = 7273571546843413099993191994471155206649636421268389195048812757571665656628711965470673099293494650775090608549703675296316887753017258939382696588767431
Gy = 3529068830277582088596828423990199939817342479929127252014627303069162247307070606247527579307935679046819531543049464667736359244475241042487530444236684
G = E(Gx, Gy)
Q = G.order()
*** Warning: MPQS: number too big to be factored with MPQS,
giving up.
both these two curves are working curves. but why does sage fail to calculate the second curves order of G? Is it a limitation of sage itself? Is there any other way to calculate the order without using MPQS method?pottzmanTue, 25 Sep 2018 18:05:43 -0500http://ask.sagemath.org/question/43765/generating the ring for schoof's division polynomialshttp://ask.sagemath.org/question/43301/generating-the-ring-for-schoofs-division-polynomials/ hello,
i want to generate the ring $F_p[x,y]/(y^2-x^3-ax-b)$, which is necessary to compute the division polynomials in schoof's algorithm to compute the amount of elements of a elliptic curve of the form $y^2=x^3+ax+b$ over $F_p$.
I already tried this:
R.<x,y>=PolynomialRing(Zmod(p))
F=R.quo(y^2-x^3-ax-b)
x,y=F.gens()
When i computed some division polynomials in the generated F and matched them with division polynomials which sage computed by this:
F=Zmod(p)
E=EllipticCurve(F,[a,b])
E.division_polynomial()
i saw that my computed division polynomials must be wrong. Does anyone have an idea for generating the Ring $F_p[x,y]/(y^2-x^3-ax-b)$ or generating a "pseudo" elliptic curve in sage, because this code
F=Zmod(p)
E=EllipticCurve(F,[a,b])
E.division_polynomial()
doesn't work if $p$ isn't prime of course.
gebertlukiThu, 09 Aug 2018 18:42:18 -0500http://ask.sagemath.org/question/43301/Evaluating the error "Can only substitute elements of positive valuation"http://ask.sagemath.org/question/42382/evaluating-the-error-can-only-substitute-elements-of-positive-valuation/I'm trying to work with sage's weierstrass_p function for elliptic curves, and I'm getting an error that I can't interpret.
This is what I'm running,
E = EllipticCurve('11a1')
WP = E.weierstrass_p()
L = E.lseries()
WP(L(1))
The error I'm getting is
"Can only substitute elements of positive valuation"
And I just don't know why sage doesn't want to evaluate the function at the given value.
Any thoughts would be really appreciated!JHalesMon, 21 May 2018 11:26:37 -0500http://ask.sagemath.org/question/42382/Twists of an Elliptic Curve over a Finite Field (secp256k1)http://ask.sagemath.org/question/42306/twists-of-an-elliptic-curve-over-a-finite-field-secp256k1/ I would like to calculate the twists of secp256k1 up to isomorphism (find one representative for the quadratic twist, and so on). Therefore I tried the function <br/>
E.quadratic_twist(d) and E.sextic_twist(d) <br/>
with E = EllipticCurve(GF(115792089237316195423570985008687907853269984665640564039457584007908834671663), [0,0,0,0,7]).
<br/>
The problem is that I don't understand what the variable $d$ does in this function. <br/>
I tried different $d$ and found a quadratic twist with $d=3$ $E' : y^2 = x^3 + 12096 = x^3 + 7 \cdot (12)^3$ and tested that $12$ is square-free in $\mathbb{F}_q$, and two sextic twists with $d=3,7$: $E^{d_6}_1: y^2 = x^3 + 7\cdot 139968$ and $E^{d_6}_2: y^2 = x^3 + 7\cdot 326592$ with $139968$ and $326592$ square- and cube-free in $\mathbb{F}_q$. <br/>
<br/>
But my method is rather brute-force, since I don't really understand the function, and I am also not sure how many different sextic twists sexp256k1 has (up to isomorphism). I think it is two, but I am not sure. <br/>
<br/>
My next question is, if there is a way to calculate the cubic twist with a similar function?
SoftyThu, 10 May 2018 09:55:45 -0500http://ask.sagemath.org/question/42306/Early abort for E.cardinality()http://ask.sagemath.org/question/33943/early-abort-for-ecardinality/I loop through curves to find one with prime cardinality. In order to speed up the process, it would be convenient to have early abort option, so that whenever some prime factor of cardinality is found, the algorithm skips that curve and goes to the next one. Any suggestions how this can be done?VovaMon, 27 Jun 2016 14:38:02 -0500http://ask.sagemath.org/question/33943/Isogeny computation for larger numbers doesn't finishhttp://ask.sagemath.org/question/41214/isogeny-computation-for-larger-numbers-doesnt-finish/I have the following code segment in Sage:
from sage.all import *
proof.arithmetic(False)
f = 1
lA = 2
lB = 3
eA = 372
eB = 239
p = f*lA**eA*lB**eB-1
assert p.is_prime()
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<j> = Fp.extension(x^2 + 1)
E_0 = EllipticCurve(Fp2, [1,0])
assert E_0.is_supersingular()
l = [lA, lB]
e = [eA, eB]
def starting_node(E_i, count):
if count == 96:
return E_i
kers = E_i(0).division_points(3)
P = E_i(0)
while P == E_i(0):
P = kers[randint(0, 8)]
psi = E_i.isogeny(P)
return starting_node(psi.codomain(), count+1)
def walk(E_i, j,lvl, prev_j ,max_lvl):
children = {}
if lvl < max_lvl:
for P in E_i(0).division_points(2):
if P == E_i(0):
continue
psi = E_i.isogeny(P)
E_child = psi.codomain()
j_child = str(E_child.j_invariant())
lvl_child = lvl+1
if j_child in children:
children[j_child] += 1
else:
children[j_child] = 1
if (j_child != prev_j) or (children[j_child] > 1):
walk(E_child, j_child, lvl_child,j, max_lvl)
idx = 0
E = starting_node(E_0, 0)
print "start: ", str(E.j_invariant())
walk(E, str(E.j_invariant()), 0, "", e[idx])
The above code seems to execute fine when I use smaller values, but still it executes very slowly. Whereas, when I use the above numbers it does not finish with the execution. There already seems to be a similar problem mentioned [here](https://ask.sagemath.org/question/40675/isogeny-computation-does-not-finish-in-sage/), but the solution there seems to be just for 3-isogenies, but what about the general case, for different isogenies and using kernels? Also Magma seems to handle isogeny computations quite efficiently, why is Sage having such a hard time? Any ideas how can I modify the above code so that it actually finishes the execution in a "reasonable" time?ninhoWed, 21 Feb 2018 04:31:58 -0600http://ask.sagemath.org/question/41214/Even degree large isogeny computationhttp://ask.sagemath.org/question/41236/even-degree-large-isogeny-computation/I want to calculate $2^{372}$ and $3^{239}$ degree isogenies in Sage, but what I noticed is that using `EllipticCurveIsogeny` function does not finish executing for such large degree isogenies. There is already a partial answer by Dan Fulea [here](https://ask.sagemath.org/question/40675/isogeny-computation-does-not-finish-in-sage/), but it does not seem to work for the even degree isogenies, and also for the above mentioned large degree odd isogeny as there is no chaining of small degree ones.
So, basically I have the following class from Dan's answer:
class EllipticCurveWithTorsionPoint(object):
"""
Class putting together in a bag:
- an elliptic curve,
- with a point R with same order as isogeny degree,
- and with a list of other points.
The main method <image> will associate an object of the same instance,
which is the "image" of the given structure w.r.t. the isogeny with kernel O, R, 2R, ... (d-1)R.
"""
def __init__(self, E, R, d=None, points=[]):
"""
E should be given in Weierstrass form.
"""
self.is_valid = True # so far
self.E = E
if E != EllipticCurve(E.base_field(), [E.a4(), E.a6()]):
self.is_valid = False
self.points = points
self.R = R
if d:
self.d = ZZ(d)
else:
self.d = ZZ(R.order())
print "Computed: order of R is %s" % R.order().factor()
if 2.divides(self.d):
print "This class works only for an odd order d, but d=%s" % self.d
self.valid = False
self.kernel = [k*R for k in [0..(self.d-1)]]
self.d1 = ZZ((self.d-1) / 2)
def image(self):
"""
Pass to E', here denoted EE, the curve which is isogenous to E, so that
ker(E -> E') is {0, R, 2R, ... (d-1)R}. Also map to E' all the existing structure.
"""
if not self.is_valid:
print "Invalid object, no image is computed"
return self
E = self.E
F = E.base_field()
R = self.R
if R == E(0):
print "No further isogeny can be built"
return self
a, b = E.a4(), E.a6()
v, w = F(0), F(0)
data = []
for mult in [1..self.d1]:
# We split the set G = R, 2R, ... , (d-2)R, (d-1)R in two, G(+)
# and G(-) so that P in G(+) <=> -P in G(-), the multiplicities
# above correspond to those for G(+).
P = mult*R # point in G(+)
xP , yP = P.xy()
gxP, gyP = 3*xP^2 + a, -2*yp
vP , uP = 2*gxP , gyP^2
v += vP
w += uP + xP*vP
data.append([xP, yP, uP, vP])
EE = EllipticCurve(F, [a-5*v, b-7*w])
def phi(point):
print "Computing phi(%s)..." % str(point)
if point in self.kernel:
return EE(0)
x , y = point.xy()
xx, yy = x, y
for xP, yP, uP, vP in data:
xx += vP /(x-xP) + uP /(x-xP)^2
yy -= uP*2*y/(x-xP)^3 + vP*y/(x-xP)^2
return EE((xx, yy))
return EllipticCurveWithTorsionPoint(EE
, EE(0)
, d = 1
, points = [phi(point) for point in self.points])
def imageStrandard(self):
"""
This does the same thing as "image" method but using the Sage
isogeny implementation.
"""
if not self.is_valid:
return self
E = self.E
R = self.R
phi = EllipticCurveIsogeny(E, R)
EE = phi.codomain()
return EllipticCurveWithTorsionPoint(EE
, EE(0)
, d = 1
, points = [phi(point) for point in self.points])
But when | try to calculate isogeny, using the following field and elliptic curve:
p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<j> = Fp.extension(x^2 + 1)
E = EllipticCurve(Fp2, [1,0])
and the following elements:
R = (9007518108646169717637829256143902727256908604612852170262845383236308734546752870948023665818612994373405439104311563180515971827416888758364379345147971116263603311381076594736408857657724917306603115510356333363208849059629*j + 8143875544876203102731118758998042519548033956324586056599014675159430178641351639084698635604334996400279245810044652728374901773305503117205094200107841651156165349992200320758569566012680521517849444975619314122642286738078 : 5933067621852699133314119054291511797259450704514751366342623924502189539964363940282453138760679452407770908256363554867263728524097776132882938143129922521585626385240622607283870971683009886348379499590584807528366215593257*j + 3243060684426863808401390460086135176972427334603406644358264254553792355536601776050361287848102972929373427788393162068323805718475829130551068182582167101080584984966674872491237953303465307684436948645319932524248022850554 : 1)
phiP = (5784307033157574162391672474522522983832304511218905707704962058799572462719474192769980361922537187309960524475241186527300549088533941865412874661143122262830946833377212881592965099601886901183961091839303261748866970694633 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661 : 1)
phiQ = (4570410708611731090586095763344282337595085134330165462411227620255106477963004653732902534638529526314592687143599015857903362887988612527631285807628029554145760006701700452765434631350888025796273995011688240123798680882198 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661*j : 1)
such that
X = EllipticCurveWithTorsionPoint(E, R, None, [phiP, phiQ])
W = X.image()
It doesn't seem to finish execution, where R has order $3^{239}$. And the class doesn't even work for an even degree isogeny, for example, evaluation this one:
R = (5110605836845566926025654047424167572170042372900551706614198682868609124986515618280597159249062586518558366705653348177099645521579421315786637369850653444795496916683519951328090963213358196198661324642758054901662568911454*j + 4234869830555943849779568791108578084407579904872225169650118735805222570371281152259184280337943783338310393473931143980765745444039692659441232529288102314058310400426732946525612162308610371741399922257500660578782200917155 : 5100498610209823809391228850023209691234397421134363575826918390640143899484912001953261335357385806761065415074391051805515401642580444835961489218757392256505375361061973605756427459420249731757621385279542696786456958672535*j + 3945657958394557421465268691904614939064430526791563586067697568085750995914128796629365705178878140816178998799696237175564589123664889202169294820353858542756862036043886052635535912561145255328107702126311995666291927980188 : 1)
phiP = (4359917396849101231053336763700300892915096700013704210194781457801412731643988367389870886884336453245156775454336249199185654250159051929975600857047173121187832546031604804277991148436536445770452624367894371450077315674371 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772 : 1)
phiQ = (5994800344920204021924431474166504428512292945535366959921408221253266209038490479113012009676730260379396436164503953186018257726363502463068559611723978695788874294047308530080408582516238481209782462483097130422588335902460 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772*j : 1)
such that
X = EllipticCurveWithTorsionPoint(E, R, None, [phiP, phiQ])
W = X.image()
where R has degree $2^{372}$. How can one chain 2 and 3 isogenies compute high degree isgonies that are powers of 2 and 3?. Any ideas how to do these efficiently in Sage so that the computations finish a "reasonable" time?ninhoThu, 22 Feb 2018 16:20:01 -0600http://ask.sagemath.org/question/41236/