2
$\begingroup$

Are there any elliptic curves, that require computing GCD for point addition? I've an algorithm, that apparently adds two points on an elliptic curve, but it uses GCD, which is strange, because I never saw it being used for addition on any kind of curve.

Are there any formulas for point operations on EC that involve GCD, or perhaps are sped up by using GCD?

By GCD I also mean extended GCD.

$\endgroup$
  • 1
    $\begingroup$ Are these elliptic curves over $\mathbb F_p$? Extended gcd is commonly used to find modular reciprocals. $\endgroup$ – Henning Makholm Sep 9 '11 at 14:59
  • $\begingroup$ Curve is over polynomials with coefficients modulo a prime. For example, x coord. of result is divided by gcd, so it isn't used just for reciprocals. $\endgroup$ – ted.k Sep 9 '11 at 15:24
  • 1
    $\begingroup$ Could it be a step intended to simplify projective coordinates of a point? $\endgroup$ – Jyrki Lahtonen Sep 10 '11 at 20:24
  • $\begingroup$ The group law on primitive integer points of $x^2 - d y^2 = 4 z^3$ uses $\gcd$. Some elliptic curves are on this surface but their group laws don't coincide. $\endgroup$ – Samuel Hambleton Feb 23 '12 at 23:46
1
$\begingroup$

Yes, there is some procedure. As far as my knowledge is concerned, I think one can use G.C.D, to add points, I don't know about its efficiency ( but the prerequisite is that one needs to consider an elliptic curve over a finite field ).

Let me tell an example, fix an elliptic curve over a finite field say $\mathbb{Z}/m\mathbb{Z}$. Now consider two points $P$ and $Q$ on it. So adding two points essentially involves the standard formula that require something called "Slope" ( I assume OP knows the formula, and he can have a look here, otherwise (where $s$ is the slope considered in wikipedia context ) ). If you see in reality they involve divisions between residue classes modulo $n$, which can be performed using the extended Euclidean algorithm which is here. In particular, division by some $\rm{v\ (mod \ n)}$ includes the calculation of the greatest common divisor $\rm{gcd}(v,n)$.

In addition If the slope is of the form $\large \frac{u}{v}$ with $\rm gcd(u,n)=1$, then $v=0 \ (mod \ n) $means that the result of the $\oplus$-addition will be , the point at infinity on the curve. However, if $\rm{gcd(v,n)}$ is neither $1$ nor $n$, then the $\oplus$-addition will not produce a meaningful point on the curve, which shows that our elliptic curve is not a group $(mod \ n)$, but, more importantly for now, $\rm gcd(v,n)$ is a non-trivial factor of $n$.

Thank you .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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