Число очков на эллиптической кривой
Если у Вас есть эллиптическая кривая в форме:
y^2 = x^3 + a*x + b (mod p)
Существует ли хорошая программа для вычисления числа очков на эту кривую?
Я читал о Schoof и алгоритм Schoof-Elkies-Atkin (SEA), но я ищу реализации с открытым исходным кодом. Кто-либо знает хорошую программу, которая может сделать это?
Также, если 1 и b 0, алгоритм SEA не может использоваться, потому что j-инвариант 0. Это корректно?
3 ответа
Здесь существуют некоторые ссылки: Реализации частей проекта P1363.
Я судил 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.
Вы услышали о Sage?
Среди мудреца Pari, который является пакетом с открытым исходным кодом для теории чисел. У Pari есть реализация SEA.
sage: k = GF(next_prime(10^20))
sage: E = EllipticCurve(k.random_element())
sage: E.cardinality() # less than a second
100000000005466254167