9
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ By a "composite field", you mean something like $\mathbb Z/n\mathbb Z$ with $n$ composite? (Those are not fields!) $\endgroup$ – yyyyyyy Jan 24 '17 at 15:21
  • $\begingroup$ 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). $\endgroup$ – 111 Jan 24 '17 at 22:14
  • $\begingroup$ Exactly i mean the same @111 $\endgroup$ – Venkatesh Jan 25 '17 at 6:01
8
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – SEJPM Jan 24 '17 at 12:16
  • $\begingroup$ @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$. $\endgroup$ – CurveEnthusiast Jan 24 '17 at 15:42
  • $\begingroup$ @CurveEnthusiast Please consider "extension field" for "composite" that an elliptic curve is defined over. $\endgroup$ – Vadym Fedyukovych Jan 25 '17 at 9:50
  • 1
    $\begingroup$ @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. $\endgroup$ – CurveEnthusiast Jan 25 '17 at 10:54
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ ${\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. $\endgroup$ – 111 Jan 26 '17 at 12:52
  • $\begingroup$ Thanks for spotting the mistake: I meant "not a field". I've corrected it and (hopefully) added clarification $\endgroup$ – Frédéric Grosshans Jan 26 '17 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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