Topic: Is it possible to divide a point of an elliptic curve by a number? (Read 216 times)

garlonicon

copper member

Activity: 821

Merit: 1992

Quote

Is it correct?

Yes, it is. You can always divide a point by a known number if you just multiply it by the inverse of that number. You can divide by two or multiply by (n+1)/2. It works for any number.

Quote

Maybe do you know any JAVA libs?

If you use some library, it probably has something called "mod inverse", "modulo inverse" or similar.

Sanka555

member

Activity: 96

Merit: 36

I found that it possible and here some formules:

y^2=x^3+ax+b over the field GF(P),
n – the number of points (including a point at infinity),
P and n are prime numbers,
Q – a point on an elliptic curve that needs to be divided by 2,
W – a point on an elliptic curve that will turn out to be as a result, dividing Q by 2.
Algorithm:
Q/2 = W --> W ≡ Q * (2^(-1))(mod n) that is, it is necessary to multiply Q by the multiplicatively inverse number (inverse) modulo.
For 2 inverse (2^(-1)) (mod n) is the same as ((n-1)/2)+1.
W ≡ Q * (((n-1)/2)+1)(mod n)
For any other number r:
W ≡ Q * (r^(-1) mod n)

Is it correct? Maybe do you know any JAVA libs? Thank you!

Bitcoin Forum>Bitcoin>Development & Technical Discussion

Jump to: