# Is an elliptic curve over $\mathbb{F}_p$ order preserving for the points $(x,y) \in \mathbb{Z}_p$?

Let $E\colon y^2=x^3+ax+b$ be an elliptic curve, and consider its realisation over the finite field of prime order $p$: $E(\mathbb{F}_{p})$.

Then if $0<a,b$ is the following true?

$$\forall x,y\in[0,p) \text{ s.t. }E(x)=y \text{ : }(x_i<x_j)\implies E(x_i)<E(x_j)$$

-
I doubt they're order-preserving in the strict sense, because you'd eventually get reduced modulo $p$ if $y$ is too big. It might meet a related definition presented in Boldyreva's second paper on OPE where modular order preservation is the goal. I don't have it on hand but I'll try to dig up specifics and post them in another comment. –  pg1989 Dec 5 '13 at 9:25
I assume that x,y are always smaller than the modulo –  curious Dec 5 '13 at 9:34
Is that a justifiable assumption, though? Doesn't it depend greatly on the choice of $a$, $b$, and $p$? –  pg1989 Dec 5 '13 at 9:38
sorry i assume there are always positive. –  curious Dec 5 '13 at 9:39
Could you define what you mean by $E(x)=y$? If $E$ is the curve, then $E(x)$ is not well-defined. Do you mean $x,y$ such that $(x,y)$ is on the curve (i.e., $y^2=x^3+ax+b \pmod p$)? –  D.W. Dec 6 '13 at 1:45

The question as currently stated is true if we assume the equation takes place in $\mathbb{Z}$, since all the values are small integers.

Proof: If $x<x'$, then $x^3<(x')^3$ and $ax<ax'$, so $$E(x)= x^3 +ax+b < (x')^3 +ax'+b = E(x')$$

The problem with trying to answer the more general issue you appear to be considering is working out what it means to say $x<y$ for $x,y\in\mathbb{F}_p$. There isn't a reasonable ordering on elements of a finite field, or indeed on $\mathbb{Z}/p\mathbb{Z}$. Intuitively, one might wish that $x<y$ if and only if $x<y$ when considered as integers. However, this doesn't work because there is no mapping that will respect the required properties. Consider the following [attempt] at defining this:

For any $x\in\mathbb{Z}$, let $\bar{x}$ denote the image of $x$ under the projection into $\mathbb{F_p}$. Then,[try to] define an ordering $\prec$ on $\mathbb{F}_p$ by $\bar{x}\prec\bar{y}\iff x<y$.

The biggest problem with this is that it isn't even well defined. For example, let $a,b\in\mathbb{F}_7$, with $a=\bar{3}$ and $b=\bar{6}$. Then since $3<6$ we deduce $a\prec b$, but since $a=\bar{3}=\bar{10}$ we must also have $b\prec a$ (since $6<10$). This would imply $a=b$, which is clearly false.