Siempre he pensado que la Naturaleza del obligado es fuerte (al menos para curvas elípticas). En otras palabras, siempre he pensado que, dado un número primo $p$, me pueden encontrar dos curvas elípticas $E_1,E_2$ sobre $\mathbb F_p$ tales que $\#E_1 = \lceil 1+p-2\sqrt p \rceil$ e $\#E_2 = \lfloor 1+p+2\sqrt p\rfloor$. Pero es esto cierto? Si es así, ¿hay una manera fácil de construir estas curvas? He visto la prueba de cómo obtener estos límites, pero creo que no me da ninguna información sobre la nitidez de la envolvente.
Respuestas
¿Demasiados anuncios?
Álvaro Lozano-Robledo
Puntos
10558
Una curva elíptica sobre un campo finito que logra el límite superior de Hasse generalmente se denomina "máxima". Aquí hay un artículo reciente con algunas respuestas a su pregunta: https://arxiv.org/pdf/1709.01352.pdf
dan_fulea
Puntos
379
Esta es sólo una respuesta parcial, sólo refleja lo que yo haría para un determinado lugar pequeño prime $p$. El carácter de la respuesta experimental. El método es la enumeración exhaustiva. Así que para un pequeño $p$ podemos usar equipo de asistencia, por debajo de la salvia, para validar o invalidar la reclamación.
Consideremos, en primer lugar $p=7$. A continuación, el siguiente código:
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)
ofrece la simétrica (w.r.t $p+1=8$) estadística:
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)]
y la pregunta que quiere de una manera para detectar las dos curvas elípticas $y^2=x^3+4$ e $y^2=x^3+3$ que alcanzan los límites.
Para $p=11$ tenemos tal vez la última imprimible caso:
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)]
No veo un método constructivo que golpea con precisión uno de los valores de $(a,b)$ para un mínimo de orden $6$ y/o máxima de la orden de $18$.
Tenga en cuenta que tenemos los siguientes pares de cuadrática giros:
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
Así que vamos a considerar sólo las curvas que dan cuenta de los "pisos de máxima Hasse obligado" para algunos pequeños números primos. Nuevo código...
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)]
Así tenemos que en la mayoría de los casos, muchas de las soluciones. A veces podemos utilizar en $y^2=x^3+ax+b$ los valores de $a=0,\pm1$, y nos encontramos con un adecuado par. Pero para tener un "sencillo decisión"... Entonces "algo" en la estructura de las curvas elípticas debe ser predictible.
En cualquier caso, aquí viene la counterquestion: ¿Qué es exactamente la espera como una "buena respuesta", un "buen edificable solución" a la OP?
