Difficulty of Reversing Elliptic Curve
On an elliptic curve as used in crypto, we can add any two points $P$ and $Q$ of the elliptic curve, yielding a new point of the elliptic curve: $X\gets P+Q$. It holds $(P+Q)+R=P+(Q+R)$, making $P+Q+R$ unambiguous.

For any integer $k&gt;0$ and point $P$, that lets us define $k$ times $P$, noted e.g. $k\times P$, as the result obtained by adding $k$ copies of $P$, that is $k\times P\;\underset{\text{def}}=\;\underbrace{P+\ldots+P}_{k\text{ times}}$

We can efficiently compute $k\times P$ per the following (recursive) method:


if $k=1$ then return $P$
otherwise, if $k$ is even, compute $Q=(k/2)\times P$ and return $Q+Q$
otherwise, compute $Q=(k-1)\times P$ and return $Q+P$


This efficient computation method for $k\times P$ takes time proportional to the number of bits in $k$, whereas applying the definition would take time proportional to $k$. The $k$ used in crypto are often about $2^{256}$, which is many times the conjectured number of atoms in the universe, but the computation still takes a fraction of a second with the efficient method.

Now, consider the problem of finding $k&gt;0$ such that $Q=k\times P$, given $P$ and $Q$. A basic method is to start from $P$ and, while $Q$ is not reached, add $P$. The desired $k$ is one more than the number of additions made. Problem is, that takes time proportional to $k$.

We know better methods that take time proportional to $\sqrt k$. The main ones are baby step/giant step¹ and Pollard's rho². But when $k$ is about $2^{256}$, $\sqrt k$ is about $2^{128}$, and we can't even count to that number: collectively, all the computing devices ever made by man did not count to that, much less made that number of elliptic curve operations.

We know³ no better method than those requiring time proportional to $\sqrt k$, and that explains the difficulty of reversing multiplication on an elliptic curve with the parameters used in cryptography.



Extra meat for thought:

¹ Baby step/giant step works as follows:


chose an $l$ large enough that we'll have $k\le l^2$
store the point $Q_0\gets Q$
for $i$ from $1$ to $l-1$


compute and store the point $Q_i\gets Q_{i-1}+P$ (these are the baby steps)

compute the point $R\gets l\times P$
initialize the point $S\gets R$
for $j$ from $1$ to $l$


search $S$ among the $Q_i$ (this can be done without scanning all the $Q_i$, much like we can find a book in a library), and if there's a match


compute and output $k\gets j\,l-i$, done!

update the point $S\gets S+R$ (these are the giant steps)



² Pollard's rho replaces the systematic search of baby step/giant step¹ by a pseudo-random walk, and replaces the impractically large array $Q_i$ by a detection that the walk goes along an already explored path. The point where the paths merge yields the solution.

³ Q: But why can't we find a better method, when we have efficient methods to solve the similar problem of finding $k&gt;0$ such that $v=k\times u$ given ordinary integers $u$ and $v$ ? $k$ is the quotient of $v$ divided by $u$ in Euclidean division, and that's feasible for numbers with million bits.
A: Euclidean division relies on comparing integers and finding the smallest, for a definition of smallest compatible with addition, in the sense that if $a&lt;b$, then $a+b&lt;a+c$. But there can't be any such notion of order on a large but finite set like an elliptic curve as used in crypto, hence Euclidean division won't cut it⁴.

⁴ Q: But that argument does not hold water! We have efficient methods to solve the similar problem of finding $k&gt;0$ such that $v=k\times u$ given $u$ and $v$ when working in some large but finite sets. For example, in arithmetic modulo $p$, there's a systematic method published in 1621 by Bachet, using an extension of the so-called Euclidean algorithm, which uses Euclidean division.
A: This does not cut it either, but for a different reason: in arithmetic modulo $p$ and all cases where similar methods are known, it is relied not only on addition of elements $a$, $b$, $c$ of the set, but also on multiplying them in a way compatible with the premise that $a\,(b+c)=a\,b+a\,c$ . When in elliptic curve arithmetic we can add points, but not meaningfully multiply them together.