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

Если у Вас есть эллиптическая кривая в форме:

y^2 = x^3 + a*x + b  (mod p)

Существует ли хорошая программа для вычисления числа очков на эту кривую?

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

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

6
задан jww 8 August 2019 в 20:18
поделиться

3 ответа

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

1
ответ дан 17 December 2019 в 04:53
поделиться

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

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

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

1
ответ дан 17 December 2019 в 04:53
поделиться

Вы услышали о Sage?

Среди мудреца Pari, который является пакетом с открытым исходным кодом для теории чисел. У 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
2
ответ дан 17 December 2019 в 04:53
поделиться
Другие вопросы по тегам:

Похожие вопросы: