TLDR: If we specialize a generator point $G$ of an Elliptic Curve group of prime order, we can consistently define the GCD of two points for that generator. But we can't efficiently find it for arbitrary points and a group of cryptographic interest, where the Discrete Logarithm Problem is hard.
Before finding something, we must know what it is. Hence poncho's sub-question:
What would 'the GCD of two points on a prime curve' mean?
GCD stands for Greatest Common Divisor. Thus we need to define three notions
- What a "prime curve" is. In this, curve stands for Elliptic Curve. And prime is a property of either
- the base finite field's order (that prime order is often noted $p$, and then the field is simply the integers modulo $p$);
- the curve's order, that is how many elements in the finite group of points of the curve, including the neutral;
- or the order of a subgroup of the curve (then often noted $n$, as we'll do).
- The notion of "divisor" of a point of a prime elliptic curve, which we'll assume is a point of the elliptic curve with some property to be defined.
- The notion of "greatest" among points of an elliptic curve.
We can define such things consistently! We posit that a "prime curve" is some subgroup of prime order $n$ of an elliptic curve (perhaps the whole curve, which can use a prime field; e.g. secp256k1, secp256r1), and $G$ a given point of the curve / an element of the group, other than the neutral. Now the set of $n$ integers in $[0,n)$ is isomorphic to the curve, by the trivial isomorphism $i\mapsto i\,G$ defined as usual: $0\,G$ is the group's neutral, $i\,G$ is $((i-1)\,G)+G$ for any $i\in[1,n)$ with $+$ the group's law.
We can define "divisor" and "greatest" on the set $[0,n)$. And we can define the GCD of two elements of that set (together with the somewhat arbitrary $\gcd(0,0)=0$ ). Then we can use this isomorphism to define the Greatest Common Divisor of two points of an Elliptic Curve Group of prime order provided with a generator point $G$.
In other words, I define the GCD of points $P$ and $Q$ as the point which matching private key (for generator $G$) is the GCD of the private keys matching $P$ and $Q$, with matching private key an integer in $[0,n)$.
If we can efficiently solve the Discrete Logarithm Problem in the group considered, then we can efficiently compute the GCD (we solve two DLP, compute the GCD of the integers, and get back to the curve).
Update: the converse is true to some degree. If we can efficiently compute the GCD of any two points $P$ and $Q$, then we can use that algorithm to efficiently compute the Discrete Logarithm $i$ of any $P$. Sketch: we select the first primes $r_j$ until $n<\prod r_j$, and for each $j$ we find $i\bmod r_j$ by asking for the GCD of $(P+k\,G,r_j\,G)$ which is either $G$ or $r_j\,G$, in the later case revealing that $i+k\equiv0\pmod{r_j}$. Then we find $i$ by the Chinese Remainder Theorem. Optimizations are possible to group a sizable number of queries into one. E.g. submits $(P+k\,G,30\,G)$ and tests if the result is $G$, $2\,G$, $3\,G$, $5\,G$, $6\,G$, $10\,G$, $15\,G$ or $30\,G$. Further reductions are possible by computing the discrete logarithm of the oracle's output using variants of Baby-Step/Giant-Step.
I don't know any application, in cryptography or otherwise.
