# Mapping points between elliptic curves and the integers

My primary question is:

• Is there an easy way to create a bijective mapping from points on an elliptic curve E (over a finite field) to the integers (desirably to $\mathbb{Z}^*_q$ where $q$ is the order of E)?

To phrase it a second way, given a point on the curve that is chosen with uniform randomness, can you translate it into a uniformly random integer in some interval (or group)? I'm also interested in mappings that are statistically close to uniform.

(I thought of using a random extractor, but this generally requires 2m bits of min-entropy in the input to produce m bits of near-uniform randomness)

I was reminded of this question when reading the Telex paper, where they encounter this issue. Their solution is to use two specially selected curves, a curve and its twist, and only map the x-coordinate.

Secondary questions:

• Using a curve and twist, is there a way to use the y-coordinate to select which curve so that the mapping is one-to-one?
• If there is an approach, does it also work with pairing-friendly curves?
• You mean to ask for a mapping that is easy to calculate in both directions, right? $F(x)=xG$, where $G$ is a generator point and $0 <= x < order(E)$, is bijective but it's only easily calculated in one direction. Mar 11, 2014 at 23:09
• Isn't this the whole premise of Elligator and, more generally, Elligator-Squared? When the curve meets specific criteria the mapping is complete, notably when q mod 4 = 1.
– DBM
Jul 11, 2015 at 2:36

I do not know of any general way to create the mapping you want (and if there was, it might turn into an efficient point-counting algorithm, which would be great), but you can do this on some curves.

Consider a prime $p$ equal to $2$ modulo $3$. In $\mathbb{Z}_p$, every value has a single cube root (because $3$ is then invertible modulo $p-1$). Then, look at the curve $y^2 = x^3+1$. For any value of $y$, $y^2-1$ has a unique cube root $x$, so there is a one-to-one mapping between non-infinity points on that curve and their $y$ coordinate in $\mathbb{Z}_p$. For completeness, map the "point at infinity" to the integer $p$, and you are all set: an easy bijective mapping between the $p+1$ curve elements, and the integers modulo $p+1$.

Moreover, this curve is pairing-friendly, with an embedding degree of only $2$ (because $p+1$ divides $p^2-1$). It also allows a distortion map so that you can have a symmetric pairing: if $\mu$ is a cubic root of $1$ distinct from $1$ (so an element of $GF(p^2)$, the field extension), then the mapping $m$ from $(x,y)$ to $(\mu x,y)$ is a morphism over the curve. Then you can define a pairing $e(P, Q)$, where $P$ and $Q$ are both points on the original curve (in $\mathbb{Z}_p$) as the Tate (or Weil) pairing computed over $P$ and $m(Q)$. This allows you to stay on the base curve as much as possible; only the pairing output will need the field extension.

Ben Lynn shows some details in his PhD dissertation (he calls that curve a "type B"). Note that since there is a pairing of embedded degree $2$, then discrete logarithm on the curve is "reduced" to discrete logarithm in the $GF(p^2)$ field; so, for proper security, $p$ must be at least 512-bit long.

Edit: A similar trick works for "type A" curves with equation $y^2 = x^3 + ax$ in $\mathbb{Z}_p$ for $p = 3 \mod 4$ and a constant $a$. For a given $x$, then exactly one of the three following situations occurs:

• There are two distinct values $y$ such that $(x, y)$ is a valid point, and they are opposite of each other, so one is lower than $p/2$ and one is greater.

• There is no valid $(x, y)$ point, but there are two valid $(-x, y)$ points for two distinct values of $y$.

• $(x, 0)$ is a valid point, and so is $(-x, 0)$ (this one can happen only if $-a$ is a square modulo $p$).

So you can map the point $(x, y)$ to:

• $x$ if $1\leq y \lt p/2$
• $-x$ if $p/2 \lt y \lt p$
• $x$ if $y = 0$

Then map the point of infinity to $p$, and you're done.

• Thanks! This is useful. Hopefully accepting this answer won't discourage other answers for other types of curves (e.g. ones that are not supersingular—Telex for example relies on DDH.) Aug 4, 2011 at 1:04
• This is probably a silly question, but doesn't regular point compression almost do this? Granted, the output is not in $Z_p$, but it's guaranteed to be in $Z/(2p+1)Z$. Sep 9, 2011 at 16:53
• @Samuel: Point compression is not bijective: from a point $(x, y)$, you get $(x, b)$ where $b$ is a single bit, but not all pairs $(x, b)$ are the compression of a valid curve point. The difficulty in this question is to have a mapping to modular integers where every modular integer value can be mapped back. Sep 9, 2011 at 19:13