Find the Order of an Elliptic Curve

Question

I have an Elliptic Curve represented by the following equation and values:

Elliptic Curve: y^2 = x^3 + A*x + B mod M

M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030

What is the order of this Elliptic curve?

I thought it should be the same as the modulo, M?

In sage math, if I check the following, I get a different result:

F = FiniteField(M)
E = EllipticCurve(F, [A, B])

E.order() = 93556643250795678718734474880013829509196181230338248789325711173791286325820

However, the value of M is: 93556643250795678718734474880013829509320385402690660619699653921022012489089

These values look similar but they are not the same.

So, I want to know the following:

How is the order of the Elliptic Curve calculated? How is it related to modulus? Since there is a similarity between the two values?

Thanks.

Answer 1

Here is a late answer to this rather sage-related triple question:

• (1) How is the order of the Elliptic Curve calculated? (...in sage i suppose.)
• (2) How is it (the order) related to modulus?
• (3) (...) *a similarity between the two values?

---

Let us re-type the code, so that it comes with printed messages:

M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030
print(f"Is M prime, M = {M}...?\n{M.is_prime()}")

F = GF(M)
print(f"F is {F}")

E = EllipticCurve(F, [A, B])
# print(f"E is {E}")    # please decomment

ord = E.order()
print(f"The order of E is:\n{ord}\nFactorized:\n{ord.factor()}")

The above delivers:

Is M prime, M = 93556643250795678718734474880013829509320385402690660619699653921022012489089...?
True
F is Finite Field of size 93556643250795678718734474880013829509320385402690660619699653921022012489089
The order of E is:
93556643250795678718734474880013829509196181230338248789325711173791286325820
Factorized:
2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569 * 106831998530025000830453 * 1975901744727669147699767

So definitively, ord, the order of the curve, and the prime M, the characteristic of the field of definition for the curve $E$, differ.

---

To have an answer to (2) and (3) in the same time, let us go to:

Hasse's Theorem on Elliptic Curves (wiki page)

The notation $M$ is rather unusual for the prime, which is the characteristic of the base field for the curve. Usually, the notation is $p$ for such a prime, and in case the base field is finite, one denotes by $q$ the number of elements in this field, it is a power of $p$. So in our case, we would expect the relation for the order $\# E(F)$ of the finite group $(E(F),+)$ of points of $E$, ( elliptic curve with affine equation $y^2 = x^3 + Ax + B$, $A,B\in F$), defined over the field $F=\Bbb F_p$ with $p=M$ elements: $$ (p+1)-2\sqrt p\le \# E(F)\le (p+1)+2\sqrt p\ . $$ And indeed:

sage: p = M
sage: bool( (p+1) - 2*sqrt(p) <= ord )
True
sage: bool( (p+1) + 2*sqrt(p) >= ord )
True

To see what happens in a "simple case", let us consider some small prime instead of $p$, for instance $p=11$ (in base ten). We build the list of all elliptic curves of the shape $y^2 = x^3+ax+b$, $a,b\in \Bbb F_{11}$, compute the order, and make a dictionary for which curves appear for which order. We expect cardinalities that differ from $(p+1)=12$ with "tolerance" $\pm 2\sqrt p=\pm2\sqrt{11}\approx 6.633\dots$.

Sage code (given, since it takes less space that the results):

p, F = 11, GF(11)
curves = [EllipticCurve(F, [a, b]) for a in F for b in F if (a/3)^3 + (b/2)^2]
orders = [E.order() for E in curves]
possible_orders = list(set(orders))
possible_orders.sort()

And the possible_orders are:

sage: possible_orders
[6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

and all of them are between the bounds $12\pm6$. Note that any value occurs! To have a quick statistics how the $110$ curves fit in this list of orders...

for ord in possible_orders:
    ord_ab = [(c.a4(), c.a6()) for c, o in zip(curves, orders) if o == ord]
    print(f"ord = {ord:>2} :: {len(ord_ab):>2} curves :: {ord_ab}")

And we get:

ord =  6 ::  5 curves :: [(1, 8), (3, 10), (4, 2), (5, 6), (9, 7)]
ord =  7 ::  5 curves :: [(2, 7), (6, 6), (7, 2), (8, 10), (10, 8)]
ord =  8 :: 10 curves :: [(1, 9), (2, 10), (3, 3), (4, 5), (5, 4), (6, 7), (7, 6), (8, 8), (9, 1), (10, 2)]
ord =  9 :: 10 curves :: [(1, 4), (2, 2), (3, 5), (4, 1), (5, 3), (6, 8), (7, 10), (8, 6), (9, 9), (10, 7)]
ord = 10 :: 10 curves :: [(1, 10), (2, 5), (3, 7), (4, 8), (5, 2), (6, 9), (7, 3), (8, 4), (9, 6), (10, 1)]
ord = 11 ::  5 curves :: [(1, 5), (3, 9), (4, 4), (5, 1), (9, 3)]
ord = 12 :: 20 curves :: [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0), (10, 0)]
ord = 13 ::  5 curves :: [(1, 6), (3, 2), (4, 7), (5, 10), (9, 8)]
ord = 14 :: 10 curves :: [(1, 1), (2, 6), (3, 4), (4, 3), (5, 9), (6, 2), (7, 8), (8, 7), (9, 5), (10, 10)]
ord = 15 :: 10 curves :: [(1, 7), (2, 9), (3, 6), (4, 10), (5, 8), (6, 3), (7, 1), (8, 5), (9, 2), (10, 4)]
ord = 16 :: 10 curves :: [(1, 2), (2, 1), (3, 8), (4, 6), (5, 7), (6, 4), (7, 5), (8, 3), (9, 10), (10, 9)]
ord = 17 ::  5 curves :: [(2, 4), (6, 5), (7, 9), (8, 1), (10, 3)]
ord = 18 ::  5 curves :: [(1, 3), (3, 1), (4, 9), (5, 5), (9, 4)]

For short, the values of characteristic $p$ (in the OP $M$) of the base field $F=\Bbb F_p$ of the elliptic curve $E$, and the order of the group of its $F$-rational points $E(F)$, do not coincide, all we know in this generality is the double inequality (Hasse).

I can't to the same for $M$, but there are $M^2$ equations (and $M^2$ is huge) of the shape $y^2=x^3 +ax+b$ that can be written in characteristic $M$, some of them are leading to singular curves, (well, $\# F_M^\times =(M-1)$ is not a multiple of $3$, so $a\to a^3$ is injective, so for each $b$ there exists exactly one $a$ leading to a zero discriminant, so there are exactly $M$ singular curves...) but "a lot of them" are non-singular, thus elliptic, and they will fit somehow into the "small range" of possible orders between the two bounds $(M+1)\pm 2\sqrt M$. The curve from the OP is one of them...

---

First question, (1) How does sage compute the order?

Well, we have to look into the code. This can be done for instance by having an instance of the class defining the method order, and asking for...

sage: E.order??

we get a lot of information...

Signature: E.order(algorithm=None, extension_degree=1)
Docstring:
   Return the number of points on this elliptic curve.

   INPUT:

   * "algorithm" -- (optional) string:

     * "'pari'" -- use the PARI C-library function "ellcard".

     * "'bsgs'" -- use the baby-step giant-step method as
          implemented in Sage, with the Cremona-Sutherland version of
          Mestre's trick.

     * "'exhaustive'" -- naive point counting.

     * "'subfield'" -- reduce to a smaller field, provided that the
       j-invariant lies in a subfield.

     * "'all'" -- compute cardinality with both "'pari'" and "'bsgs'";
       return result if they agree or raise a "AssertionError" if they
       do not

and so on, many, many doc string lines. We get then same information for the delegated work, this is the method E.cardinality, and we can immediately put the hands on the relevant piece of code:

try:
    return self._order
except AttributeError:
    pass

jpol = None
if algorithm is None:
    # Check for j in subfield
    jpol = self.j_invariant().minimal_polynomial()
    if jpol.degree() < self.base_field().degree():
        algorithm = "subfield"
    else:
        algorithm = "pari"

if algorithm == "pari":
    N = self.cardinality_pari()
elif algorithm == "subfield":
    if jpol is None:
        jpol = self.j_invariant().minimal_polynomial()
    N = self._cardinality_subfield(jpol)
elif algorithm == "bsgs":
    N = self.cardinality_bsgs()
elif algorithm == "exhaustive":
    N = self.cardinality_exhaustive()
elif algorithm == "all":
    N = self.cardinality_pari()
    N2 = self.cardinality_bsgs()
    if N != N2:
        raise AssertionError("cardinality with pari=%s but with bsgs=%s" % (N, N2))
else:
    raise ValueError("algorithm {!r} is not known".format(algorithm))

self._order = N
return N

So the computation is...

• if we have already computed the ordered (in the same sage session), then it is cached, i.e. stored in the attribute _order. If this attribute is set, we deliver it. Not the case in the OP.

• then we check if the subfield algorithm should be used, this makes sense for "bigger fields" $\Bbb F_q$ with prime field $\Bbb F_p$ (so $q$ is a power of the characteristic $p$), and can be applied iff the $j$-invariant lives in a (strict) subfield of $\Bbb F_q$. Not the case in the OP. (We already work over the prime field.) So the code decides to use the algoritm = "pari".

• and this delegates the work to the computation of the order N = self.cardinality_pari(). So the true work goes to this method, and the only line of code in it is

    return Integer(self.__pari__().ellcard())
  

So sage uses the pari/gp associated object, from it the method ellcard. It is as if we would require instead:

sage: Integer( E.__pari__().ellcard() )
93556643250795678718734474880013829509196181230338248789325711173791286325820

---

Note: Using the "other algorithms" (implemented in E.order) we get the same value. Code for them can be also inspected, this is the advantage of open source.

sage: E.order(algorithm='pari')
93556643250795678718734474880013829509196181230338248789325711173791286325820
sage: E.order(algorithm='bsgs')
93556643250795678718734474880013829509196181230338248789325711173791286325820
sage: E.order(algorithm='subfield')
93556643250795678718734474880013829509196181230338248789325711173791286325820
sage: # E.order(algorithm='exhaustive')    # well, please not in this case...
sage: E.order(algorithm='all')
93556643250795678718734474880013829509196181230338248789325711173791286325820