Hashing to elliptic curves over highly $2$-adic fields $\mathbb{F}_{\!q}$ with $O(\log(q))$ operations in $\mathbb{F}_{\!q}$

ePrint Report: Hashing to elliptic curves over highly $2$-adic fields $\mathbb{F}_{\!q}$ with $O(\log(q))$ operations in $\mathbb{F}_{\!q}$

Dmitrii Koshelev

The current article provides a new deterministic hash function $\mathcal{H}$ to almost any elliptic curve $E$ over a finite field $\mathbb{F}_{\!q}$, having an $\mathbb{F}_{\!q}$-isogeny of degree $3$. Since $\mathcal{H}$ just has to compute a certain Lucas sequence element, its complexity always equals $O(\log(q))$ operations in $\mathbb{F}_{\!q}$ with a small constant hidden in $O$. In comparison, whenever $q \equiv 1 \ (\mathrm{mod} \ …

article complexity compute current elliptic eprint report function hash hash function hashing log operations report