素数判定について

質問

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

回答No.2

yumikowoyorosiku

「コンピュータと素因子分解」和田秀男著
発行遊星社・発売星雲社
ＩＳＢＮ４-７９５２-６８８９-４
本体２０００円＋税

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

「高速乗算法と素数判定」
上智大学講究録Ｎｏ．１５

という本にも解説されています。
そちらのお求めは、
東大赤門前の有隣社（０３－３８１４－０２７５）か
東大病院前（というか旧数学科の前）のマテマティカ
（０３－３８１６－３７２４）まで。
本格的に勉強なされるのでしたら、

「A Course in Computational Algebraic Number Theory」Henri Cohen著
Graduate Texts in Mathematics 138,
Springer-Verlag
ＩＳＢＮ３－５４０－５５６４０－０
ＩＳＢＮ０－３８７－５５６４０－０

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

回答No.1

stomachman

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