Algorithm for dividing the point of an elliptic curve by a number
How to implement an algorithm for dividing by a number Z (scalar) a point lying on an elliptic curve?
Curve of the form: y^2 = x^3 + A * x + B
A, B and the number Z are known.
The point is arbitrary, lying on the curve. Operations are performed in the deduction ring.
For reference: Elliptic curve
5 answers
More details:
In the case of considering ЭК over a finite field, the algorithm for dividing a point by 2 can be implemented as follows:
ЭК – y^2=x^3+ax+b over the field GF(P),
n – the number of points (including the point at infinity),
P and n are prime numbers,
Q – the point on the elliptic curve to be divided by 2,
W – a point on an elliptic curve, which will be obtained in 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 a 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)
Wikipedia article: Discrete logarithm on an elliptic curve
There is no such algorithm. Since on an elliptic curve, you can only add and subtract points and multiply them by 2. When doubling a point, the angular coefficient is taken as the derivative (tangent) to the point. This angular coefficient cannot be calculated from a doubled point, because this tangent is already different, with a different angular coefficient. If such an algorithm existed, then there would be no cryptography using elliptic curves.
Applicable only in the deduction ring.
Q = (Qx,Qy) – the point on the elliptic curve to be divided by 2
P – modulus, prime number
N – maximum number of points
R = ((N-1)/2) * Q – point, intermediate value (multiplying a point by a scalar)
Q/2 = (R.x,P-R.y) – the result of "dividing" by 2
Note that it is impossible to calculate the point Q/r as a multiplication by r^-1 mod n, where n is the order of the point Q (the smallest integer n such that nQ=O), if the inverse element r modulo n does not exist.
b = a / 2.
so the meaning is what. there is a point b such that:
b + b = a.
it divides everything there at once. but there are nuances, 3 / 2 = b.
b + b = 3.