# Dividing a point by a specific number in elliptic curve

There is an elliptic curve with parameters:

a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635
b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320


Also the prime number is:

q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297


How can I solve the equation 65537 * P = H and obtain the value of P?

P and H are points and H equals to (72782057986002698850567456295979356220866771008308693184283729159903205979695, 7766776325114464021923523189912759786515131109431296018171065280757067869793).

Note that in the equation we have https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

• Is the $q$ you gave the order of the curve or the prime defining the underlying field? – SEJPM Oct 2 '16 at 13:37

Find an integer $k$ such that $65537k \equiv 1 \pmod q$; such a $k$ exists because $q$ is prime.

If $65537\cdot P = H$, then clearly $P = k\cdot H$ (keeping in mind that $q\cdot P = \mathcal{O}$ for all points $P$), and conversely $(k\cdot H)\cdot 65537 = H$.

• For the interested reader: If you have looked for an excuse to get into SAGE, here it is, as elliptic curves are fully supported :) – SEJPM Oct 2 '16 at 13:38
• Dear @fkraiem, based on your answer, $k$ must be equal to $2544954363427735394864394040193014025260293190481810685052829923353728826615$. Now, let $P=k*H$. Using simple computation it is easy to see that $65537*P \ne H$. – Meysam Ghahramani Oct 3 '16 at 10:24
• @MeysamGhahramani Is $q$ not the order of the group we are operating in, as is usual? I am too old to do the actual computations. :D – fkraiem Oct 3 '16 at 11:25
• @fkraiem, Yes, $q$ is the order of group $Z_q$. But in this problem we have two groups. First group is $Z_q$ and second is elliptic curve defined over $Z_q$ with order $\#E$. – Meysam Ghahramani Oct 3 '16 at 12:55

The order of your elliptic curve is:

$$\#E=16503925798136106726026894143294039201930\\439456987742756395524593191976084900.$$

$65537\cdot P=H$ so $P=(65537^{-1} \quad mod \#E)\cdot H$. Therefore $P$ is:

$$(93813596734667685691144143661248488893272149637339517155513405730225\\00973149,126326936796887255657293386261991198154426075402912518061871706759386\\37384365)$$

Note that $q\cdot P=\mathcal{O}$ is not true for all points $P$.

Example: $q=17$, $a=1$, $b=4$ and $P=(0,2)$ then $17\cdot P=(14,5)\ne \mathcal{O}$.