Finding elliptic curves achieving the upper and lower bounds of Hasse's Interval

Question

I always thought that Hasse's bound is sharp (at least for elliptic curves). In other words I always thought that given a prime number $p$, I can find two elliptic curves $E_1,E_2$ over $\mathbb F_p$ such that $\#E_1 = \lceil 1+p-2\sqrt p \rceil$ and $\#E_2 = \lfloor 1+p+2\sqrt p\rfloor$. But is this even true? If so, is there an easy way to construct these curves? I've seen the proof of how to obtain these bounds but I don't think it gives me any information on the sharpness of the bound.

Answer 1

This is only a very partial answer, reflects only what i would do for a given rather small prime $p$. The character of the answer is experimental. The method is exhaustive enumeration. So for a small $p$ we may use computer assistance, below sage, to validate or invalidate the claim.

Consider first $p=7$. Then the following code:

def orderStatisticForEC(p):
    F = GF(p)
    orders_dic = {}
    for a in F:
        for b in F:
            try:
                E = EllipticCurve(F, [a, b])
                ord = E.order()
                if ord in orders_dic:
                    orders_dic[ord].append((a, b))
                else:
                    orders_dic[ord] = [(a, b)]
            except Exception:
                pass    # singular curve
    orders = orders_dic.keys()
    orders.sort()
    h1, h2 = p - 2*sqrt(p) + 1, p + 2*sqrt(p) + 1
    z1, z2 = ZZ(h1.n().ceil()), ZZ(h2.n().floor())
    print "Hasse interval ~ [ {} , {} ]".format(h1.n(), h2.n())
    print "Hasse orders in  [ {} , {} ]".format(z1, z2)

    print "Statistic of orders:"
    for order in orders:
        print "Order {:3} for {}".format(order, orders_dic[order])

orderStatisticForEC(7)

delivers the symmetric (w.r.t $p+1=8$) statistic:

Hasse interval ~ [ 2.70849737787082 , 13.2915026221292 ]
Hasse orders in  [ 3 , 13 ]
Statistic of orders:
Order   3 for [(0, 4)]
Order   4 for [(0, 6), (3, 6), (5, 6), (6, 6)]
Order   5 for [(1, 1), (2, 1), (4, 1)]
Order   6 for [(1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3)]
Order   7 for [(0, 5), (3, 5), (5, 5), (6, 5)]
Order   8 for [(1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0)]
Order   9 for [(0, 2), (3, 2), (5, 2), (6, 2)]
Order  10 for [(1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4)]
Order  11 for [(1, 6), (2, 6), (4, 6)]
Order  12 for [(0, 1), (3, 1), (5, 1), (6, 1)]
Order  13 for [(0, 3)]

and the question wants a way to detect the two elliptic curves $y^2=x^3+4$ and $y^2=x^3+3$ that attain the bounds.

For $p=11$ we have maybe the last printable case:

sage: orderStatisticForEC(11)
Hasse interval ~ [ 5.36675041928920 , 18.6332495807108 ]
Hasse orders in  [ 6 , 18 ]
Statistic of orders:
Order   6 for [(1, 8), (3, 10), (4, 2), (5, 6), (9, 7)]
Order   7 for [(2, 7), (6, 6), (7, 2), (8, 10), (10, 8)]
Order   8 for [(1, 9), (2, 10), (3, 3), (4, 5), (5, 4), (6, 7), (7, 6), (8, 8), (9, 1), (10, 2)]
Order   9 for [(1, 4), (2, 2), (3, 5), (4, 1), (5, 3), (6, 8), (7, 10), (8, 6), (9, 9), (10, 7)]
Order  10 for [(1, 10), (2, 5), (3, 7), (4, 8), (5, 2), (6, 9), (7, 3), (8, 4), (9, 6), (10, 1)]
Order  11 for [(1, 5), (3, 9), (4, 4), (5, 1), (9, 3)]
Order  12 for [(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)]
Order  13 for [(1, 6), (3, 2), (4, 7), (5, 10), (9, 8)]
Order  14 for [(1, 1), (2, 6), (3, 4), (4, 3), (5, 9), (6, 2), (7, 8), (8, 7), (9, 5), (10, 10)]
Order  15 for [(1, 7), (2, 9), (3, 6), (4, 10), (5, 8), (6, 3), (7, 1), (8, 5), (9, 2), (10, 4)]
Order  16 for [(1, 2), (2, 1), (3, 8), (4, 6), (5, 7), (6, 4), (7, 5), (8, 3), (9, 10), (10, 9)]
Order  17 for [(2, 4), (6, 5), (7, 9), (8, 1), (10, 3)]
Order  18 for [(1, 3), (3, 1), (4, 9), (5, 5), (9, 4)]

I do not see a constructive method that hits with precision one of the values $(a,b)$ for minimal order $6$ and/or maximal order $18$.

Note that we have the following pairs of quadratic twists:

sage: for a, b in [(1, 8), (3, 10), (4, 2), (5, 6), (9, 7)]:
....:     E = EllipticCurve(GF(11), [a, b])
....:     print E, '\n', E.quadratic_twist(), '\n'
....:     
Elliptic Curve defined by y^2 = x^3 + x + 8 over Finite Field of size 11 
Elliptic Curve defined by y^2 = x^3 + 4*x + 9 over Finite Field of size 11 

Elliptic Curve defined by y^2 = x^3 + 3*x + 10 over Finite Field of size 11 
Elliptic Curve defined by y^2 = x^3 + x + 3 over Finite Field of size 11 

Elliptic Curve defined by y^2 = x^3 + 4*x + 2 over Finite Field of size 11 
Elliptic Curve defined by y^2 = x^3 + 9*x + 4 over Finite Field of size 11 

Elliptic Curve defined by y^2 = x^3 + 5*x + 6 over Finite Field of size 11 
Elliptic Curve defined by y^2 = x^3 + 9*x + 4 over Finite Field of size 11 

Elliptic Curve defined by y^2 = x^3 + 9*x + 7 over Finite Field of size 11 
Elliptic Curve defined by y^2 = x^3 + 5*x + 5 over Finite Field of size 11 

So let us consider only curves that realize the "floored maximal Hasse bound" for some small primes. New code...

sage: for p in primes(5, 100):
....:     max_order = ZZ( floor( (p + 1 + 2*sqrt(p)).n() ) )
....:     F = GF(p)
....:     ab_list = []    # so far, but we append soon 
....:     for a, b in cartesian_product( [F, F] ):
....:         try:
....:             E = EllipticCurve(F, [a,b] )
....:             if E.order() == max_order:
....:                 ab_list.append((a,b))
....:         except:
....:             pass    # singular curve
....:     print( "p = %3s :: order = %s :: %s solutions, first five are %s"
....:            % (p, max_order, len(ab_list), ab_list[:5]) )
....:     
p =   5 :: order = 10 :: 1 solutions, first five are [(3, 0)]
p =   7 :: order = 13 :: 1 solutions, first five are [(0, 3)]
p =  11 :: order = 18 :: 5 solutions, first five are [(1, 3), (3, 1), (4, 9), (5, 5), (9, 4)]
p =  13 :: order = 21 :: 2 solutions, first five are [(0, 4), (0, 9)]
p =  17 :: order = 26 :: 4 solutions, first five are [(3, 0), (5, 0), (12, 0), (14, 0)]
p =  19 :: order = 28 :: 12 solutions, first five are [(0, 8), (0, 12), (0, 18), (1, 17), (4, 16)]
p =  23 :: order = 33 :: 11 solutions, first five are [(1, 11), (2, 5), (3, 22), (4, 19), (6, 10)]
p =  29 :: order = 40 :: 21 solutions, first five are [(4, 0), (5, 0), (6, 0), (8, 2), (8, 27)]
p =  31 :: order = 43 :: 5 solutions, first five are [(0, 3), (0, 6), (0, 12), (0, 17), (0, 24)]
p =  37 :: order = 50 :: 9 solutions, first five are [(2, 0), (14, 0), (15, 0), (18, 0), (20, 0)]
p =  41 :: order = 54 :: 40 solutions, first five are [(2, 4), (2, 37), (5, 2), (5, 39), (6, 5)]
p =  43 :: order = 57 :: 7 solutions, first five are [(0, 9), (0, 13), (0, 14), (0, 15), (0, 17)]
p =  47 :: order = 61 :: 23 solutions, first five are [(1, 38), (2, 15), (3, 5), (4, 22), (6, 23)]
p =  53 :: order = 68 :: 39 solutions, first five are [(1, 0), (4, 10), (4, 43), (6, 24), (6, 29)]
p =  59 :: order = 75 :: 29 solutions, first five are [(2, 22), (6, 41), (8, 1), (10, 5), (11, 16)]
p =  61 :: order = 77 :: 30 solutions, first five are [(6, 29), (6, 32), (8, 30), (8, 31), (10, 30)]
p =  67 :: order = 84 :: 44 solutions, first five are [(0, 1), (0, 9), (0, 14), (0, 15), (0, 22)]
p =  71 :: order = 88 :: 70 solutions, first five are [(1, 9), (2, 3), (3, 25), (4, 1), (5, 16)]
p =  73 :: order = 91 :: 12 solutions, first five are [(0, 5), (0, 11), (0, 15), (0, 26), (0, 28)]
p =  79 :: order = 97 :: 52 solutions, first five are [(0, 3), (0, 24), (0, 28), (0, 30), (0, 34)]
p =  83 :: order = 102 :: 41 solutions, first five are [(2, 19), (5, 67), (6, 6), (8, 14), (13, 52)]
p =  89 :: order = 108 :: 132 solutions, first five are [(1, 8), (1, 81), (2, 44), (2, 45), (3, 34)]
p =  97 :: order = 117 :: 64 solutions, first five are [(0, 2), (0, 3), (0, 16), (0, 24), (0, 31)]

So we have in most cases many solutions. Sometimes we can use in $y^2=x^3+ax+b$ the values $a=0,\pm1$, and we find a suitable pair. But to have a "straightforward decision"... Then "something" in the structure of the elliptic curves must be predictible.

---

At any rate, here comes the counterquestion: What exactly is expected as a "good answer", a "good constructible solution" to the OP?

Answer 2

An elliptic curve over a finite field that achieves Hasse's upper bound is usually called "maximal". Here is a recent article with some answers to your question: https://arxiv.org/pdf/1709.01352.pdf