0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ By "manually", do you mean with just pencil and paper? $\endgroup$ – fkraiem Feb 16 '17 at 14:25
  • 1
    $\begingroup$ Well, compared to factoring the order, $\frac{3\log n}2$ is really quite cheap... $\endgroup$ – SEJPM Feb 16 '17 at 14:27
  • $\begingroup$ @fkraiem Yes, by hand $\endgroup$ – AdHominem Feb 16 '17 at 15:39
  • $\begingroup$ @SEJPM Well since it is done manually the number would be so small that factoring would actually be no problem $\endgroup$ – AdHominem Feb 16 '17 at 15:41
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The best curve to do by hand is $y^2=x^3+2x+2 mod 17$. When I have to talk through things with people, it's very tractable with only 19 points Start with $P=(5,1)$ $\endgroup$ – b degnan Feb 18 '17 at 18:40
-1
$\begingroup$

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$

| improve this answer | |
$\endgroup$
  • $\begingroup$ The OP asked manually, not programmatically. $\endgroup$ – kelalaka Sep 30 '19 at 9:26
  • $\begingroup$ @kelalaka I have given one way to calculate it by hand. You can check it. I think that the principle is the same by hand and by programming. You just transfer the program to handwork. $\endgroup$ – 孙海城 Sep 30 '19 at 13:14
  • $\begingroup$ Also, you say #P=10 but you find 18. $\endgroup$ – kelalaka Sep 30 '19 at 14:15
  • $\begingroup$ @kelalaka I say $\#P=19$ , there are 18 points, and there is a implicit element, $O$ element. $\endgroup$ – 孙海城 Sep 30 '19 at 14:50
  • $\begingroup$ So, your code confusing, right? You forgot to include the point of infinity on your list. $\endgroup$ – kelalaka Sep 30 '19 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.