Ask Your Question
0

Elliptic Curve and a generator?

asked 2018-02-20 19:47:33 -0500

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

edit retag flag offensive close merge delete

Comments

Please provide a clear example. The simple answer would be to play with the order of $E$ and the one of the to-be-generator.

dan_fulea gravatar imagedan_fulea ( 2018-02-21 23:43:16 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2018-02-23 06:06:21 -0500

dan_fulea gravatar image

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.

edit flag offensive delete link more

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

Stats

Asked: 2018-02-20 19:47:33 -0500

Seen: 106 times

Last updated: Feb 23