Количество точек на эллиптической кривой

StackOverflow https://stackoverflow.com/questions/407977

  •  03-07-2019
  •  | 
  •  

Вопрос

Если у вас есть эллиптическая кривая в виде:

y^2 = x^3 + a*x + b (модуль p)

Есть ли хорошая программа для расчета количества точек на этой кривой?

Я читал об алгоритме Шуфа и Шуфа-Элкиса-Аткина (SEA), но ищу реализации с открытым исходным кодом.Кто-нибудь знает хорошую программу, которая может это сделать?

Кроме того, если a равно 1, а b равно 0, алгоритм SEA нельзя использовать, поскольку j-инвариант равен 0.Это верно?

Редактировать:это в контексте криптографии с эллиптическими кривыми

Это было полезно?

Решение

Здесь есть несколько ссылок:Реализации частей проекта P1363.

Другие советы

Вы слышали о Мудрец?

В состав Sage входит Pari — пакет с открытым исходным кодом для теории чисел.В Париже реализована SEA.

От http://wstein.org/papers/2008-bordeaux/sphinx/elliptic_curves.html#schoof-elkies-atkin-point-counting:

sage: k = GF(next_prime(10^20))
sage: E = EllipticCurve(k.random_element())
sage: E.cardinality()                   # less than a second
100000000005466254167

Я попробовал Сейдж.Компиляция в Ubuntu x64 заняла у меня около 3-4 часов.Кажется, это хорошая программа.Но когда j-инвариант равен 0, алгоритм SEA не может быть использован, и тогда возникают некоторые проблемы, если вы используете большие значения для p/k.

Покопавшись еще немного, я также нашел чудо: http://www.shamus.ie/index.php?page=elliptic-curvesУ них есть реализации как для обычного алгоритма Шуфа, так и для SEA.Но у этой программы также есть некоторые проблемы при использовании больших входных значений.Через 3-4 часа работы вылетел :/.Я попытался это исправить, и в настоящее время он снова работает, так что, надеюсь, сработает.

Редактировать:Теперь это работает.Программа по ссылке выше идентична той, которую дал Расмус Фабер.

Для этой цели я также использовал программу Майка Скотта (miracl).Из простого любопытства могу спросить:Насколько велики были домены с порядком простых групп, которые вы могли создать с помощью программного обеспечения?Я дошел до 1024 бит и теперь ушел, потому что мой офисный компьютер нужен мне для чего-то другого, кроме запуска программного обеспечения для подсчета точек в течение нескольких недель подряд.Вы создавали более крупные домены?Если да, то я был бы рад получить параметры домена и, если у вас нет возражений, включил бы их в мою академическую подпись ECC-Software.

Мои домены можно найти здесь Страница домена ECC.Программное обеспечение для их использования доступно здесь. Руководство со ссылкой на страницу загрузки

С уважением Майкла Андерса

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top