Given an elliptic curve, how do I calculate the order of the points manually, when we don't know about the curve's points?

Question

So basically all I can do is

1. use Lagrange's Theorem and figure which factors of the group order are in line, then
2. start trying each of these using the Double-and-Add-Algorithm until I get $\mathcal{O}$?

This takes forever if I do it by hand. Is there any easier way to find the order of all points? or find all the points on the curve?

Answer 1

Okay after some research: There is no shortcut. If you do it manually you need to proceed as suggested above. Realistically this is possible only for very small curves because of the complexity.

Answer 2

Given the Elliptic curve $E:y^2= x^3 + 2x + 2 \pmod {17}, \#P=19$

We can get all the points: by hands and by Python programming

1. For small number, we calculate it by hand. The procedure is:

1.1 For every $x$, we calculate $x^3 + 2x + 2 \pmod {17}$, the list is:

$x^3 + 2x + 2 \pmod {17}$　　　　　　　　　　　　　　　　　　$x$　　　　　　　　　　　

2　　　　　　　　　　　　　　　　　　　　　　　　　　　　[0, 7, 10]
3　　　　　　　　　　　　　　　　　　　　　　　　　　　　[8, 12, 14]
5　　　　　　　　　　　　　　　　　　　　　　　　　　　　[1]
6　　　　　　　　　　　　　　　　　　　　　　　　　　　　[4]
7　　　　　　　　　　　　　　　　　　　　　　　　　　　　[15]
9　　　　　　　　　　　　　　　　　　　　　　　　　　　　[6]    
12　　　　　　　　　　　　　　　　　　　　　　　　　　　　[11]
14　　　　　　　　　　　　　　　　　　　　　　　　　　　　[2]
15　　　　　　　　　　　　　　　　　　　　　　　　　　　　[13]
16　　　　　　　　　　　　　　　　　　　　　　　　　　　　[16]

1.2 Similarly, for every $y$, we calculate $y^2 \pmod {17}$ , the list is:

$y^2 \pmod {17}$　　　　　　　　　　　　　　　　　　　　　　$y$　

1　　　　　　　　　　　　　　　　　　　　　　　　　　　　[1, 16]
2　　　　　　　　　　　　　　　　　　　　　　　　　　　　[6, 11]
4　　　　　　　　　　　　　　　　　　　　　　　　　　　　[2, 15]
8　　　　　　　　　　　　　　　　　　　　　　　　　　　　[5, 12]
9　　　　　　　　　　　　　　　　　　　　　　　　　　　　[3, 14]
13　　　　　　　　　　　　　　　　　　　　　　　　　　　　[8, 9]
15　　　　　　　　　　　　　　　　　　　　　　　　　　　　[7, 10]
16　　　　　　　　　　　　　　　　　　　　　　　　　　　　[4, 13]

1.3. Find the sets of intersection with the same value of module, and calculate the product of the two sets.

For example, regarding the same module $1$, we calculate the product. $[3, 5, 9] \cdot [1, 16]$, the result is: $(3,1),(3,16),(5,1),(5,16),(9,1),(9,16)$

1.4. For all the same module, we get the total result(18 points):

$(0, 6), (0, 11), (3, 1), (3, 16), (5, 1), (5, 16), (6, 3), (6, 14), (7, 6), (7, 11), (9, 1), (9, 16), (10, 6), (10, 11), (13, 7), (13, 10), (16, 4), (16, 13) $

By adding the implicit infinity point $\mathcal{O}$, the $\#P=18+1=19$

2. We can use brute force algorithm with python program to find all the points on one curve.

Given the Elliptic curve $E:y^2= x^3 + 2x + 2 \pmod {17}, \#P=19$

2.1. We can get all the points by programming.

# -*- coding:UTF-8

import itertools

# y^2 = x^3 + 2x + 2 (mod 17)
p=17
a=2
b=2

xlable = dict()
ylable = dict()

# for all the number x, get the module (x^3 + ax + b) % p
def lablex(x):
   xlable.setdefault((x**3+a*x+b)%p, []).append(x)

# for all the number y, get the module (y^2) % p
def labley(y):
   ylable.setdefault((y**2)%p, []).append(y)

# calculate all the number
for num in range(0,p):
   lablex(num)
   labley(num)

# get all the points an length
intersect = []
for item in xlable.keys():
   if ylable.has_key(item):
       tmp = list(itertools.product(xlable[item], ylable[item]))
       intersect = intersect + tmp;
print "points:", sorted(intersect)
print "length:", len(intersect)

2.2. Run this program, we can get the result:

points: [(0, 6), (0, 11), (3, 1), (3, 16), (5, 1), (5, 16), (6, 3), (6, 14), (7, 6), (7, 11), (9, 1), (9, 16), (10, 6), (10, 11), (13, 7), (13, 10), (16, 4), (16, 13)]
length: 18

By adding the implicit infinity point $\mathcal{O}$, the $\#P=18+1=19$

2.3. For another Elliptic curve $E:y^2= x^3+x \pmod {257}, \#P=256$

We can also get the correct result.

points: [(0, 0), (1, 60), (1, 197), (3, 95), (3, 162), (4, 117), (4, 140), (6, 42), (6, 215), (10, 53), (10, 204), (11, 91), (11, 166), (12, 55), (12, 202), (15, 7), (15, 250), (16, 0), (18, 14), (18, 243), (19, 14), (19, 243), (21, 95), (21, 162), (22, 90), (22, 167), (23, 25), (23, 232), (24, 22), (24, 235), (27, 101), (27, 156), (28, 69), (28, 188), (34, 70), (34, 187), (35, 48), (35, 209), (37, 33), (37, 224), (38, 13), (38, 244), (39, 48), (39, 209), (42, 63), (42, 194), (43, 44), (43, 213), (46, 39), (46, 218), (47, 82), (47, 175), (49, 121), (49, 136), (52, 9), (52, 248), (54, 100), (54, 157), (56, 107), (56, 150), (59, 98), (59, 159), (61, 25), (61, 232), (63, 7), (63, 250), (64, 117), (64, 140), (66, 39), (66, 218), (67, 59), (67, 198), (68, 73), (68, 184), (70, 80), (70, 177), (73, 121), (73, 136), (74, 3), (74, 254), (75, 124), (75, 133), (77, 101), (77, 156), (78, 112), (78, 145), (80, 81), (80, 176), (81, 118), (81, 139), (82, 106), (82, 151), (84, 114), (84, 143), (86, 18), (86, 239), (88, 32), (88, 225), (92, 29), (92, 228), (95, 115), (95, 142), (99, 123), (99, 134), (100, 65), (100, 192), (101, 54), (101, 203), (102, 97), (102, 160), (104, 74), (104, 183), (106, 21), (106, 236), (107, 51), (107, 206), (112, 110), (112, 147), (115, 8), (115, 249), (119, 30), (119, 227), (120, 56), (120, 201), (122, 120), (122, 137), (125, 43), (125, 214), (132, 83), (132, 174), (135, 121), (135, 136), (137, 125), (137, 132), (138, 34), (138, 223), (142, 128), (142, 129), (145, 39), (145, 218), (150, 45), (150, 212), (151, 79), (151, 178), (153, 101), (153, 156), (155, 10), (155, 247), (156, 93), (156, 164), (157, 12), (157, 245), (158, 88), (158, 169), (162, 41), (162, 216), (165, 50), (165, 207), (169, 2), (169, 255), (171, 31), (171, 226), (173, 25), (173, 232), (175, 103), (175, 154), (176, 89), (176, 168), (177, 11), (177, 246), (179, 7), (179, 250), (180, 74), (180, 183), (182, 72), (182, 185), (183, 48), (183, 209), (184, 120), (184, 137), (187, 5), (187, 252), (189, 117), (189, 140), (190, 84), (190, 173), (191, 110), (191, 147), (193, 73), (193, 184), (194, 112), (194, 145), (196, 114), (196, 143), (198, 26), (198, 231), (201, 87), (201, 170), (203, 58), (203, 199), (205, 113), (205, 144), (208, 120), (208, 137), (210, 27), (210, 230), (211, 110), (211, 147), (214, 67), (214, 190), (215, 20), (215, 237), (218, 3), (218, 254), (219, 49), (219, 208), (220, 14), (220, 243), (222, 3), (222, 254), (223, 92), (223, 165), (229, 76), (229, 181), (230, 74), (230, 183), (233, 95), (233, 162), (234, 114), (234, 143), (235, 102), (235, 155), (236, 22), (236, 235), (238, 33), (238, 224), (239, 33), (239, 224), (241, 0), (242, 112), (242, 145), (245, 109), (245, 148), (246, 86), (246, 171), (247, 77), (247, 180), (251, 99), (251, 158), (253, 73), (253, 184), (254, 22), (254, 235), (256, 68), (256, 189)]
length: 255

By adding the infinity point $\mathcal{O}$, the $\#P=255+1=256$