An x-Coordinate Point Compression Method for Elliptic Curves over Fp

In this paper we propose an $x$-coordinate point compression method for elliptic curves over ${\mathbf F}_p,$ where $p>3$ is prime, as an alternative to the classical $y$-coordinate point compression method. A point $P=(x,y)$ will be compressed as $\tilde{P}=(\tilde{x},y)$ where $\tilde{x}$ has only two bits and, thus, our method allows more compact representations when $\lceil \log_2{x} \rceil > \lceil \log_2{y} \rceil+1 $. Both our compression and decompression algorithms involve solving cubic equations or, in some cases, only computing cube roots modulo a prime, thus being of worst-case complexity ${\cal O}((\log_2{p})^4).$ For some particular cases, our compression algorithm can be significantly improved, requiring only two multiplications (thus, being of worst-case complexity ${\cal O}((\log_2{p})^2)$).