7

次の形式の楕円曲線がある場合:

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

この曲線上の点の数を計算する良いプログラムはありますか?

Schoof および Schoof-Elkies-Atkin (SEA) アルゴリズムについて読んだことがありますが、オープン ソースの実装を探しています。これを行うことができる良いプログラムを知っている人はいますか？

また、a が 1 で b が 0 の場合、j 不変量が 0 であるため、SEA アルゴリズムは使用できません。これは正しいですか?

4

4 に答える 4

3

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

この目的のためにも、Mike Scotts プログラム (miracl) を使用しています。ちょっと興味があるので質問させてください: ソフトウェアで生成できる素数群の順序を持​​つドメインはどれくらいの大きさでしたか? 私は 1024 ビットになりましたが、数週間続けてポイント カウント ソフトウェアを実行する以外の目的でオフィス PC が必要になったため、今はやめました。より大きなドメインを作成しましたか? もしそうなら、喜んでドメイン パラメータを取得します。異議がなければ、それらを私の ECC ソフトウェア アカデミック シグネチャに含めます。

私のドメインはECC ドメイン ページにあります。それらを使用するソフトウェアは、ダウンロードページへのリンクを含むマニュアルからアクセスできます

よろしく。

于 2013-03-17T14:34:13.860 に答える
1

私はセージを試しました。x64 ubuntu にコンパイルするのに約 3 ～ 4 時間かかりました。いい番組になりそうです。しかし、j-invariant が 0 の場合、SEA アルゴリズムは使用できず、p/k に大きな値を使用すると問題が発生するようです。

さらに検索した後、ミラクルも見つけました。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 に答える