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.

  • 0
    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.2012-02-23

1 Answers 1

1

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 .