1

I am reading the book Zero to Monero: Second Edition from the GetMonero Library.

On the 3rd paragraph of page 15, the book mentions an algorithm for finding points inside the subgroup of order l, given an elliptic curve group of order N.

If I understand correctly, the group is assumed to be cyclic. Since in the last paragraph of page 14, it is assumed that P' is a generator.

Since the group is cyclic, we can identify it with Z/(N) = {0, P', 2P', ..., (N - 1)P'} where P' is a generator. Put h = 2, l = 3, then N = 6 and the subgroup of order l is Z/(l) = {0, 2P', 4P'}.

Next we want to check if 5P' is in Z/(l). Now 2(5P') = 10P' = 4P' != 0 mod 6. So by the algorithm, 5P' is in Z/(l)! But this clearly contradicts Z/(l) = {0, 2P', 4P'}.

Is this an error or am I misunderstand something?

Edit: My initial question is confusing. I modify it to specify P' as a generator to make it easier to distinguish between EC points and scalars.

0
3

Is this an error or am I misunderstand something?

No it is not an error, you are misunderstanding.

Since the group is cyclic, we can identify it with... Next we check if 5 is in...

Group elements are EC points, not scalars.

Now 2 · 5 ...

In the book, page 15 bullet 3, hP is a point multiplication, i.e. point P added to itself h times.

UPDATE incorporating your question edits above and comments below

With an initial group of {0, P, 2P, 3P, 4P, 5P} then using point 2P to select a subgroup with order l = 3, we have the subgroup {0, 2P, 4P}.

Now per the book, selecting a random point (5P in this example), we have:

h = N/l = 6/3 = 2
P' = 5P
P = hP' = 2P' = 4P

Again per the book, because P (here P = hP' = 2P' = 4P) is not 0, it is in the subgroup of order l = 3, which we can see is correct, 4P is indeed in the subgroup {0, 2P, 4P}.

I believe your confusion is this:

So by the algorithm, 5P' is in Z/(l)!

This statement is incorrect. Using your notation, the algorithm is actually saying 2(5P') is in Z/(l).

5
  • Hello jtgrassie. Thanks for answering. My initial question is confusing. I modify it to specify P' as a generator to make it easier to distinguish between EC points and scalars.
    – user11254
    Dec 17 '20 at 15:30
  • I've now fixed that confusing notation. What I really mean is 2(5P') = 10P' = 4P' mod 6.
    – user11254
    Dec 17 '20 at 16:06
  • If your initial group has points {0, P, 2P, 3P, 4P, 5P} (so order of 6) then the subgroup generated using 5P would have the same order and set of points (i.e. by adding 5P to itself until it reaches I yields the same set of points, {5P, 4P, 3P, 2P, P, 0}).
    – jtgrassie
    Dec 17 '20 at 18:57
  • Suppose the initial group has points {0, P', 2P', 3P', 4P', 5P'}. In step 1, we choose the subgroup order to be l = 3, so the subgroup is generated by 2P', with elements {0, 2P', 4P'}. In step 2, 5P' is the random point chosen.
    – user11254
    Dec 18 '20 at 18:23
  • And 2(5P) = 4P which is in the subgroup {0, 2P, 4P} because 2(5P) is not 0.
    – jtgrassie
    Dec 18 '20 at 21:24

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.