2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Эллиптическая кривая над конечным полем
Сообщение06.01.2007, 15:34 


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

 Профиль  
                  
 
 
Сообщение09.01.2007, 09:47 
Модератор
Аватара пользователя


11/01/06
5532
А в чем хитрость-то? Рассматриваем кривые в канонической форме $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.$

 Профиль  
                  
 
 
Сообщение09.01.2007, 10:00 
Заслуженный участник
Аватара пользователя


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

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

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

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

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

maxal писал(а):
А в чем хитрость-то?

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

 Профиль  
                  
 
 
Сообщение09.01.2007, 10:25 
Модератор
Аватара пользователя


11/01/06
5532
RIP писал(а):
Хотя, наверное, считались точки на проективной кривой.

Логично. Считается ведь порядок группы, а без бесконечно-удаленной точки группы не будет.
RIP писал(а):
А хитрость, видимо, в том, чтобы подобрать искомую кривульку вручную.

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

Кстати, порядок 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]

 Профиль  
                  
 
 
Сообщение09.01.2007, 10:50 
Заслуженный участник
Аватара пользователя


11/01/06
3665
maxal писал(а):
RIP писал(а):
А хитрость, видимо, в том, чтобы подобрать искомую кривульку вручную.

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

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

 Профиль  
                  
 
 Эллиптическая кривая в конечном поле
Сообщение31.07.2008, 00:50 
Аватара пользователя


23/09/07
364
Здравствуйте.

Пусть $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$. А ещё когда?

 Профиль  
                  
 
 
Сообщение31.07.2008, 22:40 
Заслуженный участник
Аватара пользователя


18/12/07
760
А с чем связана такая задача?

 Профиль  
                  
 
 
Сообщение17.08.2008, 08:25 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group