Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$$

share|improve this question
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.

For more information, this wikipedia page might help.

share|improve this answer
@downvote: What can I do to improve this answer? A downvote without explanation isn't helpful :( – figlesquidge Dec 6 '13 at 11:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.