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$
4
  • 2
    $\begingroup$ By "manually", do you mean with just pencil and paper? $\endgroup$
    – fkraiem
    Commented Feb 16, 2017 at 14:25
  • 1
    $\begingroup$ Well, compared to factoring the order, $\frac{3\log n}2$ is really quite cheap... $\endgroup$
    – SEJPM
    Commented Feb 16, 2017 at 14:27
  • $\begingroup$ @fkraiem Yes, by hand $\endgroup$
    – AdHominem
    Commented Feb 16, 2017 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
    Commented Feb 16, 2017 at 15:41

2 Answers 2

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.

$\endgroup$
1
  • 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
    Commented Feb 18, 2017 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$

$\endgroup$
6
  • $\begingroup$ The OP asked manually, not programmatically. $\endgroup$
    – kelalaka
    Commented Sep 30, 2019 at 9:26
  • 1
    $\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$
    – 孙海城
    Commented Sep 30, 2019 at 13:14
  • $\begingroup$ Also, you say #P=10 but you find 18. $\endgroup$
    – kelalaka
    Commented Sep 30, 2019 at 14:15
  • $\begingroup$ @kelalaka I say $\#P=19$ , there are 18 points, and there is a implicit element, $O$ element. $\endgroup$
    – 孙海城
    Commented Sep 30, 2019 at 14:50
  • $\begingroup$ So, your code confusing, right? You forgot to include the point of infinity on your list. $\endgroup$
    – kelalaka
    Commented Sep 30, 2019 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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