1
$\begingroup$

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?

$\endgroup$
17
  • $\begingroup$ Using conventional notation, you can't multiply or divide points on an elliptic curve. Can you explain more on what you want to do? $\endgroup$ – Aman Grewal Jul 28 '20 at 21:24
  • $\begingroup$ I Thant get Z = X/Y , I need inversion of Y and add after this inversed Y $\endgroup$ – Donald Jul 28 '20 at 21:26
  • $\begingroup$ Yes Kalalaka, and what formula for inverse this Y element ? And what I need to do after with Y Add this inversed Y or subtract Y from X for get X/Y ? $\endgroup$ – Donald Jul 28 '20 at 21:29
  • $\begingroup$ You are professionals I hope you understand what I talk about. $\endgroup$ – Donald Jul 28 '20 at 21:36
  • $\begingroup$ You can use the Extended_GCD to find the inverse. Your question is not clear. You should write something like this. Given a point P=(x,y) in affine coordinates how can I found $Q=(x/z,y/t)$. I'm pretty sure there were similar questions around here that people don't understand /Y infinite fileds. It is just $Y^{-1}$. $\endgroup$ – kelalaka Jul 28 '20 at 21:36
4
$\begingroup$

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.
$\endgroup$

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