Computing points on an elliptic curve

Question

I'm studying cryptography and I'm stuck with this problem here.

I have this elliptic curve $E: y^2=x^3+3 \pmod{17}$, that has $13$ points. Alice makes public the point $A=(1,2)$ and the point $B=aA=(2,2)$.

The question is list the possible values of the curve $E$.

Any idea?

Answer 1

The SageMath is your friend on the learning curve, it may help you check your calculations;

#define the field
K = GF(17)

#Set the Curve with equation y^2 = x^3 + b x + c where [b,c] is the parameters
E = EllipticCurve(K,[0,3])

#Get the group information
print(E.abelian_group())

#Get the size of the group
print( E.cardinality())

#iterate the element ( here print the elements with their order)
# !!! don't execute this on large ECC groups !!!

for R in E.points():
    print ("ord(",R,")=", R.order())

#define a point on the curve
#if given x and y doesn't satisfy the curve equation, you will get error

#your case provide error !!! so not on the curve
#P = E(2,2)

P = E(1,2)
print(P)

#You can add points, here doubling 
Q = P + P 
print(Q)

#here the scalar multiplication is normally written by [k]P
Q = 5*P

#get the X-projecrive coordinate
print(P[0])
#get the Y-projecrive coordinate
print(P[1])
#get the Z-projecrive coordinate
print(P[2])

#random element
R = E.random_element()
print(R)

#return one or all points with the given x coordinate.
E.liftx(x, all=False)

Now, some of the outputs

Additive abelian group isomorphic to Z/18 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 17
18
ord( (0 : 1 : 0) )= 1
ord( (1 : 2 : 1) )= 9
ord( (1 : 15 : 1) )= 9
ord( (3 : 8 : 1) )= 18
ord( (3 : 9 : 1) )= 18
ord( (4 : 4 : 1) )= 6
ord( (4 : 13 : 1) )= 6
ord( (5 : 3 : 1) )= 18
ord( (5 : 14 : 1) )= 18
ord( (6 : 7 : 1) )= 9
ord( (6 : 10 : 1) )= 9
ord( (9 : 1 : 1) )= 9
ord( (9 : 16 : 1) )= 9
ord( (10 : 0 : 1) )= 2
ord( (11 : 5 : 1) )= 3
ord( (11 : 12 : 1) )= 3
ord( (16 : 6 : 1) )= 18
ord( (16 : 11 : 1) )= 18

Note that the points are stored in projective coordinates with $(X:Y:Z)$ format in which $(X:Y:Z) = (\lambda X:\lambda Y:\lambda Z), \lambda \in \mathbb Z$ - in short defines an equivalence relation. One can convert projective coordinates into affine coordinates by $x =X/Z$, $y = Y/Z$ in which the capitals are used for projective coordinates.

Note that the identity of this curve is $\mathcal{O} = (0:1:0)$ has no presentation on the affine coordinates. Instead, we use this symbol $\mathcal{O}$ for it!

You might ask why the orders different, the answer is that the curve group is not prime. So, the Lagrange Theorem on the group theory applies; the order of any subgroup must divide the order of the group.