ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 23 Feb 2018 13:06:21 +0100Elliptic Curve and a generator?https://ask.sagemath.org/question/41211/elliptic-curve-and-a-generator/ I have been googling to find out how to verify a certain element is a generator for a given elliptic curve.
Elliptic curve over Fp for a certain prime p.
p = 123456
E = EllipticCurve(GF(p), [0,1,0,1,-1])
g = E(11111111,22222222)
Q. how can I check that the element g is a generator?
I tried things like
E.abelian_group()
d = E.gens(); d
and it gives me a generator that does NOT match g.
I will appreciate for any hint/help/syntax!!
thanks
Wed, 21 Feb 2018 02:47:33 +0100https://ask.sagemath.org/question/41211/elliptic-curve-and-a-generator/Comment by dan_fulea for <p>I have been googling to find out how to verify a certain element is a generator for a given elliptic curve.</p>
<p>Elliptic curve over Fp for a certain prime p.
p = 123456
E = EllipticCurve(GF(p), [0,1,0,1,-1])</p>
<p>g = E(11111111,22222222)</p>
<p>Q. how can I check that the element g is a generator?
I tried things like
E.abelian_group()
d = E.gens(); d
and it gives me a generator that does NOT match g.</p>
<p>I will appreciate for any hint/help/syntax!!
thanks</p>
https://ask.sagemath.org/question/41211/elliptic-curve-and-a-generator/?comment=41229#post-id-41229Please provide a clear example. The simple answer would be to play with the order of $E$ and the one of the to-be-generator.Thu, 22 Feb 2018 06:43:16 +0100https://ask.sagemath.org/question/41211/elliptic-curve-and-a-generator/?comment=41229#post-id-41229Answer by dan_fulea for <p>I have been googling to find out how to verify a certain element is a generator for a given elliptic curve.</p>
<p>Elliptic curve over Fp for a certain prime p.
p = 123456
E = EllipticCurve(GF(p), [0,1,0,1,-1])</p>
<p>g = E(11111111,22222222)</p>
<p>Q. how can I check that the element g is a generator?
I tried things like
E.abelian_group()
d = E.gens(); d
and it gives me a generator that does NOT match g.</p>
<p>I will appreciate for any hint/help/syntax!!
thanks</p>
https://ask.sagemath.org/question/41211/elliptic-curve-and-a-generator/?answer=41241#post-id-41241I try to illustrate the situation in some simple cases first. Let us consider the curve with the posted parameters, and let the field of definition variate as follows:
for p in primes(100):
try:
E = EllipticCurve(GF(p), [0,1,0,1,-1])
print "p = %s generators are %s, order is %s" % ( p, E.gens(), E.order().factor() )
except Exception:
print "p = %s :: singular curve" % p
The results are:
p = 2 :: singular curve
p = 3 generators are ((2 : 1 : 1),), order is 3
p = 5 generators are ((0 : 2 : 1),), order is 3
p = 7 generators are ((1 : 4 : 1),), order is 2^2
p = 11 :: singular curve
p = 13 generators are ((9 : 8 : 1),), order is 2^2 * 3
p = 17 generators are ((5 : 16 : 1),), order is 2 * 13
p = 19 generators are ((18 : 13 : 1),), order is 2 * 7
p = 23 generators are ((2 : 6 : 1),), order is 29
p = 29 generators are ((27 : 15 : 1),), order is 2 * 17
p = 31 generators are ((18 : 2 : 1),), order is 3 * 11
p = 37 generators are ((22 : 4 : 1),), order is 41
p = 41 generators are ((10 : 17 : 1),), order is 2^4 * 3
p = 43 generators are ((40 : 8 : 1),), order is 2 * 5^2
p = 47 generators are ((20 : 37 : 1), (12 : 12 : 1)), order is 2^2 * 3^2
p = 53 generators are ((51 : 29 : 1), (31 : 28 : 1)), order is 2^4 * 3
p = 59 generators are ((41 : 14 : 1),), order is 3 * 19
p = 61 generators are ((37 : 56 : 1),), order is 2 * 31
p = 67 generators are ((32 : 51 : 1),), order is 3 * 19
p = 71 generators are ((25 : 50 : 1),), order is 67
p = 73 generators are ((22 : 35 : 1),), order is 2^2 * 3 * 7
p = 79 generators are ((62 : 16 : 1),), order is 2 * 3 * 13
p = 83 generators are ((50 : 12 : 1),), order is 2 * 43
p = 89 generators are ((8 : 7 : 1),), order is 5 * 19
p = 97 generators are ((1 : 14 : 1),), order is 5 * 17
A first observation is that in two cases $p=47$ and $p=53$ the group of rational points is not generated by one element. The answer to the posted question is thus always negative.
Let us consider an other example, $p=73$, because there is a better statistical chance to fail generation by random $\mathbb F_p$-rational point on the curve. (The order has more factors.) We consider now some random points on the curve and their orders.
E = EllipticCurve(GF(73), [0,1,0,1,-1])
for trial in range(10):
P = E.random_point()
print "P = %s has order %s" % ( P, P.order().factor() )
This gives this time:
P = (60 : 41 : 1) has order 2^2 * 3 * 7
P = (40 : 31 : 1) has order 2^2 * 3 * 7
P = (61 : 70 : 1) has order 2 * 3 * 7
P = (29 : 0 : 1) has order 2
P = (63 : 44 : 1) has order 2^2 * 7
P = (27 : 12 : 1) has order 2 * 7
P = (8 : 46 : 1) has order 2^2 * 3
P = (62 : 26 : 1) has order 2^2 * 7
P = (46 : 12 : 1) has order 2^2 * 3 * 7
P = (52 : 8 : 1) has order 7
And now we ask specifically in each case if the point $P$ is a generator. Then there are the following answers to the question, all of them start from the hypothesis that we know the order $N$ of the group of rational points on the given elliptic curve:
* It the prime $p$ is small, we can simply ask for the order of $P$, as above, and compare it with the order of the curve.
* We can check if $(N/2)P$, and/or $(N/3)P$, and/or $(N/7)P$ is zero on the curve. If yes, $P$ does not have full order, but an order dividing the one and/or the other of the numbers$N/2$, $N/3$, $N/7$. (Here, $2,3,7$ are the prime divisors of the order $N$.)
For instance, in the last case:
sage: E = EllipticCurve(GF(73), [0,1,0,1,-1])
sage: P = E.point( (52,8) )
sage: N = E.order()
sage: ZZ(N/2) * P
(0 : 1 : 0)
sage: ZZ(N/3) * P
(0 : 1 : 0)
sage: ZZ(N/7) * P
(45 : 22 : 1)
In all cases, we need some information on the curve, e.g. its order. This is relevant for "complicated" elliptic curves.
Fri, 23 Feb 2018 13:06:21 +0100https://ask.sagemath.org/question/41211/elliptic-curve-and-a-generator/?answer=41241#post-id-41241