Количество точек на эллиптической кривой - PullRequest
Новая
       57

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

6 голосов
/ 02 января 2009

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

у ^ 2 = х ^ 3 + а * х + б (мод р)

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

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

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

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

Ответы [ 4 ]

1 голос
/ 17 марта 2013

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

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

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

1 голос
/ 04 января 2009

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

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

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

1 голос
/ 07 января 2009

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

1 голос
/ 03 января 2009

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

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
...