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

このQ&Aに関連する最新のQ&A

A 回答 (2件)

「コンピュータと素因子分解」和田秀男著


発行遊星社・発売星雲社
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

を手元に置かれると宜しいかと思われます。
書き込むのが遅すぎましたかもしれませんが、
お役に立てれば幸いです。
    • good
    • 0

回答になってないんですが...


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年)でヒットしますから、コピー入手可能でしょう。また、国内の何処やらの大学の修論発表会のリストにも載ってますから、その大学に問い合わせる手もあるかも。
 なお、他にも楕円関数論を使った高速な方法がある。もちろんこの分野の話を理解するには最低限代数学・ゼータ関数の知識は要求されるでしょうから、いっぱい勉強しないといけないですね。
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング