How to divide 2 coordinates on elliptic curve? [closed]

Question

On the elliptic curves, there is no divide function, and I need divide coordinates - X/Y, o I need not divide but make (X minus or multiply to "modified" Y). How to modify Y?

Answer 1

An elliptic curve as used in cryptography is a finite group, constructed on top a finite field. A pair of elements of the field that obey the curve equation form the Cartesian coordinates of a point of the elliptic curve group (and vice versa for all points of the elliptic curve group, except the neutral / point at infinity, often noted $\infty$).

In the field we can add; subtract; multiply; and divide, except by 0. The result is an element of the field.

In the elliptic curve group we can add and subtract. The result is an element of the elliptic curve group. One such addition involves several operations in the field (with the exception of addition of the neutral).

There is no multiplication in the elliptic curve group: we can't meaningfully multiply two points of an elliptic curve group. We can however define multiplication of an integer $k$ and a point $U$ of an elliptic curve group, by using repeated addition: $$k\times U\,\underset{\text{def}}=\;\begin{cases}\infty&\text{if }k=0\\((k-1)\times U)+U&\text{if }k>0\\(-k)\times(-U)&\text{if }k<0\end{cases}$$

It follows $1\times U=U$, and $2\times U=U+U$.

---

On the elliptic curves, there is no divide function.

That's an oversimplification. We can meaningfully define division of two points of an elliptic curve. $U/V$ can be the lowest non-negative integer $k$ such that $U=k\times V$, when there exists such an integer. For many elliptic curves of cryptographic interest, that operation is defined except when $V=\infty$; but is not efficiently computable for random $U$ or $V$ (that's the very basis of the security of cryptography on that elliptic curve).

---

How to divide 2 coordinates on elliptic curve?

That's just a division in the field, independent of an elliptic curve. How to perform the operation depends on the field.

A common field is $\Bbb F_p$, that is arithmetic modulo a prime $p$. In this field, we can compute $x/y$ (for $y\ne0$):

• as $x\cdot\left(y^{p-2}\right)$, computed modulo $p$. In Python, that's x*pow(y,p-2,p)%p.
• or, more efficiently, as $x\cdot a$, computed modulo $p$, where $a$ is the modular inverse of $y$ computed using the extended Euclidean algorithm. The integer $a$ (and the integer $b$, that we do not need) is found by solving for unknowns $a$, $b$ and givens $y$, $p$ the Bézout identity $a\cdot y+b\cdot p=1$. In Python starting with version 3.8, that's x*pow(y,-1,p)%p.