1
$\begingroup$

I am studying elliptic curves in particular point counting. If I have coordinates P and 2P, is there a way to calculate the total points in between P and 2P using either curve parameters or algorithm?

The reason for the question is to determine if there is difference in the total number for each nP, without having to access all points via addition and doubling. A small example below for y^2 = x^3 + 7 where a=0, b=7 and prime =53. The total count between P and 2P is 6 from physically counting. The points are as follows: (2, 42), (2, 11), (6, 45), (6, 8), (8, 28), (8, 25), (9, 10)

When I increase to another curve with prime =97, the distance increases to 58 with P (1,69) & 2P (68,16) with the following points: (1, 28), (1, 69), (5, 61), (5, 36), (12, 59), (12, 38), (13, 19), (13, 78), (14, 61), (14, 36), (17, 19), (17, 78), (20, 76), (20, 21), (21, 21), (21, 76), (23, 7), (23, 90), (27, 75), (27, 22), (29, 90), (29, 7), (32, 59), (32, 38), (33, 65), (33, 32), (35, 69), (35, 28), (36, 43), (36, 54), (44, 5), (44, 92), (45, 90), (45, 7), (52, 16), (52, 81), (53, 38), (53, 59), (55, 30), (55, 67), (56, 76), (56, 21), (57, 30), (57, 67), (60, 45), (60, 52), (61, 28), (61, 69), (62, 43), (62, 54), (63, 52), (63, 45), (65, 5), (65, 92), (67, 78), (67, 19), (68, 81), (68, 16)

Thanks,

$\endgroup$
  • 4
    $\begingroup$ "in between P and 2P"; what do you mean "in between"? It would appear to mean "if you assume a specific curve representation, and if, in that representation, $P=(X1, Y1)$ and $2P = (X2, Y2)$, how many points have representations $(X, Y)$ with $X1 < X < X2$ or $X2 < X < X1$"? That is not a natural question (and would strongly depend on the representation you pick); I'd be surprised if there were an efficient algorithm for large curves... $\endgroup$ – poncho Jan 7 at 18:34
  • $\begingroup$ Cross posted Math.SE where it is closed. $\endgroup$ – kelalaka Jan 7 at 18:35
  • $\begingroup$ Yes, I am considering all X coordinates which are in between P and 2P. (P x P) = 2P, P + Q = next point via addition. $\endgroup$ – kmart875 Jan 7 at 18:48
  • 1
    $\begingroup$ I do not think we can efficiently find an exact answer. However we can find an approximation, under the heuristic assumption that the number is approximately proportional to $\max(|P_1-P_2|-1,0)$. $\endgroup$ – fgrieu Jan 7 at 19:13

Your Answer

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

Browse other questions tagged or ask your own question.