Elliptic Curve and a generator?

savecancel

I 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.