Elliptic Curve Point Division

5.9k Views Asked by At

I have seen several different responses to this type of question, and I find them all contradictory or unclear. This is a multi-part question.

  1. If I have a point Q on an elliptic curve over a finite field, can it be divided by an integer say 2 to find the point which generates it by being doubled?

To illustrate, let's take a toy example that I have seen elsewhere: $y^2 = x^3 + ax + b$

where:

a = -2

b = 1

*modulus = 89

With a Generator Point of (4,18) We get the set:

1 * P = (4, 18)    2 * P = (45, 73)
3 * P = (49, 28)   4 * P = (80, 64)
5 * P = (27, 36)   6 * P = (11, 81)
7 * P = (66, 47)   8 * P = (58, 40)
9 * P = (76, 12)   10 * P = (43, 52)
11 * P = (53, 26)  12 * P = (0, 88)
13 * P = (13, 6)   14 * P = (54, 19)
15 * P = (20, 60)  16 * P = (26, 80)
17 * P = (64, 88)  18 * P = (10, 64)
19 * P = (25, 88)  20 * P = (81, 22)
21 * P = (14, 15)  22 * P = (88, 25)
23 * P = (31, 2)   24 * P = (1, 0)
25 * P = (31, 87)  26 * P = (88, 64)
27 * P = (14, 74)  28 * P = (81, 67)
29 * P = (25, 1)   30 * P = (10, 25)
31 * P = (64, 1)   32 * P = (26, 9)
33 * P = (20, 29)  34 * P = (54, 70)
35 * P = (13, 83)  36 * P = (0, 1)

So, for example, I know that doubling 7*P (66,47) gives me the point 14*P (54,19).

  1. Is there a division operation which can take the point (54,19) and give me (66,47)? If so, could I do it again to 7*P, and what would be the result? 3*P or 4*P?

In this blog post towards the top, she mentions the Multiplicative Inverse being used in the division operation.

I am using a C# Library (found here) to calculate the values above, and it also has an "Extended Euclidean" Function which when I plug in 14*P (54,19) spits out (6,-17).

  1. Is (6,-17) the multiplicative inverse of (54,19), and if so how do I use it to get back to (66,47)

  2. If this is possible, can the same rules be applied to very large sets for example NIST P-192 or the secp256k1?

Thanks for your consideration and time.