3
$\begingroup$

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

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

And we know

[4]P = (19 , 20)

[8]P = (12 , 17)

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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Dec 12, 2021 at 14:38
  • $\begingroup$ If you look at the addition formulas you will see that when $P_1 = P_2 = [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. $\endgroup$
    – kelalaka
    Dec 12, 2021 at 14:47
  • $\begingroup$ @kelalaka Thanks for your answer. Is point halving possible on elliptic curves of odd order? $\endgroup$
    – Lordi
    Dec 12, 2021 at 15:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Dec 12, 2021 at 16:17
  • $\begingroup$ Now, you can vote up and accept in Cryptography.SE. upvote if the answer is good, accept if the answer is satisfactory. $\endgroup$
    – kelalaka
    Dec 14, 2021 at 11:04

1 Answer 1

Reset to default
1
$\begingroup$

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 $[2](x,y)$. We want $x$ to be equal 19, so:

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

We can verify that $[2](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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is there a formal definition of multiplication_by_m $\endgroup$
    – kelalaka
    Dec 13, 2021 at 11:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – Fractalice
    Dec 14, 2021 at 6:02
  • $\begingroup$ And. you may edit the question so that for future references it can be found easier. $\endgroup$
    – kelalaka
    Dec 14, 2021 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.