7

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

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

有没有一个好的程序来计算这条曲线上的点数？

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

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

4

4 回答 4

3

你听说过圣人吗？

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
于 2009-01-03T05:14:44.300 回答
2

为此，我也一直在使用 Mike Scotts 程序（miracl）。只是好奇，我可能会问：您可以使用该软件生成的具有主要组顺序的域有多大？我升到了 1024 位，现在退出了，因为我需要我的办公室 PC 来连续数周运行点计数软件以外的东西。您是否制作了更大的域？如果是这样，我会很高兴获得域参数，如果您没有异议，请将它们包含在我的 ECC 软件学术签名中。

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

问候。

于 2013-03-17T14:34:13.860 回答
1

我试过圣人。我花了大约 3-4 个小时编译到 x64 ubuntu。这似乎是一个很好的程序。但是当 j-invariant 为 0 时，不能使用 SEA 算法，如果 p/k 使用较大的值，似乎会出现一些问题。

在搜索了更多之后，我还发现了 miracl：http ://www.shamus.ie/index.php?page=elliptic-curves 他们对普通的 Schoof 和 SEA 算法都有实现。但是这个程序在使用大输入值时也存在一些问题。运行 3-4 小时后，它崩溃了：/。我试图修复它，目前它正在再次运行，所以希望它会起作用。

编辑：它现在工作。上面链接中的程序与 Rasmus Faber 给出的程序相同。

于 2009-01-04T14:03:46.527 回答
1

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

于 2009-01-07T18:35:35.790 回答