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

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.

• math.dartmouth.edu/~jvoight/articles/pointscurves-moscow.pdf Prop 4.3 here seems to help - although without proof. Also note that $\sqrt(p)$ isn't an integer for $p$ prime! – ODF Dec 11 '18 at 0:54
• Yeah I thought someone would refer to Deuring which is a subject of another post. But that's a theoretical result. So it answer : only the upper bound for the first part of the question. At least I have confidence now for the upper bound :) – quantum Dec 11 '18 at 1:32
• Counting points on $E(F_p)$ is a matter of Jacobi sums thus of Gauss sums for characters of order $2,3,6$ (the idea is that $\sum_l \chi_3^l(n)$ indicates if $n \equiv a^3 \bmod p$ for some $a$) – reuns Dec 11 '18 at 16:45

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

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?

• I think it could become less cryptic once turned into a statement about Jacobi sums and Gauss sums for characters mod $p$ of order $2,3,6$ (perhaps even find directly the $a,b$ such that $y^2= x^3+ax+b \bmod p$ attains the bound) – reuns Dec 11 '18 at 16:48
• For me this is a good answer. Though, brute force. A better answer would be a more efficient algorithm but this is good enough. Im not sure if character sum is necessarily cheaper. The fact that there exists such a curve for both integral bounds is from Deuring so I will probably accept this as an answer after waiting a bit to see how others respond. Thank you for the sage code – quantum Dec 11 '18 at 18:16