Эллиптическая кривая над конечным полем

[Imperator]

Найти эллиптическую кривую с наибольшим количеством точек, заданную над полем $\mathbb{F}_{13}.$

[maxal]

А в чем хитрость-то? Рассматриваем кривые в канонической форме $y^2=x^3+ax+b$ (таких кривулек не более $13^2=169$ штук) и считаем количество точек на каждой из них алгоритмом SEA или еще каким, ну и выбираем ту, что имеет наибольшее число точек.

Вот реализация на PARI/GP с использованием пакета ellsea:

? read("sea.gp");
? m=0; for(a=0,12,for(b=0,12, trap(,0, E=ellinit([0,0,0,a,b]*Mod(1,13)); t=ellsea(E,13); if(t>m,m=t;B=[a,b]) ) )); print(m); print(B)
21
[0, 4]

Таким образом, наибольшее число точек (равное 21) над $\mathbb{F}_{13}$ имеет кривая $y^2=x^3+4.$

[RIP]

maxal писал(а):

Таким образом, наибольшее число точек (равное 21) над $\mathbb{F}_{13}$ имеет кривая $y^2=x^3+4.$

Только точек 20. 21 их и быть не может по теореме Хассе-Вейля.

Добавлено спустя 1 минуту 40 секунд:

Хотя, наверное, считались точки на проективной кривой.

Добавлено спустя 2 минуты 55 секунд:

maxal писал(а):

А в чем хитрость-то?

А хитрость, видимо, в том, чтобы подобрать искомую кривульку вручную.

[maxal]

RIP писал(а):

Хотя, наверное, считались точки на проективной кривой.

Логично. Считается ведь порядок группы, а без бесконечно-удаленной точки группы не будет.

RIP писал(а):

А хитрость, видимо, в том, чтобы подобрать искомую кривульку вручную.

Ужос. Рутинной (алгоритмиризуемой) работой должен заниматься компьютер, а человеческий мозг можно занять чем-нибудь более интересным.

Кстати, порядок 13 довольно мал и вместо тяжелой артилерии (SEA) можно считать тупо в лоб по формуле (4). Результат (как и следовало ожидать) тот же:

? m=0; for(a=0,12,for(b=0,12, t=14+sum(x=0,12,kronecker(x^3+a*x+b,13)); if(t>m,m=t;B=[a,b]) )); print(m); print(B)
21
[0, 4]

[RIP]

maxal писал(а):

RIP писал(а):

А хитрость, видимо, в том, чтобы подобрать искомую кривульку вручную.

Ужос. Рутинной (алгоритмиризуемой) работой должен заниматься компьютер, а человеческий мозг можно занять чем-нибудь более интересным.

Учитывая вид искомой кривой, ее можно подобрать вручную (и это легко). На различных олимпиадах порой бывают конструкции похлеще.

[Echo-Off]

Здравствуйте.

Пусть $p$ - простое число, и рассмотрим эллиптическую кривую $y^2=x^3+ax+b$ над полем $\mathbb{F}_p$. Известны ли условия (хотя бы достаточные), когда она имеет ровно $p+1$ точек (включая нулевую)?

Мне известно, что такое верно при $b=0$, $p \equiv 3 \pmod 4$ и $a=0$, $p \equiv 2 \pmod 3$. А ещё когда?

[Коровьев]

А с чем связана такая задача?

[Echo-Off]

1) С алгоритмами нахождения числа точек эллиптической кривой
2) Просто интересно