椭圆曲线上的点数

Question

如果您有一条以下形式的椭圆曲线：

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

是否有一个好的程序来计算该曲线上的点数？

我已经阅读了 Schoof 和 Schoof-Elkies-Atkin (SEA) 算法，但我正在寻找开源实现。 有谁知道一个可以做到这一点的好程序？

另外，如果 a 为 1，b 为 0，则无法使用 SEA 算法，因为 j 不变量为 0。这是否正确？

Answer 1

您听说过 Sage 吗？

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

Answer 2

为此，我也一直在使用 Mike Scotts 程序（miracl）。
出于好奇，我可以问一下：您可以使用该软件生成具有素数群阶的域有多大？
我升到了 1024 位，现在退出了，因为我需要办公室 PC 做其他事情，而不是连续几周运行点计数软件。
您是否创建了更大的域？ 如果是这样，我会很高兴获得域参数，如果您没有异议，我会将它们包含在我的 ECC 软件学术签名中。

我的域名可以在ECC 域名页面处找到。
可以从这里访问使用它们的软件带有下载页面链接的手册< /a>

问候。

Answer 3

这里有一些链接：
P1363 草案部分内容的实现（回溯此页面的备份链接 ）。

Answer 4

我试过圣人。 我大约花了 3-4 个小时才编译成 x64 ubuntu。 这似乎是一个很好的计划。 但是当 j 不变量为 0 时，SEA 算法就无法使用，并且如果使用较大的 p/k 值，似乎会出现一些问题。

经过更多搜索后，我还发现了奇迹： http://www.shamus.ie /index.php?page=椭圆曲线
他们有普通 Schoof 和 SEA 算法的实现。 但该程序在使用大输入值时也存在一些问题。 运行 3-4 小时后崩溃了：/。 我尝试修复它，目前它再次运行，希望它能起作用。

编辑：现在可以了。 上面链接中的程序与 Rasmus Faber 提供的程序相同。