Decoding a message on elliptic curve Let's say I have an elliptic curve $E$ $y^2=x^3 + 486662x^2 + x$ over a prime field $GF(2^{255} - 19)$. My algorithm for computing $E(m)$ is as follows:

I take the bits 1 through 32 of the message and plug that for $x$ in the equation.

I then calculate the result, store it as $x$,

and calculate the sign of $y$ using the first bit of $m$.
Let $e$ be the encryption key, then we can set the encrypted value of $m$ equal to $$Enc(m) = E(m)^e.$$


My question is how can I decode the message if I know the encryption key? Is it always possible?
if your $e$ is coprime to $p-1$ where $p=2^{255}-19$ you can calculate the $e$-th of an integer modulo $p$ which means you can recover $E(m)$ given $E(m)^e$. In fact, if the condition holds, there exist $u,v \in \mathbb{Z}$ such that $eu+(p-1)v=1$ (Bezout's identity). Now, we are looking for an integer $x$ such that $x \equiv a^{1/e} \pmod p$ i.e. $x^e \equiv a \pmod p$. It is easy to find it: $a^u \equiv x^{eu} \equiv x^{1-(p-1)v} \equiv x\times (x^{p-1})^{(-v)}\equiv x \pmod p$ because $x^{p-1} \equiv 1 \pmod p$ according to Fermat's little theorem.