# Is it possible to calculate multiplication inverse of a point on elliptic curve?

The title must be confusing. Imagine we have this curve:

$$y^2 = x^3 + 9x + 17$$ over $$\mathbb F_{23}$$

And we know

P = (19 , 20)

P = (12 , 17)

If we only have the value of $$P$$, Is it possible to calculate $$2^{-1}X$$ and $$2^{-1}Y$$ of $$P$$ to get $$P$$?

• Point halving: Point halving on elliptic curves of even order and article Point halving on elliptic curves of even order. I've corrected the notation, and even we say $x(P)$ for the x-coordinate of point $P$. This curve has an even order = 32, so it is applicable but not the way you look. Point doubling doesn't work in that way. Dec 12, 2021 at 14:38
• If you look at the addition formulas you will see that when $P_1 = P_2 = P_1$ is not multiplication by 2. You can plug your numbers and do the arithmetic in the first link to find it without discrete log. Dec 12, 2021 at 14:47
• @kelalaka Thanks for your answer. Is point halving possible on elliptic curves of odd order? Dec 12, 2021 at 15:46
• Be careful halving in even order may result in a double solution that prevents solving DLOG. In the odd case, let $n = 2k-1$ be the order then we can find the halve as; $[1/2]G = [k]G$ why? Because $[2k-1]G = \mathcal{O}$ then $[2k-1]G + G = G$ so $[k]G = [1/2]G$. This is a well-defined map for abelian groups of odd order. Dec 12, 2021 at 16:17
• Now, you can vote up and accept in Cryptography.SE. upvote if the answer is good, accept if the answer is satisfactory. Dec 14, 2021 at 11:04

Since 2 divides the group order (which is 32), there are two preimages. They can be found as roots of the multiplication-by-2 polynomial minus the target $$x$$ (which can be computed from division polynomials).

Example in Sage:

sage: E = EllipticCurve(GF(23), [9, 17])
sage: E.multiplication_by_m(2)
((x^4 + 5*x^2 + 2*x - 11)/(4*x^3 - 10*x - 1),
(8*x^6*y - 8*x^4*y + 6*x^3*y + 3*x^2*y + 3*x*y + 6*y)/(-5*x^6 + 2*x^4 - 9*x^3 + 9*x^2 + 11*x + 4))


These are the two rational maps for computing $$x$$ and $$y$$ of the point $$(x,y)$$. We want $$x$$ to be equal 19, so:

sage: (E.multiplication_by_m(2) - 19)
.numerator()
.univariate_polynomial()
.roots(multiplicities=False)
[20, 10]


We can verify that $$(20, *) = (19, *)$$. Note that the sign of $$y$$ has to be chosen to match the output sign.

sage: P = E.lift_x(20)
sage: 2*P
(19 : 3 : 1)
sage: 2*(-P)
(19 : 20 : 1)


Can be repeated twice to get 4-roots, or use the multiplication-by-4 map directly (which is a bit less efficient).

• Is there a formal definition of multiplication_by_m Dec 13, 2021 at 11:59
• @kelalaka multiplication_by_m is a pair of functions $(f(x),y\cdot g(x))$, such that this pair equals to $[n]P$ when $P=(x,y)$. On the wikipedia page about division polynomials I linked, there are formulas for constructing $f(x)$ and $g(x)$, which are rational functions. Dec 14, 2021 at 6:02
• And. you may edit the question so that for future references it can be found easier. Dec 14, 2021 at 11:03