4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – ODF Dec 11 '18 at 0:54
  • $\begingroup$ 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 :) $\endgroup$ – quantum Dec 11 '18 at 1:32
  • $\begingroup$ 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$) $\endgroup$ – reuns Dec 11 '18 at 16:45
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – reuns Dec 11 '18 at 16:48
  • $\begingroup$ 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 $\endgroup$ – quantum Dec 11 '18 at 18:16

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.