# Why are elliptic curves constructed using prime fields and not composite fields?

I come across this:

Numbers mod composite number does not form a field rather it forms a ring

and

every number has a multiplicative inverse under integer mod prime

Maybe these are the reasons why prime field is preferred? By the first above fact it means that construction of a composite field is not possible. But I have seen some research articles about multiplication algorithm using composite fields…

Why are elliptic curves constructed using prime fields and not composite fields?

• By a "composite field", you mean something like $\mathbb Z/n\mathbb Z$ with $n$ composite? (Those are not fields!) – yyyyyyy Jan 24 '17 at 15:21
• define composite field. From what you wrote it seems that (as yyyyyyy noticed) that by composite field you mean something like Z_n with n composite. Elliptic curves can be defined over a field (finite,p-adic,Q,R,C). – 111 Jan 24 '17 at 22:14
• Exactly i mean the same @111 – Venkatesh Jan 25 '17 at 6:01

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{GF}(p^n)$, but they are constructed differently. For $n\ge2$, they are commonly called extension fields (as opposed to prime fields for $n=1$), as they can be viewed as extensions of $\mathbb{F}_p$.

There are examples of elliptic curves over extension fields. For example, every cryptographically secure curve in characteristic two is defined over a field of the form $\mathbb{F}_{2^m}$, i.e. a field with $2^m$ elements. There is also the Four$\mathbb{Q}$ curve, which is defined over $\mathbb{F}_{p^2}$ where $p=2^{127}-1$.

Doing things over extension fields can get a bit more tricky. There are attacks which can exploit the fact that $n\ge2$, which lead to faster algorithms for the discrete logarithm problem, on which elliptic-curve crypto is built. This gets complex pretty quickly, but some of it is explained in Galbraith's book (see $\S15.7$ and $\S15.8$). These attacks do not apply to every curve over an extension field, but show that you'll have to be more careful.

• For the uninitiated: If you have some $x\in \mathbb Z/n\mathbb Z$ (ie "Numbers mod n") with $\gcd(x,n)>1$ and $x<n$ then $x$ doesn't have an inverse which violates one of the axioms ("basic requirements") for fields. – SEJPM Jan 24 '17 at 12:16
• @SEJPM Thanks for the addition! I would even say it violates the axiom for fields, in the sense that a ring is (by definition) a field if and only if every non-zero element has an inverse. And $\mathbb{Z}/n\mathbb{Z}$ is a ring for every $n$. – CurveEnthusiast Jan 24 '17 at 15:42
• @CurveEnthusiast Please consider "extension field" for "composite" that an elliptic curve is defined over. – Vadym Fedyukovych Jan 25 '17 at 9:50
• @VadymFedyukovych You are right that it is better to use the correct terminology. I tried not to confuse the questioner too much by introducing new terms, but have now edited it anyway. – CurveEnthusiast Jan 25 '17 at 10:54

To complete the other answer, one can note that elliptic curves over the $\mathbb{Z}/n\mathbb{Z}$ ring for non-prime $n$ are at the heart of Lenstra elliptic curve factorization, so such elliptic curves are not totally useless. However, this is not really a counterexample, since the algorithm works by looking for points of the curves which cannot be added, showing that this elliptic curve is not a group. It is not a group because $\mathbb{Z}/n\mathbb{Z}$ is not a field if $n$ is not prime, and actually these points give a nontrivial factorization of $n$.

If you want your elliptic curve to define a group, you need to define it over a a field. When defined over a ring which is not a field, like $ℤ/nℤ$ for composite $n$, where inverses do not exist when $\gcd (k,n)\neq1$, an elliptic curve is not a group, and there are some points which cannot even be added. This of course problematic for most applications, but this very failure to define a group can be used to reveal some information on the structure of the ring itself.

• ${\bf Z}/n{\bf Z}$ is a ring but not a group? Is a commutative ring ==> is a group under addition $\mod n$, but not multiplicative group since $n$ is not prime. – 111 Jan 26 '17 at 12:52
• Thanks for spotting the mistake: I meant "not a field". I've corrected it and (hopefully) added clarification – Frédéric Grosshans Jan 26 '17 at 17:02