-PR-
締切済み

素数判定について

  • すぐに回答を!
  • 質問No.28221
  • 閲覧数316
  • ありがとう数10
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 0% (0/2)

 Adleman-Rumely法について,くわしい内容を教えてください
1980年に発表された完全な素数判定で、100桁ぐらいの整数に対応できるようです。
 図書館で調べても、インターネットで調べても、内容(アルゴリズム)まで載っているものはありませんでした。どなたか詳しく載っている本、紹介しているホームページを教えてください。よろしくお願いします。
 ちなみにAdleman-Rumely法は数学的な(整数論)バックグラウンドがかなり必要だそうです。 
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全2件)

  • 回答No.1
レベル14

ベストアンサー率 57% (1014/1775)

回答になってないんですが... APR Testというやつ。話にしか聞いてません。多項式時間に非常に近い高速な方法だそうで、今時のPCなら100桁どころじゃないでしょう。  という訳で、この際、面白そうだから探してみましたが駄目ですねえ。でも、1990年頃に改良版が出たようで、Googleで探すと→Bosma, W. and van der Hulst, M.-P. ``Faster Primalit ...続きを読む
回答になってないんですが...
APR Testというやつ。話にしか聞いてません。多項式時間に非常に近い高速な方法だそうで、今時のPCなら100桁どころじゃないでしょう。
 という訳で、この際、面白そうだから探してみましたが駄目ですねえ。でも、1990年頃に改良版が出たようで、Googleで探すと→Bosma, W. and van der Hulst, M.-P. ``Faster Primality Testing.'' Advances in Cryptology, Proc. Eurocrypt '89, Springer-Verlag, 652-656, 1990. が出てきました。この文献は、国会図書館http://www.ndl.go.jp/の検索(タイトル=Eurocrypt ,刊行=1990年)でヒットしますから、コピー入手可能でしょう。また、国内の何処やらの大学の修論発表会のリストにも載ってますから、その大学に問い合わせる手もあるかも。
 なお、他にも楕円関数論を使った高速な方法がある。もちろんこの分野の話を理解するには最低限代数学・ゼータ関数の知識は要求されるでしょうから、いっぱい勉強しないといけないですね。
関連するQ&A


  • 回答No.2
レベル4

ベストアンサー率 100% (2/2)

「コンピュータと素因子分解」和田秀男著 発行遊星社・発売星雲社 ISBN4-7952-6889-4 本体2000円+税 の第7章にずばり解説されてます。 手元にある本によると 1999年4月に改訂版第1刷発行とありますから まだ手に入ることでしょう。 また、同じ著者による 「高速乗算法と素数判定」 上智大学講究録No.15 という本にも解説されています。 そちらのお求め ...続きを読む
「コンピュータと素因子分解」和田秀男著
発行遊星社・発売星雲社
ISBN4-7952-6889-4
本体2000円+税

の第7章にずばり解説されてます。
手元にある本によると
1999年4月に改訂版第1刷発行とありますから
まだ手に入ることでしょう。
また、同じ著者による

「高速乗算法と素数判定」
上智大学講究録No.15

という本にも解説されています。
そちらのお求めは、
東大赤門前の有隣社(03-3814-0275)か
東大病院前(というか旧数学科の前)のマテマティカ
(03-3816-3724)まで。
本格的に勉強なされるのでしたら、

「A Course in Computational Algebraic Number Theory」Henri Cohen著
Graduate Texts in Mathematics 138,
Springer-Verlag
ISBN3-540-55640-0
ISBN0-387-55640-0

を手元に置かれると宜しいかと思われます。
書き込むのが遅すぎましたかもしれませんが、
お役に立てれば幸いです。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


新大学生・新社会人のパソコンの悩みを解決!

いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ